• Advertisement
Sign in to follow this  

Maximising Score Algorithm

This topic is 4303 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.


Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
Can anyone verify my best game on that grid? Coordinates (1,1) correspond to the top left corner.

(1,3) (4,9) (6,2) (4,10) (3,9) (8,2) (14,9) (10,6) (1,7) (5,9) (15,4) (14,8) (10,5) (6,6) (10,7) (16,7) (11,6) (2,7) (1,8) (3,8) (12,9) (16,6) (10,9) (15,10) (3,8) (12,4) (9,8) (5,10) (11,5) (13,10) (8,5) (10,9) (10,9) (11,9) (11,9) (9,10) (13,7) (10,8) (4,9) (10,9) (7,5) (1,7) (2,9) (6,8) (4,10) (3,10) (3,10) (4,9) (1,10)
score: 1892

Share this post


Link to post
Share on other sites
Sorry alvaro, I got lost on your fifth move, I could not see how i could make the move (3,9). Just had a thought, why not put up my test program so far so here it is:

http://www.cash-inn.co.uk/blocks.zip

Click the test button to have a go at clicking the blocks for yourself, click the solve button to have the program attempt to auto solve the test grid. Note that the number counting up in 100's is how many attempts the solver has had at finding the best option and the high score label below that is the best score that has been found for that pass. This resets 8 times to allow for a different number of moves on each pass (the first pass we only search with two move options at each grid state, second with 3, third with 4 etc...) This so far has been the most favourable way of doing things as the way I assign possible moves means that the best moves are often one of the first 5 assigned, if that makes any sense at all.

For the test grid now I get scores of around 2348 although I believe a score of over 3500 is possible

thanks again for everybodys help so far

Share this post


Link to post
Share on other sites
Well, I didn't realize your blocks "fall" to the left as well. In my interpretation of the game, blocks only fall downwards. Actually, I think I have played that game before.

I'll modify my code tonight to deal with the "falling to the left" rule.

EDIT: Now that I reread your posts, you did say that blocks fall to the left after they fall down. My fault.

Share this post


Link to post
Share on other sites
I also misunderstood. In the game I work on, sliding horizontally only happens when the column is completely cleared. The columns slide as a unit. Vertically stacked blocks can not be seperated. This does not mean writing a program to solve your game is any harder, but for the human it is more difficult. Each move in your game changes the position of more blocks. Your game is more dynamic.

I would recommend you have more than one test board. If you concentrate too much on one game board, your program could end up optimized for that one board and play others poorly.

Share this post


Link to post
Share on other sites
very sorry for not being more clear about the game, I also have the option of making random boards at the moment which get similar scores to the test board so I think I wont have a problem there. Am going to try and get my head around the branch and bound technique and see if this improves the score or not.

Share this post


Link to post
Share on other sites
Quote:
Original post by Andrew2110
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.


That's actually what I meant. My apologies if it wasn't clear from what I wrote.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement