Authors:

Gothello – The Expert Othello Playing Program

The project associated with
this writing, which we call Gothello, is an attempt to make a computer play the
game of Othello at a very high skill level.

The game of Othello is a descendant of an old Japanese
board game. It is similar to chess in that it is a deterministic, perfect
information and a zero-sum game of strategy between two players on an 8 x 8
board. The complexity of this game, which causes any attempt to find an *exact* solution on today's computers to
fail miserably, along with the
simplicity of the rules make this game one of most attractive domains
when studying and implementing game playing computer programs based on game
tree search. It is intricate enough as to warrant a good amount of
thought to produce a strong Othello program.

The effort presented here is based on the latest
advanced techniques that have been invented in recent times for producing
tournament level Othello game play. It has been developed on the knowledge base
that includes many techniques that are used by “**Logistello**”, one of the strongest Othello playing computer programs
ever made, and other world-class programs of similar stature. We have adapted
and modified these techniques to make them suitable for the scale of this
implementation and the required complexity, while adding some innovative tricks
on our own.

The resulting program Gothello has *never even come close* to a defeat by the
numerous human opponents it has played so far, including the authors. It has
beaten several other computer programs that play Othello including a few
available on the Internet.

The algorithm behind the working of the program
can be divided into six key areas:

1. Position Evaluation

2. Search

3. Opening Book

4. Move Ordering

5. Transposition Table

6. Endgame-customized Search and Evaluation.

**Position
Evaluation**: The heart of any
game-playing program is the position evaluation function. A strong evaluation
function is necessary for producing strong gameplay. This program evaluates a
position by using a mathematical evaluation function, which is a weighted sum
of the numerical values representing different features that are considered
characteristics of a winning position. The features used are some important
patterns considered locally, mobility (a measure of the number of moves
playable), potential mobility (a measure of the number of frontier disks), edge
configurations and parity. The important patterns that are considered here are
every possible configuration of horizontal and vertical rows, of the 4-8 length
diagonal, 3X3 corners and 2X5 corners. The weights associated with the patterns
have been found out by an analysis of thousands of games played between expert
players. The weights of the rest of the features are found out using a
technique called value adaptation. This routine has been optimized for speed
since the time required by this routine is critical to the final speed of play
generated by the program.

**Search**:
All strong Othello programs of today determine the best move in a position by
searching many moves ahead. They assume best responses from both sides
throughout the search. The move chosen is the one that produces the best
resulting position after a deep search. This is called the MiniMax
search algorithm. The best position is decided by operating the Evaluation
Function discussed above at the positions on the leaves of the tree built by
the search. However, the number of possible positions arising even after only a
few moves grows very fast; in most mid-game positions, each player have about
ten moves each, so to search to depth 8 results in 100000000 positions to
investigate. To counter that, a procedure called Alpha-Beta Pruning is used
which greatly reduces the number of positions that need to be examined.
However, deeper searches are performed using one selective search technique
called the Probability Cut (ProbCut); this enables it to identify bad moves
that do not deserve deeper search, by performing a shallower initial search.

**Opening Book**: The strength of a computer player weakens substantially in the
opening phase since this phase requires a very good understanding of strategy
which practically only human players can achieve. To temper this, we
implemented a feature called opening book. The Opening Book contains previously
calculated best moves for particular positions. Since this is done beforehand,
deeper searches can be afforded to find the best move possible in the positions
that are found in the training database.

**Move Ordering**:** **In Alpha Beta pruning
procedure, to produce the best optimization for speed, move ordering plays an
important role. Move Ordering is concerned with the order in which moves are
considered and evaluated during the search. Alpha Beta pruning gives best
results when the moves evaluated are in the order of decreasing value from the
best to the worst. For this, a killer response has been stored for each move
that is to be considered first in the search. Apart from this, for better
performance, a shallow search is performed initially say of the depth of 2; which
can be used to find the estimated merits of the moves.

**Transposition Table**:** **Certain positions are
often repeated after different multiple move sequences are followed. A repeated
evaluation of the same position must be avoided for increased efficiency. For
this, each position that has been evaluated, along with the assessment and the
best move found, is stored in a so-called Transposition Table.

**Endgame-customized Search and Evaluation**:** **During the endgame, the number of available moves becomes less for
both the players. It is possible to search until the game ends, so even
evaluation of any position is not needed. These factors give rise to a
situation that is favourable for an endgame-customized implementation of a
search that can go a lot more deeper and can find the
result of the game many moves before the end.

All these features have made
Gothello highly complex; yet at the same time we maintained a very simple user
interface, well defined modularity in the thousands of lines of VC++ program
code and the necessary speed of play.

Gothello has indeed turned
out to be quite a strong Othello player.

--- Gaurang Khetan,
Milind Bandekar

§Value adapatab