Hello everyone! I'm having some trouble working out how to create an auto solver algorithm for my game and was hoping someone here could help me out or point me in a direction where I could find help. As I'm only starting out with game programming my game is simple and rather boring: there are a number of blocks on a 16x10, to get points you click on a set of two or more similarily coloured blocks, the score for which is the amount of blocks you just clicked on, squared (ie. if you clicked on a group of 5 blocks you would get 25 points (5x5). Anyway I've tried making this so far with a tree structure where its branches hold moves possible from the current grid state, the problem with this being that there are up to 15 moves on some grid state so the tree rapidly becomes to big to handle, however I feel that I may be going the wrong way about this so any pointers on how to make a maximising function with a tree would be great :) Functions that I have that I know work are: getmoves(var grid:TGrid;x:integer):integer; which tries to populate a grid with x moves and returns the actual amount of moves it could put into the grid. domove(var grid:TGrid; moveoption:byte):integer; which removes all moves of number 'moveoption' from the grid and returns the score for doing this. there are a number of other functions that do things like resetting the grid but the above I think are the most important for the auto solver. Anyway sorry for the long first post, any help would be much appreciated! Thanks

Let me make sure that I understood this correctly. After you make a move something happens to the grid that makes the list of available moves change, right? At some point you will get stuck with no moves available, and your total score is the sum of the scores of the previous moves, right?

If all of that is correct, there are two things that I would try:

1) Make an A*-style search where you guide the search using the score so far and a heuristic expectation of the score you will get in the future. If you don't have time to exhaust all possible the branches in the tree, you can stop this algorithm when you run out of time, and the best path found so far should be pretty good.

2) Monte-Carlo. For each one of your possible moves, play N random games, where N is a largish number. Pick the move that gets the highest score you find. If you manage to make the simulation fast, this might play reasonably well.

I have been working on a similar problem in my spare time for the last few years. JT's Blocks on Yahoo Games has a 14 x 9 grid with 5 colors. Looking at the average branch factors I estimate 1E+34 possible board positions. A complete tree search would not be possible. If your grid is 16 x 10 you would have a much larger tree. A classic NP Hard problem.

I know a few programmers that have tried to solve the game. Most use a brute force approach using a breadth first search. After searching a ply, continue the search of the next ply using only the nodes that have the highest evaluations.

One programmer was using a genetic algorithm. I don't have any idea of how it worked, but it is interesting.

I honestly cannot work out the gameplay from the terse descriptions given. Could the OP please describe the game in more detail (describe a game state and how the game transitions between states, what the set of user actions is, etc) so that we can offer realistic advice for how an optimal (or near optimal) AI might be designed to play the game. Without this description we're just poking around in the dark.

Cheers,

Timkin

Hi. Thanks for the replies :) so far I have tried the 'monte carlo' approach after starting the game off in a way in which I would like to which has given me a more favourable start, although after around 50,000 searches I start thinking that most of the time its just going over combinations its already gone over, still this is scoring around 300,400 more points than my previous solution so thankyou!

Sorry if the description of the game was a little poor, a test grid I've been working on can be found at:

http://www.cash-inn.co.uk/grid.jpg

Note that when a set of blocks is cleared, other blocks on the grid are moved first down and then left to fill the blank spaces.

Thanks again for your replies so far.

I will adapt my program and use your test grid and see what score I can find.

What is your current best score for that test grid?

thanks again for all your replies, have now started reading up on genetic algorithms and am finding it very interesting! For that test grid the high score was 1802, that was done by first getting rid of some blocks which there are least of (there are only very few reds so program gets rid of a few of these to leave larger clusters of other colours), then the program chooses the highest score out of 40,000 attempts and then shows the user the path to this score. I would be interested to hear of any better ways this can be done :)

Okay, now I believe understand the game... I've played this before...
you click on a coloured block to make it and any of its neighbours (and any of their neighbours) of the same colour disappear, generating a hole, into which blocks above fall. If the result of a 'clearing' leaves a blank column (or columns) the blocks to the right of the column all shift left (to move the empty space to the far right). If there are any difference between your implementation and this outline, could you elaborate on them please?

My thoughts as to a solution method go down two lines. One is to use a branch and bound type optimisation strategy with the tree search and the other is to implement a pattern based solver that incorporates delay learning. I'd probably lean toward the former, although the latter might be more fun to design.

Cheers,

Timkin

I changed my program to handle your grid. I am not 100% sure it is working correctly. A quick search found a score of 1602. This is 200 less than your score. Do you add a bonus for clearing the board?

Searching a little deeper I found 1658. A much deeper search yielded 1776.

I can verify your score if you can supply the moves for your solution.

Hi. I'm very sorry for not saying this earlier but yes there is a 1000 point bonus for clearing the board, without the 1000 point bonus my algorithm would rarely score over 1000 :(

Thanks for your post timkin. There is one slight difference between my implementation and yours in that when squares are clicked on, the blocks above the column are shifted downwards to fill the blank, and then the blocks to the right are shifted left to fill blanks.

Our algorithms lecturer tried teaching us a branch and bound technique last term so maybe it would make sense for me to try implementing this first but a pattern based solver does sound a lot more fun!

If anybody is interested in swapping any psuedocode for their similar games then I would be happy to see what else is out there, just PM me and I'll sort out my design documents :)