Creating an AI to play Hive with Mzinga, Part III

In the first post in this series, I introduced Mzinga, my attempt at an open-source AI for the board game Hive. Then in my last post, I gave a high-level overview of how the Mzinga AI works. Now I’d like to discuss Mzinga’s board evaluation function, which is at the core of the Mzinga AI.

As I said in the last post, the purpose of the board evaluation function is to determine, based on the current state of the board, which player is “ahead” in the game. The function returns a number from negative infinity to positive infinity, where negative infinity means the current player has lost, and positive infinity means the current player has won.

The first thing that needs to happen, is I need to collect some information about the state of the board. So I go through the board and calculate a variety of metrics – that is to say – I count a bunch of situations. For example, for each piece on the board, I count how many moves it can make, how many neighbors it has touching it, and flag  whether or not it’s “pinned” (can’t move because other pieces won’t allow it).

I also add those numbers up for each player – how many pieces does the player have in play vs. still in their hand, how many pieces do they have that are pinned, and how many total moves they have available.

I do all of this for both players, and it takes a while, relatively speaking. In chess you have the benefit of a set board size, and despite the enormous number of positions that the board could be in, it’s still in a square grid, which can benefit from some fancy programming (see Bitboards) to make it computer friendly and faster.

Hive, on the other hand, is played on a potentially infinite grid of hexes. A typical chess board might determine there are 25 valid moves for a player – in Hive I’ve seen upwards of 150.

Anyway, once I have calculated a board’s metrics, the next step is to determine what they mean. So I know Black has more pieces pinned than White, but White’s Queen Bee is starting to get surrounded, who is ahead? Black still has more pieces to play, but White has a Beetle working its way toward a key spot, who is ahead? How do I evaluate all of the different situations against each other?

The answer is to use a weighted score. Basically, I take each of the metrics and multiply the number by its matching weight. The weight can be any number, positive or negative, but every metric has it’s own matching weight, with bigger weights meaning that the matching metric has more impact on the final score.

So for example, if I think that having more available moves each turn is better for a player, then for the metric Player.ValidMoveCount, I might give a high positive value to Player.ValidMoveWeight. Since the object of the game is to surround the opponent’s Queen Bee, for the Opponent.QueenBee.NeighborCount metric I might also set the corresponding Opponent.QueenBee.NeighborWeight very high. And since I don’t want to leave my Queen Bee unprotected, for my own Player.QueenBee.NeighborCount metric, I would want to give a negative value to Player.QueenBee.NeighborWeight

My board evaluation function simply adds all of these products (metric x metric weight) together to get the board’s final score. With this kind of generic function, the question now becomes: What are the weights that make up the best AI player? The more accurately the board score actually describes how far ahead or behind a player is, the better the AI has a chance of making moves that keep it ahead until it wins.

So, what are the best weights? I don’t know. No one does. Even in a game like chess, with centuries of study, where players have a much better grasp of what pieces are the most important, and what positions are better than others, there’s still no perfect, definitive answer. Great sophisticated starting points, sure, not but not perfect.

Now for a young game like Hive, the starting point may be as simple as the “surround the enemy queen but also keep your queen from getting surrounded” with some simple guesses for those weights, and ignoring everything else on the board. And in fact, that’s where the Mzinga AI is at today. Smart enough to actually play the game toward winning, and much better than just randomly picking moves.

So how do we make it better? How do we get better weights?

Here is where the “real” fun begins, and that’s a topic for the next post. So stay tuned for Part IV, where I go more into detail about how I’m trying to improve the metric weights.

Try out Mzinga today!

/jon