Creating an AI to play Hive with Mzinga, Part II

In my last post, I introduced Mzinga, my attempt at an open-source AI for the board game Hive. In this post, I want to go through how the Mzinga AI works and what I’m doing to make it better.

Like many chess AIs, the algorithm I used for the Mzinga AI is called Minimax. At a high level, the decision making goes something like this:

  1. Determine how many moves ahead I want to look (let’s say 2).
  2. List out all of the valid moves that I, the current player could play.
  3. Try a move.
  4. After I’ve tried a move, calculate the board’s “score” with an evaluation function. Higher  (positive) numbers mean I’m doing better than my opponent, and positive infinity means that I’ve won the game. Lower (negative) scores mean my opponent is doing better than me, and negative infinity means my opponent has won the game. (We’ll come back to this in Part III).
  5. If the game isn’t over, list out all of the moves that my opponent could play at this point.
  6. Try a move.
  7. Again, calculate the board’s “score” with the evaluation function.
  8. Repeat steps 6-7 for each of my opponent’s possible moves (from that 2nd turn)
  9. Repeats steps 3-8 for each of my original possible moves (from that 1st turn)

The algorithm is called Minimax, because for each player’s turn, the AI assumes that the player will take the move that gets them the best score. I’m called the “maximizing” player because for my turns, I’m going to take the move that maximizes the score. My opponent is called the “minimizing” player, because I assume they’re going to take the move that minimizes the score.

By looking ahead, I can modify the score of an earlier move – ie. a move on my first turn might look great for me, but it may turn out that it opens up a really great move for my opponent. Since I assume they’re always going to take the best move, I replace the score of my move to equal the score of the move they’re most likely going to take. That way I don’t take the move that will screw me later.

After all of the calculations are done, I look at the original set of moves available to me, and I pick the one with the best score and actually play it.

Now, a key part of this working is the part where I “calculate” a board’s score. I’ll get into that next post, because there’s a few more things to note. First, doing that calculation, whatever it is, usually takes some time. So the more moves you look at (whether because a player has lots of moves to choose from, or because you’re searching more moves ahead) the longer it takes to come to a decision. So a lot of science goes into reducing how long it takes to calculate a board’s score, and how to avoid looking at some moves all together.

To reduce how long it takes to calculate a board’s score, I use a Transposition Table. Basically, since I’m playing a game where you take turns moving one piece at a time, there’s a good chance that I’m going to end up in the same layout of pieces, or position, at some point in the future. So, as I’m going along calculating board scores, I save them off. That way, when I see a position that I’ve seen before, I can just reuse value I’ve saved. As the game progresses, that table gets bigger and bigger, and I have more saved off values to reuse.

To reduce how many moves I look at, I use Alpha-Beta Pruning. Essentially, it means that if I’m looking through a player’s moves, there are times when I know that there’s no point in looking anymore. If I do move A and while looking through my opponent’s possible responses I see a move that wins the game for them, I don’t need to look at any more moves that would come after playing move A. I assume that playing move A will lose me the game.

The final thing I do is something called an iterative search. The deeper the depth of your search, the exponentially longer it takes. The game wouldn’t be very fun to play if the AI takes hours to decide what to do. Conversely, if the depth is too low, then the AI will be considerably weaker, since it doesn’t “think ahead”. So instead we do an iterative search.

It turns out that Alpha-Beta Pruning is most effective when you look at the “best” moves for each turn first. Only, if we already knew the best moves, we wouldn’t need to search! To help Alpha-Beta pruning out, what I do is:

  1. Search to a depth of one, ie. just looking at my move and not my opponent’s response.
  2. Sort my moves from best to worst.
  3. Search again but now to a depth of two, looking at both my moves and my opponent’s responses.
  4. Sort my moves again from best to worst.
  5. Search again but now to a depth of three, looking at both my moves, my opponent’s responses, and my next move.
  6. And so on, and so on…

Instead of having a set depth to search, I instead set a time limit on my search, say five seconds. I start searching deeper and deeper, each time resorting the moves better and better, until I run out of time. Combined with the fact that I’m saving off board scores as I go, each search iteration gets faster and faster as I see the same board positions over and over.

Now, a lot of code is spent making these operations go as fast as possible, but at the end of the day, the everything hinges on how good your AI is at evaluating a board’s position. The faster and more accurately you can rate who’s “ahead”, the stronger your AI will be.

Stay tuned for Part III, where I go more into detail about how the AI evaluates board positions and how I’m trying to improve it.

Try out Mzinga today!


Update (15-JUL-2016): Creating an AI to play Hive with Mzinga, Part III is up.

Creating an AI to play Hive with Mzinga, Part I

I first started playing chess seriously in college, and I learned just enough to realize that I wasn’t going to be able to commit to the kind of study that makes a great chess player. I even built a super weak chess AI in Matlab that just made random moves. More recently I’ve gotten back into playing over at (hit me up for a game), and when I was looking for a side project last winter, I peered back into the deep and treacherous waters of chess AI programming.

But I’d already built a chess AI (dumb as it was) and wanted to do something new. Then it occurred to me that I could try to make an AI for another game I love to play, Hive.

What is Hive? Hive is an abstract board game (like chess) where the pieces are different kinds of bugs. Each bug moves in a certain way, and the goal is surround your opponent’s Queen Bee before they surround yours. Like chess in many ways, but simpler and more approachable to many people.

So I started looking around to see if anyone had already created any Hive AIs. While there is some software for playing Hive (play Hive online at Boardspace, with the PC game from BlueLine Games, or via various mobile apps) and that software usually has an AI player to play against, I couldn’t find anyone specifically trying to make a strong Hive AI player.

The chess world on the other hand, is loaded with people trying to make better chess AIs. The amount of available chess AIs (see this list of chess engines for example) and publicly available research material (see the Chess Programming Wiki) is simply astonishing.

One of the coolest aspects of it is the separation of the chess engine (where the AI does its work) and the UI (which just displays the game). There are well established protocols that chess engines can implement (such as the Chess Engine Communication Protocol or the Universal Chess Interface) to specify how you ask a chess engine to evaluate a board and pick the best move. This means that by implementing these protocols, chess programmers don’t have to agree on what programming language to use, or waste time making pretty interfaces. They can focus on the guts of their engine, using whatever tools they want, and they’ll be able to participate in games against both humans and other chess engines.

It’s with that model in mind that I started work on Mzinga.

Mzinga 0.9 ScreenshotMzinga is an open-source AI to play the board game Hive. It is architected similar to various chess-playing AIs, consisting of:

  • A set of standardized commands similar to the Universal Chess Interface
  • An command-line reference engine, which accepts the standardized commands
  • A general board UI which can interface with any engine that implements the standardized commands

The goal is not to simply implement Hive in code, but to establish a standard way for programmers to create their own AI players. The hope is that this will encourage explorations around Hive AI.

It’s written in C# (see the Mzinga source on GitHub) and runs on Windows 7 and above. You can play player vs. player, player vs. cpu, or cpu vs. cpu. It’s very beta – the included AI is not very strong, and the UI is a little bare, but it is very playable. Check it out and let me know what you think!

Stay tuned for Part II, where I go more into detail about how the AI works and what I’m doing to improve it.

Try out Mzinga today!


Update (14-JUL-2016): Creating an AI to play Hive with Mzinga, Part II is up.