Is there a known good way to have a "computer" opponent play a Match 3 game? It doesn't have to be fancy, or even considered fair. If the AI always takes the best move on the board that would be OK with me. Note that a valid move is one that doesn't make a match.
Edit: What I am currently doing is a brute force approach. I look at every tile on the board, and see what the best move that tile can do. I add it to a collection and give it a score (based on how many it will match 3 or 4). Once I have traversed the entire board I use the move with the best score. In the event of a tie I pick one.
If a 5 match combo is found I short circuit out to that one. 5 is the highest combo you can get)
I may not be able to improve it, but it feels like this should have been solved already.
Answer
One approach would be a simple tree-search algorithm, similar to the methods used for many deterministic puzzles.
The first problem is that the new gems added with each move are non-deterministic. One way to handle that is to consider all the possibilities for each new gem. This gives a way to estimate probabilities.
The big problem is that the number of combinations to consider would be immense, even a small number of moves into the future. The solution to that is to use heuristics to prune the tree, and to guide the search. For the random gems, only consider a small random selection of the possibilities.
For more tips and more detail, Google for tree search nondeterministic games.
http://www.google.com/search?q=tree+search+nondeterministic+games
On second thoughts, try tree search nondeterministic puzzles.
http://www.google.com/search?q=tree+search+nondeterministic+puzzles
Also, remember to keep it simple - there's probably very rapidly diminishing returns in Bejewelled, either for deeper searching or for more sophisticated heuristics.
No comments:
Post a Comment