CC AI

[lotu]

How many moves are possible in a CC level, given the time limit (say Lesson 1 in CC1)? Anyone with better math skills than I do have an idea?

Well Lesson 1 has a time limit of 100 seconds and you can make normally make 5 moves per second so conceivably you could make 500 moves before time runs out. There are 4 moves (up, down, left, right) so that gives us 4^500 which is around 10^301. For comparison the are only 10^80 atoms in the observable universe. Trying every every possible set of moves is not a solution except when talking about in the theoretical sense.

Now CC has a lot of repeated states, for example if you move left then up, or up, then left you are in the same sate after those two moves. So don't need to treat those as two separate situations. In other words you only have to look at different broad positions or states. The first level has 26 items that can either be on or off the board, (keys, doors, and chips) and chip has 25 valid location not including the exit. So their are (2^26)*25 around 17 billion states, (though not all are reachable), this is much less than 10^301. You could probably explore the whole state space in several seconds, with a regular desktop.

There are more advanced techniques that start to mimic how a human might solve a problem I'm using in my AI, that can reduce this state space even further.