Writing an Othello program

Prerequisites / Searching / Position evaluation / Opening knowledge / Endgame / Some source code / Other resources


In order to put together an Othello program of moderate strength, some programming experience is necessary. Most of the algorithms and data structures used can be found in textbooks on artificial intelligence, textbooks on algorithms and on the web. A good high school student or undergraduate student of computer science should be able to grasp the algorithms well enough to create a strong program.

Some of the more advanced techniques referred to below require some familiarity with optimization theory and linear regression; this material is on the level of undergraduate courses in applied mathematics.

The real difficulty with creating a strong Othello program is the debugging. Due to the nature of the search algorithms, bugs can lurk for quite a long time before surfacing (taking the programmer by surprise). The only advice I have here is to test all new modules thoroughly.


Position evaluation

This is by far the most important part of the program, if this module is weak it matters little if the program has great search algorithms. I will describe three different paradigms for creating evaluation functions. They describe the evolution of Zebra's knowledge and I believe that most Othello programs can be placed in one of these categories.

Opening knowledge

All strong programs use opening books and update their books automatically after each game. Most of the top programs have opening books which to some extent are based on IOS/GGS games, so the books have a large overlap. What differs is how the information from the games is used. An approach, used by all top programs, is to go through all positions from all games in the game database and determine the best move not played in any database game. This is time-consuming as a deep search must be performed for each position, but once this is done, updating the book on the fly is easy - after each game played, all new positions (and maybe some old) are searched for the best deviation. Using the resulting set of positions and moves (both deviations and moves actually played) the best book lines for both sides can be determined using a simple minimax search.

Some other programs don't store deviations from each position but instead calculate deviations on the fly. The main advantage of this approach is that there is no need to calculate the deviations (which is very time-consuming). There are several drawbacks though; this kind of opening book is much more vulnerable to weak moves in the game database which can lead to dead lost positions straight out of book.


As the number of moves available to each player decreases towards the end of the game, the programs can search much deeper in the endgame phase of the game. This enables them to play the endgame much better than any human; watching computers play the endgame often feels quite weird as both opponents know the outcome of the game with more than 20 moves left! For computer programs, the endgame starts in what most humans would refer to the late midgame; with 20-30 moves left of the game.

The search algorithms used in the midgame work well in the endgame as well (including a variation of MPC). The objective changes though: For a program, the endgame starts when it can calculate who is winning, i.e., follow all variations until no player has any move left. This is usually with 24-30 moves left for the top programs. When the program knows who is winning, it starts to optimize the score (win by as much as possible). This usually is much harder than determining who is winning (unless the position is a draw) and can usually be accomplished with 23-28 moves left.

Good endgame performance is all about move ordering, and it pays off to use move ordering heuristics different from those used in the midgame. The reason is as follows: Most lines analyzed contain one or more blunders, and it when finding a refutation of a bad move it suffices to find any refutation, not necessarily the best refutation. As we want the program to solve a position as fast as possible, it makes sense to look for the fastest refutation (measured in thinking time). This is accomplished by searching moves after which the opponent has low mobility earlier than they would be searched in the midgame. This is commonly referred to as the Fastest-First heuristic.

Some source code

Basic endgame solver

When I started working on computer Othello I downloaded an endgame solver created by Warren Smith and later improved by Jean-Christophe Weill. I then improved it myself, the resulting solver is found here. A more sophisticated endgame solver written by Richard Delorme can be found here.

Bitboard trickery

Zebra's endgame solver is very fast, maybe the fastest around. One reason for this is that it represents the Othello board as four 32-bit words, two words for the black discs and two words for the white discs. Using this representation it is possible to write a very fast move generation functions. The fastest-first heuristics used for move ordering benefits from this as well, here you find a C+assembly function that computes the number of legal moves for one player in less than 200 clock cycles on an AMD Athlon - I have not timed it on other platforms, on a Pentium III I expect the cycle count to be roughly the same, whereas on a Pentium IV my guess is that it needs 300-400 cycles.

The code is used as follows: Call init_mmx() to initialize some constants (you only have to call this function once), then use bitboard_mobility() to get the mobility. The code can be compiled as C code using GCC's asm extension. It is straightforward but boring to convert it into code that can be compiled using Microsoft Visual C++.

The main trick used by the code is to find all moves that flip discs in a certain direction, e.g. up, in parallel. This can be done in several different ways, this code uses a variation first suggested by Richard Delorme which I have improved somewhat. There are 8 possible flip directions, 6 of these are managed by the MMX ALUs and the remaining 2 by the integer ALUs.

Currently the code averages about 2 instructions per clock cycle on an AMD Athlon - 400 instructions in 200 cycles. Using the processor optimally it should be possible to execute 3 instructions per clock cycle. For this application it may be impossible to attain the theoretical optimum, but it almost certainly is possible to improve on my code by considering pairing and register stalls throughout - I am a novice assembly programmer and have probably introduced lots of unnecessary stalls. It is possible to make it slightly faster by using the psadbw instruction which is available on Pentium III, Pentium IV, and Athlon.

Since I wrote the above texts, Toshihiko Okuhara has contributed even faster bitboard code. Download the Zebra source code if you are interested in it.

Other resources

Annotated bibliography of Othello programming.
Contains references to research papers in this area. Almost all the material covered on this page can be found in the papers listed.
Machine learning in games
Jay Scott maintains this large web site covering all aspects of game programming. Contains many different games, not only board games but also robotic soccer and adventure game AI. Many techniques are reviewed and there are links to other resources on the Internet. Very good site.
Michael Buro's publications
Here the breakthrough papers by Michael Buro can be downloaded. If you want to create a strong Othello program, reading these papers is strongly recommended.

Last modified April 2, 2007 by Gunnar Andersson