Screen Capture from WZebra
(one of the best computer players out there)

Othello is a very simple board game where two opponents attempt to capture each other's pieces to get the more of their color at the end of the game. At the higher levels, this game can be as difficult as Chess. It makes for a great Artificial Intelligence problem for programmers to work on because the game has a definite midgame and endgame parts.

When I began working in C++ as a high school student, this was one of the first problems I tackled. My goal was to create an Othello player which was capable of beating me. In the end, my player was able to beat a random mover every time, and it even beat me a few times, but I could usually beat it if I was trying hard enough. This article will briefly go over my methods of madness for creating a semi-intelligent Othello player.

Minimax Search
The classic way of creating an intelligent board game player is to have the computer look ahead a certain number of moves and evaluate which move is better. Of course, we don't just want to take the best move for us, we want to assume that our opponent will choose the best move for them. So looking ahead involves taking the minimum of the maximum of moves.

Figure 1: An example of a minimax tree and it's solution.

Each node represents a possible board, and each child of a board is one possible move to take. Notice that the best possible move (15) is not the one taken because it's unlikely that the opponent would make a move to get there. The 8 is more likely to be chosen.

Evaluation Function
The numbers in the Figure 1 are values assigned to a board state measuring how good that state is. The evaluation function is key to making your player intelligent. Your function ought to be able to look at any board and tell you how good of state you are in the form of an integer. In Othello, the standard way of coding an evaluation function is to reward good position. A corner, for example, is a very good spot to have because it cannot be taken back. A spot next to a corner is not good, however, because your opponent can take the corner (that is, if you haven't taken it already!). This approach seems to work at the amateur levels, but from what I've read the best evaluation functions also try to force the opponent into making certain moves. This mobility approach has made computer players better than human players.

Figure 2 A table of weights associated
with each move (upper left corner shown,
symmetrical for other corners)
Diagram taken from OthelloMaster.com Opening Book and Endgame Solving
Two tools that my program never used but are standard practice in the Othello world are using opening books and endgame solving. Opening books are databases that have various opening strategies. This makes the computer player play differently every time because it's choosing its moves based on a pre-recorded sequence of moves. If you use WZebra, you'll notice that they have human-generated openings and computer-generated openings. In training sessions, the makers of the Zebra player have calculated sequences of moves by using the minimax approach. If your player can employ an opening book, it will give it more time to focus on the middle part of the game.

Engame solving is the other tool which is common in Othello programming. This is where the game is almost done and the program simply figures out the best possible way to play so it can win in the end. Both computers and humans tend to be good at this, so it's very important that an Othello player has a good endgame solver. The way this is done is essentially some modifications to the minimax search.

Retrospective Remarks
I have decided to only give a brief overview of my work in Othello because it was my first project. It's probably the most lines of code that I've ever written on one project before junior year of college (over 1500 lines of C++ code). It's also some of the most inefficient, buggy code I've written. It was my first attempt at something big and useful and, since I got a few working compilations that played decently well, I guess I can call it a success. I code with much more brevity now, though. I would not put my player up against any of the greats out there, but I learned an enormous amount about code and AI through this project. Maybe someday I will rewrite the code in Java and put it on the website, but that's a long way away!

Page last updated: February 04, 2008