Posts: 12
Threads: 2
Joined: Mar 2012
Quote: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.
Posts: 12
Threads: 2
Joined: Mar 2012
Alright, I though I would let you guys see the latest iteration, this version runs though three sections keys, toggle walls, and ice. The AI (which can see the whole board) comes up with a plan at the start and then executes it.
Also, thanks for the support, it's nice to know that people are interested.
Posts: 12
Threads: 2
Joined: Mar 2012
Quote:...well, wouldn't it be different if there was a blank floor to your left but a bomb right above you? Would the AI be able to detect the presence of the bomb (or at least 'remember' it in future playthroughs) and hence avoid it?
Yes, in the case you describe the state would be different. Though a better example would be chip above you, as in one case you have collected a chip and in the other you did not. As for remembering the presence of a bomb, I was actually talking about AI's in general so that is depend on the implementation. But our AI is designed to see the 9x9 grid that a human sees, and not remember anything between play throughs, though it is very easy to extend the vision of the AI to the whole board at which point the AI dosen't need to remember anything.
Posts: 81
Threads: 19
Joined: Jul 2012
Favorite Pack: CC1
On a more funny note, what about an AI for teeth? Make it intelligent enough to kill Chip every time or make sure that he can't solve the level? e.g. Avoid the trap buttons in My Friend?
- budugoo
Posts: 718
Threads: 67
Joined: Jan 2012
Favorite Pack: CC1
Scorecard:
Lessinath
It would be better if it worked in currently existing levels to some extent, even if it did change the solution.
Quote:You tested your own land mine. It worked!
Posts: 12
Threads: 2
Joined: Mar 2012
Wow, I haven't posted in a year about this, but I wanted to get back to this project. After I finished the AI in April 2012 I got a new job and moved to New York, so I've been busy focusing on other things but right now I'd like to share if people are still interested.
The AI for Chips Challenge works it solves several real levels from the original game. I made a presentation which has some videos our AI working here
http://prezi.com/rbs_w0ai_cze/chips-chal...f-12893181 This included several videos of our AI solving real levels, (the only video that is not our AI is the one with the teeth in it)
A summery what it does. The AI is a patch to Tile World, that generates the state of the world at every tick and calls a separate program called Fast Downward which generates a plan. (This means running the AI is a bit of pain, and hard if you aren't using linux, but I could try to put something together if their is intrest.) The AI then follows this plan until it finds a flaw in it (such as discoviering new information), at which point it stops and tries again. This means the AI dosen't work in real time, it effectively pauses the game while it does it's thinking. It ignores the monsters in the game, we never got a good version working that handled them well. Other than monsters I think the AI handles all game elements except for bear traps and teleports. Though the force floors can be slightly buggy in some cases.
I'm going to follow this thread now so feel free to ask any questions and I'll try to answer them.
