Authors:
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