Position evaluation

What creates the personality of an Othello program is the knowledge is possesses. This is by far the most important part of Zebra; having sophisticated search algorithms does not help much if the program does not understand the positions it encounters.

Strong human players strive to maximize mobility and minimize the number of frontier disks in the midgame. Edge and corner configurations are taken into consideration too. How can these measures be coded in a program? The most successful approach, and the one employed in Zebra, is to break down the position into many local configurations. Zebra has a value associated with each configuration of each row, column, diagonal of length 4-8, 3x3 corner (e.g. a1,a2,a3,b1,b2,b3,c1,c2,c3), 5x2 corner (e.g. a1,a2,b1,b2,c1,c2,d1,d2,e1,e2) and edge+adjacent X-squares (e.g. a1,a2,a3,a4,a5,a6,a7,a8,b2,b7). To evaluate the merits of a position, the 46 values corresponding to the board configurations listed above are summed up. If the player to move has parity, a bonus for this is added too. The resulting value is an estimate of the final disk difference in the game.

The set of patterns used in the evaluation function is what defines the knowledge of the program. Choosing good patterns therefore is very important. Another aspect is that of speed; complicated patterns slow down the program. The patterns used in Zebra can be calculated very quickly and are still powerful enough to give a solid understanding of the positional aspects of the game.

The main problem now is the following: There are lots of different local patterns which need values associated with them - there are 3321 different edge configurations alone, and when all the configurations are counted, there are tens of thousands. To make bad things worse, the relative values of the different configurations are highly game-stage dependent. Clearly, the process of determining values for all configurations must be done automatically. This is done by taking a large database of games played between strong players and calculating statistics for each configuration in each game stage from all the games. Zebra spent about a week analyzing 100'000 games in order to determine suitable values for about 1'000'000 different board patterns.