Hello everyone! I would very much like to participate in a little AI contest. But since the task appears to be very hard and I have in little experience in this area I came here for your advice. The game: The problem can be considered as a one player game. There is a board made of 100 tiles, the player and some gold treasures. The setup is quite similar to the board game "The aMAZEing Labyrinth", see picture below. So on each tile there are ways drawn in different directions. The task: The player can do about 5 actions (in every order he likes), which may be: 1) Walk around on the paths if he can (as far as he wishes) 2) Push in a tile at one side, so the whole row in the board gets shifted His goal is to reach one or more treasures on the board. The problem: The player has around 100 possibilities in every action. So when he can do 5 actions that means 10^7 aka 10,000,000 possibilities! Thats's too much to test through [crying] My question: What AI approaches are there to solve such problems (where the search space of possibilities is way to big to be completely tested)? Could neural networks help here? (although I read that they are bad at logics...) What I tried so far: I already implemented a function to evaluate a board according to certain qualities. Then I look at every possible action (but only 1 action into the future!) and choose that one that gives the best result. This works only 50% of the time since there are board setups that require to do some "bad" moves in between so that the gold can be reached. Then I tried to make the algorithm look further into the future (e.g. 5 moves) and it computed around 5 Minutes! [rolleyes] That's of course too much since I only have seconds..... What would you suggest? What methods are out there for such problems? THANKS!!!!!!!!!!!!!!!!!!!!!!!

If you have a heuristic that estimates how many steps you have left before you achieve your goal, the natural algorithm to use is A*. (Note: The graph on which you apply A* is the game tree, not the board.)

Here's a crazier idea: If the game is such that a significant fraction of random move sequences end up in the goal being satisfied, you can use UCT.

If you could post a specific example of initial board and exact rules and goal, it would be easier to think of what could work.

The rules haven't been announced completely. But here's a little Teaser-Trailer that shows some of the game mechanics (and has cool music) ;-)
TeaserTrailer

And here's an example board I generated with my AI-Test-Application (Yellow = gold, Blue = player, red = some opponent):


About my heuristic: the heuristic rather sucks. It evaluates mainly two things:
1) Distance from player to gold (the shorter the better)
2) Length of paths below player and gold (idea: longer pathes -> stuff is easier reachable)

The main problem here is:
At the beginning it works great, so the player approaches the gold quickly. But when he is very close to it and there is no way to decrese the distance (maybe they are even on tiles next to each other) but there is NO DIRECT CONNECTION the player doesn't know what to do anymore.
-> So decreasing the distance isn't always the right way....building good pathes should also be taken into consideration....

I also tried to google UCT and came up with
University of Cape Town
Underwater Camping Team
Ultra Clean Technology
etc.
But that's not what you meant, right? [grin]

So I guess I'll take a more close look at A* (since I thought that would only be used for pathfinding in RTS games)....

Sorry about not saying what I meant by UCT (I hate when people do that!). I meant "upper confidence bounds applied to trees". It's an algorithm that has been very successful in computer go, and it's so general that you can use it in single-player games, in games with randomness, etc.

UTC seems to be pretty cool :-) I could imagine that it is well suited for this problem....
Do you have some good resources on this? All I found on Monte Carlo UTC Go were some VERY SHORT explainations, that I didn't really understand (at least not far enough to be able to implement it).
Thanks's for your help so far!

Of course any other ideas are welcome, too!

Okay, I looked into UTC and MonteCarlo algorithms. Sadly I'm now pretty sure this won't work.
Here's why:
MonteCarlso algorithms rely on the information the "random solving" gives them, to see weather the initial move was good or bad.
But applying an random algorithm to this problem isn't a good idea because my simulations show: a random algo can't solve a single board out of 500. So there's no information to get from that....

On A*:
After thinking some time about it I can't see how it fits in here. I have no complete game graph to search in and my heuristic is not suitable either...
I Don't see a chance here :-(

So I'm back to zero!
More ideas please! :-D

Quote: Original post by VanKurt
Okay, I looked into UTC and MonteCarlo algorithms. Sadly I'm now pretty sure this won't work.
Here's why:
MonteCarlso algorithms rely on the information the "random solving" gives them, to see weather the initial move was good or bad.
But applying an random algorithm to this problem isn't a good idea because my simulations show: a random algo can't solve a single board out of 500. So there's no information to get from that....

I did mention that caveat when I first suggested it. However, I believe random solving will solve all of those puzzles with probability 1; It might take a really long time, though. :)

Quote: On A*:
After thinking some time about it I can't see how it fits in here. I have no complete game graph to search in and my heuristic is not suitable either...
I Don't see a chance here :-(

You don't need to have the entire graph in memory to apply A*. You do have the complete game graph in the sense that you can query what the neighbors of any node are. Really, that's all you need.

About the suitability of the heuristic, any heuristic "works", but certain heuristics will be much better than others and certain heuristics won't guarantee that you find the shortest solution.

:P, I've played that game before! I have it. :)

And? Found any cool algorithms while playing it? ;-)
Right now I'm going after the A* approach. Thanks for all your help!