Bubble Breaker Puzzle

i Am given a problem to solve the Bubble breaker puzzle Game. there are two parts of the game. 1.User player 2.Cpu Player. i wrote the code for the User player but have no idea how the Cpu player will play in such a way so that the cpu player can get maximum score and completly clear the board. if someone can help me with this??

when the game starts its load a file containg integer ranging b/w 1 and 3. 1 for red colour 2 for green 3 for yellow

1111111111
2323333132
1131123222
2222222113
1111111111
1111111111
1111111111
1111111111

adjacent colours shold be delete.

a game like this开发者_StackOverflow. plz help me out with the cpu player by giving me hints to get the best score. thanks in advance.

If you just need a "good" score instead of the perfect score, you can use Monte Carlo techniques. The basic idea is:

Randomly select a position to click on. Do that until there's no possibility to remove any balls. Remember the score and the points where you clicked on.

Do this 10000 times, and you will be fine against most humans.

If you still need to get a better AI player you can take the maximum score you gained above as a lower limit. You would then estimate the maximum points that can be reached from a certain position, and if that number is less that the "best random score", you can cancel that particular try.

You can treat the grid as two dimensional array.

The

11...
23...

means

arr[0][0]=1; 
arr[0][1]=1; 
arr[1][0]=2; 
arr[1][1]=3; 

And you can check the existence of same color this way:

//using arr[0][0] as the base point
if ( (arr[0][0])==(arr[0][1])) //look in your right
{
   //explode
}
if ( (arr[0][0])==(arr[1][0])) //look below
{
   //explode
}
if ( (arr[0][0])==(arr[1][1])) //look at lower right (diagonal)
{
   //explode
}

To get the best score, a number of possibilities must be calculated. Factors that affect such possibilities are:

1. how many adjacent bubbles will it take to explode? Is it 3 bubbles in a row? 4 bubbles in a row? 5?

2. another factor is how many kinds of formation does your bubble form in order to explode? horizontal formation only? vertical only? does it include diagonal?

3. The third factor is the size of your grid. How big is it?

So this would really give a huge number of possibilities after taking consideration of those factors.

But lets try analyzing a simple one. Say, 2x2 grid with horizontal and vertical formation only, taking 2 bubbles to explode:

[a][b]
[c][d]

The possibilities are: a-b, c-d, a-c, b-d = 4 possibilities.

It already gives you 4 possibilities.

So with a grid of 4x4, with vertical and hor formation, and 3 bubbles to explode would really pile up a huge computation.