Game Player - Step 2 - Calculate the Best Move

This is an unfinished article posted to save it sitting in Draft limbo forever.

Now that we have our game state we can move on to working out what move we should make. We could, if we wanted, just click randomly on the game board and hope for results but that wouldn't really be in keeping with the project's aim, we want the system to actually play the game.

Deciding what the best move is depends on what we feel best means. Imagine a shoot'em up game where we are flying through space blasting aliens. We might decide it is best to go for the power up first and then dispatch the enemies or we might decide it is better to clear the screen of enemies and think of power-ups as a secondary objective. If we really wanted we could create a machine leaning algorithm that decides itself what is best based on experience, but that is for another day! For now we will stick to deciding ourselves what our goal is and that will help us decide what the best way to achieve it is.

For now I'm going to go with a simple goal, to clear a set of blocks from the screen with every click. This is a good goal as it will score us lots of points with each move and hopefully lead to us getting a high score come the end of the game. In the future we will have a more complex goal but we can use what we develop here as part of a bigger reasoner in the future as well and this tends to be how large A.I. systems work, lots of small reasoners working out simple things and then a larger reasoner combining all the results and deciding upon the best course of action.

So to work out which game piece will remove blocks from the board we need to find the a chain of connected, matching pieces in our game state. In keeping with our new, tidy code we'll put the code to do this into a separate function and call it from our main call in our JNI method. This is also going to be our first foray into pointers in C since I want to return 2 ints marking the row and column of the piece for our move but as we have learnt returning an array in C is a no no.

So this is going to be our function prototype:

void getMove(vector<vector<int> > gameState, int *row, int *column);

We pass in our gameState, a place to store the row to click on and a place to store the column to click on. Fairly simple, the hard task is filling this with the logic.

This is what our gameState current holds:

Our game state.

Of course the values in yours will be different unless the board lay out was exactly the same (which there is a pretty slim chance of unless you are using an image of mine). And what we want to do is find any chain of connected colours as represented by the numbers in our array (I'll use the word vector and array interchangeably). There is an algorithm that already performs a task similar to this called the Flood Fill algorithm and I think that will be a good place to start if you already have a good understanding of this sort of stuff. You can read more about the Flood fill algorithm on Wikipedia and see a good example (along with source code) of different C++ implementations of it at Lode's Computer Graphics Tutorial and with just a little modification you should be able to use it to find the biggest chain of connected colours. However my C still isn't up to scratch so I'm going to go with getting a basic algorithm in first that takes the first legal move it finds and then work up from there.