Vying Games : Blog

In this article I discuss the AI used by Vying Games' Othello bots (see Wikipedia on Bots if you're unfamiliar with the term). As you read about them, keep in mind that my overall goal with these bots is that they are:

1. Fast (hopefully, making a decision in less than a second)
2. Competitive with as many players as possible (I don't want dominance, one way or the other), and
3. Varied (each bot should have its own strategy)

Commonalities

I've tried to create bots that use completely different strategies in order to give people both variety and different levels of play. However, CapellaBot, VegaBot, and SiriusBot each share a common base.

For one, they all use the same search algorithm (alpha-beta pruned minimax, with differing search depths), and the same end game evaluation function. As such, they all try to maximize discs when they near the end of the game. SiriusBot does have an advantage here: it adjusts its search depth as it nears the end game, giving it perfect play from further out.

They also share an opening book that they play from randomly. It's gleaned from this list of human Othello openings, even though these are not always optimal (my bots must lose 99% of the time when they take the X-Square Opening, for example).

CapellaBot

Othello is won by having more discs than your opponent at the end of the game. Most new players take this fact and turn it into a very naive, sub-optimal strategy. Playing greedily from the very beginning is often disastrous against more experienced players. This is the strategy employed by CapellaBot.

Interestingly enough, by playing from a more advanced opening book, CapellaBot is forced to take "bad" (by its own definition) moves during the beginnings of games.

VegaBot

Greedy players usually start to adapt their strategy after a few losses. They'll notice that their opponents usually capture the corners en route to victory. Corners are valuable due to their stable nature. Once taken, a corner can never be flipped. Further, a captured corner can lead to a captured (and stable!) edge. Indeed, capture enough corners and the rest, usually, falls into place.

So, VegaBot uses a strategy that assigns points to each square on the board. For example, corners might be valued at 50 points. C-Squares (adjacent to the corner, on the edge) and X-Squares (adjacent to the corner, on the diagonal) might be valued at -10 points because having a piece on those squares opens up the possibility of losing a corner.

This positional strategy is much better than the greedy strategy, but still has its faults. For starters, the value of each square is static, while the true value is more dynamic -- changing based on what other pieces are in neighboring squares. As an example, an X-Square might be a liability when the corner is empty, but an asset if you've already captured the corner. And yet, VegaBot will always avoid X-Squares, even if it might otherwise be considered the best move available.

A Quick Aside: Emergent Behavior in AI

When developing AI, it is very easy for a seemingly inconsequential decision to lead to unexpected behavior (for better or worse). When I initially developed, VegaBot, I used weights that looked like this:

[[50, -9, 0, 0, 0, 0, -9, 50], [-9, -9, 1, 1, 1, 1, -9, -9], [ 0, 1, 2, 4, 4, 2, 1, 0], [ 0, 1, 4, 5, 5, 4, 1, 0], [ 0, 1, 4, 5, 5, 4, 1, 0], [ 0, 1, 2, 4, 4, 2, 1, 0], [-9, -9, 1, 1, 1, 1, -9, -9], [50, -9, 0, 0, 0, 0, -9, 50]]

This set of weights was actually used in the first half of the game (when less than 30 moves have been played). My goal in assigning positive weights to the middle squares was to try to encourage VegaBot to keep to the middle of the board. And it worked -- a little too well. You see, the middle four squares are each assigned 5 points, which is alright. But what if VegaBot had all 4 middle squares? That'd be worth 20 points. That's much better. I'd inadvertently, told VegaBot to be greedy (at least with middle squares), which as we know is one of the worst Othello strategies.

So how do I fix the greediness, but still have VegaBot stay to the center squares? Like this:

[[50, -9, -6, -6, -6, -6, -9, 50], [-9, -9, -5, -5, -5, -5, -9, -9], [-6, -5, -4, -2, -2, -4, -5, -6], [-6, -5, -2, -1, -1, -2, -5, -6], [-6, -5, -2, -1, -1, -2, -5, -6], [-6, -5, -4, -2, -2, -4, -5, -6], [-9, -9, -5, -5, -5, -5, -9, -9], [50, -9, -6, -6, -6, -6, -9, 50]]

VegaBot now hates all squares (except those beautiful corners), he just hates the center squares a little less.

SiriusBot

So why is it bad to be greedy? The more discs you have, the more discs that could potentially be flipped, the more moves your opponent has. Having less discs, usually, leads to having more moves. The more moves you have, the more likely you are to have good moves. This is the concept of mobility. It's all about keeping your options open, while reducing your opponent to nothing but bad moves. It's how you get those corners when your opponent doesn't want to surrender them.

SiriusBot combines two strategies, the first of which is maximizing mobility. It's not as simple as just reducing discs, though, what SiriusBot really measures is the number of potential moves. In some situations, it's not bad to have more discs than your opponent, as long as you also have more moves.

Secondly, SiriusBot doesn't value squares like VegaBot does. Rather, it values configurations of the discs around the corners. So SiriusBot knows that having C-Squares and X-Squares is actually a good thing, if it already has the corner. This leads to much stronger play.

Summary

Here's how the bots do versus each other. This table is laid out with the win-loss record of the bot in row vs the bot in the column header. For example, SiriusBot had 19 wins against only 1 loss in 20 matches against CapellaBot.

In one of the games SiriusBot lost, it was wiped out by by CapellaBot before the game was even 20 moves old. That's what happens occasionally when one bot tries to minimize discs while the other tries to maximize discs. Most human players will recognize a greedy opponent and adjust their play to avoid such a fate. But these bots at least, are not capable of such flexibility.