steamknight.com

Let me begin with a bit of backstory.  In its most current incarnation, Pookie Pookie is written in C#, the thought behind this to allow it to be playable on the PC as well as the Xbox 360 via XNA — and who knows?  Maybe get published on Xbox Live Arcade?  Ahhh…  a boy can dream.

I’d made the decision early on to develop the core internals of Pookie Pookie as a separate DLL and build a console (as in text-mode) based harness to test it out.  This would allow me to be able to quickly make sure that the logic was working properly before spending a lot of time doing the graphical version.  It also makes development and iteration over the code much faster.

Walking into this project today, I already had the board representation down as well as all the logic necessary to process the moves and score.  My focus for today is creating an input model that will work for both human and AI players.  Hopefully, with XNA 2.0, this will expand to both local and remote players.

Once the input model is finalized (it sounds really simple, but it’s more complex than you think), the next step is to create the AI for Pookie Pookie.  In a previous post, I mentioned my thoughts on the AI, so I won’t repeat them here.

Once the AI and input are in place, the core game will be complete and working on the console and it will be time to make that jump to the graphical version.  Much like the Unreal Tournament 2007 team did, I will not be focusing on the graphic assets just yet.  Using simple shapes to denote the pieces, board, etc. will allow me to focus on the gameplay without getting stuck on the assets until the game is ready.

What separates a game, even a good game, from a great game?  Spit and Polish™!  Having the game automatically dump you into a match will simply not do.  In order for the game to look really good it must have the following features:

• Title Screen
• Main Screen (this has links to other areas)
  • New Game (Local game 1 to 3 bots)
    • New Game Screen (this is where you choose who is a human and who is a computer)
  • Xbox Live
    • Create a game
    • Join a game
  • Tutorial (Teaches you how to play the game)
  • Achievements (See all your achievements)
  • Options
  • Exit

Clearly there’s a lot to be done by my birthday and not a lot of time to slack off.  During this Thanksgiving week I am to have a lot of this done, namely:

• The core gameplay (player input, AI)
• Screen management
• Multiplayer

This is pretty aggressive, but I hope to kick some ass .  I’ll talk more about the are areas when the game is working in its most basic form.

I’ll hopefully have more updates as the project comes along.

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!

In my previous post I mentioned that we’d talk about how we store the state in Ataxx, or as I’ll call it from now on, Pookie Pookie.

Not all squares on the 7×7 game board are free, some of them can have a wall or obstacle, making that particular square permanently occupied. The walls are mirrored on all four quadants like these examples:

If we label the squares in the top-left quadrant 0-15, we can encode the walls with 16 bits, where a 0 signifies an empty square and a 1 is a square with a wall. The previous 3 examples would be encoded as 0111100010001000, 000000110100010, and 1000000100100100 respectively or 0×7888, 0×01A2, and 0×8124.

Note that bits 3, 7, 11, 12, 13, 14, and 15 are shared between two or more quadrants. Because the players always start at the corners, bit 0 can never be 1 so there really are 2^15 possible board layouts. Of those 32k board types, many will result in the players being “locked in” unable to move causing the game to automatically end since there are no more moves. It takes a minimum of 8 “on” bits to make sure that the game is over before it starts. I find that 6 “on” bits is about the most you can do and still have interesting playable boards, so really, the number of functional game boards is much smaller.

Weird Math…
If I’ve done my math right, any 6 bits out 15, 5 out of 15, 4 out of 15, 3 out of 15, 2 out of 15, 1 out of 15 and all zeros are valid boards. “X choose Y” is calculated by so the equation should be which should equal to 9949 boards! If someone sees fault with this, please let me know

Now that we know how to encode the board type, how do we encode the board itself?

Assuming we do a two player game, each square can have one of four states: it’s free, it has a piece from player 1, it has a piece from player 2, or it has a wall. (4 player is similar, just requires a little extra work). Since we have 4 different states we can encode each cell with 2 bits, making each row 14 bits. If we squeeze this into the lower bits of a 16-bit integer, the whole board gets encoded in 14 bytes! How’s that for frugal?

We’ve accomplished a few goals by having created such a small data structure for the representation of the board. We have very little data that we have to transfer in a multiplayer game over the ‘net, and we’re minimizing the ammount of memory needed by the AI to figure out what move to make. As well see in the next post, we’ll be very glad that our board data is so small!

Also, I promise that the next one will have less math, certainly it won’t have any equations!