The structure of Herkules
Of course the basic principles for searching in the game tree are the same for Othello and other board games. Compared with chess or go it is easier programming computers to play Othello. This is because the moves on the board often change the situation dramatically, which makes Othello hard to calculate for human players. On the other hand it is possible for a computer to precalculate the value of a lot of patterns occuring during the game on a row, a line, a diagonal or other regions of the board and use this for a quick and not so bad evaluation of a position.
The search algorithm
Naturally the search algorithm of Herkules is based on the classical minimax algorithm tuned by
These and the following terms are explained in the standard literature available on the Web, for a good compilation of references see Robert Gatliff.
The evaluation function
The main evaluation function used by the search algorithm uses the following concepts:
This function is completely table based, i.e. all of the possible patterns in each region are evaluated and stored in the initializition phase of the program. The coefficients on which the evaluations are based, were optimized by selfplaying some ten thousend of games.
For the endgame a tuned version of the algorithm is used to speed up the calculation. Unfortunately this is not so fast as the algorithm implemented by most of the other programs.
Back to main page