Here I describe an excellent heuristic/evaluation function for Reversi (trademark name Othello) and provide its C++ implementation.

This heuristic function is actually a collection of several heuristics and calculates the utility value of a board position by assigning different weights to those heuristics. These heuristics take into account the mobility, coin parity, stability and corners-captured aspects of a board configuration. Each heuristic scales its return value from -100 to 100. These values are weighed appropriately to play an optimal game. The various heuristics include:

**1. Coin Parity**

This component of the utility function captures the difference in coins between the max player and the min player. The return value is determined as follows :

Coin Parity Heuristic Value = 100 * (Max Player Coins - Min Player Coins ) / (Max Player Coins + Min Player Coins)

**2. Mobility**

It attempts to capture the relative difference between the number of possible moves for the max and the min players, with the intent of restricting the opponent’s mobility and increasing one’s own mobility. This value is calculated as follows :

if ( Max Player Moves + Min Player Moves != 0) Mobility Heuristic Value = 100 * (Max Player Moves - Min Player Moves) / (Max Player Moves + Min Player Moves) else Mobility Heuristic Value = 0

**3. Corners Captured**

Corners hold special importance because once captured, they cannot be flanked by the opponent. They also allow a player to build coins around them and provide stability to the player’s coins. This value is captured as follows :

if ( Max Player Corners + Min Player Corners != 0) Corner Heuristic Value = 100 * (Max Player Corners - Min Player Corners) / (Max Player Corners + Min Player Corners) else Corner Heuristic Value = 0

**4. Stability**

The stability measure of a coin is a quantitative representation of how vulnerable it is to being flanked. Coins can be classified as belonging to one of three categories: (i) stable, (ii) semi-stable and (iii) unstable.

Stable coins are coins which cannot be flanked at any point of time in the game from the given state. Unstable coins are those that could be flanked in the very next move. Semi-stable coins are those that could potentially be flanked at some point in the future, but they do not face the danger of being flanked immediately in the next move. Corners are always stable in nature, and by building upon corners, more coins become stable in the region.

Weights are associated to each of the three categories, and summed to give rise to a final stability value for the player. Typical weights could be 1 for stable coins, -1 for unstable coins and 0 for semi-stable coins.

The stability value is calculated as follows :

if ( Max Player Stability Value + Min Player Stability Value != 0) Stability Heuristic Value = 100 * (Max Player Stability Value - Min Player Stability Value) / (Max Player Stability Value + Min Player Stability Value) else Stability Heuristic Value = 0

Take a look at the C++ implementation.

Reference : An Analysis of Heuristics in Othello

I just have a quick question for the C++ implementation. How did you find the appropriate weights for the final score equation

I did not. Those researchers from University of Washington, who wrote the paper I reference at the end of the post, found them.

I read your C++ implement and i can’t find where X1, and Y1 in this part “x = i + X1[k] and y = j + Y1[k]”. Can you explain it?

I’m extremely sorry I didn’t include their definition in the code. They were defined outside the heuristic function.

int X1[] = {-1, -1, 0, 1, 1, 1, 0, -1};

int Y1[] = {0, 1, 1, 1, 0, -1, -1, -1};

They are used to find the indices of the eight neighboring cells of a given cell. By cycling through their values and adding them to the indices of a given cell, we can obtain the indices of the 8 neighbors.

I’ll include it in the code as soon as pastebin comes up. Apparently it’s under heavy load right now.

Hi, I have reviewed your code and it is not clear to me whether and how you deal with coin stability. What approach did you take? Simon

Hi, I noticed that definition of matrix V was missing in the code I had pasted. In my original code, it was defined elsewhere. I have updated the code snippet to include it.

The calculations with V values (referred to in the code as d) and frontier disks (my_front_tiles and opp_front_tiles) serve as proxy for stability values. A tile is a front tile if it is adjacent to an empty square and so can potentially be flipped. I made a tradeoff between accuracy and computation time. Calculating coin stability accurately might have been too expensive.

The code I presented is not the only way (certainly not the best way) to implement the heuristics described. It’s only my interpretation and what felt right at that time.

Many thanks Kartik! This is very helpfu.l I am struggling with a computationally ‘cheap’ way of dealing with coin stability: one way might be to focus on edge stability. I am not sure that the proxies you use are measures of coin stability. Frontier discs, for example, are usually a measure of potential mobility rather than stability. And the V table you use is akin to a static heuristic discussed in the useful article you attached. Simon

Pingback: Alpha Beta Search | Everything Under The Sun