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

• alpha beta pruning
• a variation of multi prob cut
• a simple quiet scene search
• an implementation of a hash table to store the best moves in a position

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:

• mobility, i.e. the number of legal moves in the actual position
• potential mobility, i.e. a measure of the size of the frontier and centralization ("innerness") of the discs
• parity in the corners
• parity regarding the number of remaining moves
• access to the quadrants of the board
• some 150 other features of the position, e.g. value of a corner, special edge configurations, number of discs, etc.
• 58 regions defining local evaluations: 16 rows and lines, 22 diagonals, eight 4x2 corners, four 4x2 edge-regions (e.g. a3 to b6), four non-connected regions (e.g. g1, h1, h2, h3, h6, h7, h8, g8) and finally four 3x3 corners
• 13 stages of the game (4 empties up to 52 empties) with individual evaluations

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