As only my most loyal readers may recall, a few months ago I discussed the game Ataxx and expressed my desire to write a version of the game Pookie Pookie. It’s the kind of project that everyone has: you work on it a little bit, life gets in the way for months, the you work on it some more. At some point you realize that better tools are out so you start over — and the cycle continues.
At this point I’m not going to make vague promises of getting the game done, but I can catalog here my periodic progress. What I wanted to talk about today was the AI for the game.
Pookie Pookie is a logic game meaning that given a board there are a finite number of valid moves that can be made. Also it is a “full information game”, both players know everything about the other player’s possible moves and status in the game. This makes Pookie Pookie a perfect candidate for Min-Max Algorithm.
MinMax
When using Min-Max, you start off with the current state of the game. From there you look at all the possible moves that a player can make — the idea is to Maximize the player’s score. For each one of those possibilities, we do the same from the other player’s perspective. In essence we try to Minimize the original player’s score. Then, for each one of those we do it all over again. If this is starting to sound like a tree to you, then you’ve been paying attention. The more we run this, the more “think-ahead” will the AI do.
Each possible result (node in the tree) is evaluated and given a score. We then choose the move that leads us along the right path. We can then “prune” the other branches. There is no need to throw away the whole tree since we’ve already calculated all of our opponent’s possible moves based on ours. We simply figure out which move they made and make that node the new root. All we have to do then is keep the tree up to date which entails Minimizing and then Maximizing once regardless of how many moves we want to look ahead.
By the way, when I say two moves, I mean two moves for the player, which is really 5 moves: the move we make, the opponent’s response, our first look-ahead move, the opponent’s response, and our final look-ahead.
Assume that we have two moves look-ahead, we end up calculating a tree that is 6 levels deep. The first level is the root node which is the current state of the board after the opponent’s move. The second level is every possible move for us, let’s say we have 5 possible move. Level three, is every possible response the opponent can take to counter us. Let’s say that there are 4 possible moves for each one of ours — 20 moves total. Now comes the first look-ahead, for each one of those twenty moves, we calculate all the possible moves — assuming each one leaves us with 5 moves, this level has 100 possible moves. As you can see, it quickly gets very large. By the time we get to the second look-ahead move, we might have over a thousand.
We then choose the move on level 2 that is the ancestor of the best scoring move, our opponent will make their move and we will already have a partially constructed tree. As a matter of fact, all it needs is for us to calculate the second look-ahead over again since what was the second look-ahead last move is now the first one.
Evaluation Function
Being able to create the Min-Max tree is useless we know how to pick winning moves. To do this we need to run an evaluation function over every node. The evaluation would go something like this:
- Calculate the score delta for the move
- Since we want to favor sliding (cloning a piece) over jumping (moving a piece which might leave us exposed), subtract 1 if this move is a jump
That’s it! Two simple rules. It’s possible to add a whole bunch of heuristics to the evaluation function, but sometimes simple is better. Using this evaluation function, I’m ashamed to admit that I lost to the AI even though it was doing no look-ahead. I had underestimated it and it generated some pretty good moves. Subsequent tries have yielded me I took it seriously and I cheated — I knew how it was going to choose a move because I wrote the algorithm 
Lastly, when we go to choose a move, it’s possible that may paths will ultimately yield the same evaluation value. To keep the opponent guessing, if we have two or more “best” moves, we’ll choose one randomly. This could probably be more intelligent, but it’s good for now.
Musings
The MinMax approach is not without its problems. The more you look ahead, the more larger the tree and even a tree that’s not that deep can grow to thousands of nodes. It may also take a while to evaluate all those moves, so on less powerful or memory constrained hardware it may not be feasable to do too many look-aheads.
On the other hand, some of the burden could be levied by having a thread dedicated to generating the tree, even when the player is still selecting their move. On a dual core CPU or an Xbox 360, maybe this thread can even run on its own core — multithreaded programming, of course, bring along its own special set of problems but it’s a pretty interesting solution since we could leaverage the “dead” time when the player is thinking about their move.
Ultimately, if there is enough memory on the system, it might even be possible to calculate every possible move up to the endgame — It’s something I’d be interested in experimenting with, but feasable only for machines with a lot of memory.
Another possible improvement for slow systems is to see how many look-aheads can be done in x seconds, and use that as the top limit for the AI. Here, x is the number of seconds we think the player won’t mind waiting for the computer to act.
Ok, this was a long post, more later!