For Veritas Open Software Contest, TechFest 2001

Indian Institute of Technology, Bombay

 

Gothello

The Expert Othello Playing Program

 

 

 

 

 

 

Authors:

Gaurang Khetan

Milind Bandekar

 

 

                                  

           
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