Using NegaMax & Transposition Tables

This post follows on from the previous post which described negamax. In this post we will discuss how to actually call negamax search in a chess engine. Then we will look at one way to parallelise negamax. Towards the end we will briefly cover the concept of transposition tables which are a way to optimise our search. Sticking with our theme, we will use chess engine as the context for our discussion.

Calling NegaMax

NegaMax usage consists of two methods:

1. Root method
2. Actual negamax

When you call negamax, you only call the root negamax which then calls the actual negamax. Actual negamax is the negamax we saw in our previous post. Here’s what the resposibilities of root negamax are:
1. Generate a list of moves available to current player. Let’s say there are n possible moves.
2. Make each move to obtain a new board position. There will be n board positions.
3. Call actual negamax for each of the n board positions and for a specific depth.
4. Multiply the result of each actual negamax call by -1. This is because after making the move in step 2 above, actual negamax will compute scores from the point of view of the opponent. By multiplying by -1, we are reversing the point of view.
5. Find the maximum of the values in step 4 above. That will be the score and the move that resulted in that score will be the best move.

Following is the pseudocode for root negamax:

int root( int depth ) {
if ( depth == 0 ) return evaluate();
int max = -oo, score;
for ( all moves)  {
make move();
score = -1*negaMax(depth – 1);
if(score > max)
{
max = score;
}
}
return max;
}

Paralellised NegaMax

Here we will describe a simple way to paralellise negamax search. This is not necessarily the best way to do it. It is presented here to tie into our next topic which is lockless lookup tables.

Our version of parallel negamax simply takes the for loop in root negamax function and makes each iteration of the for loop to run in parallel. We store the results of each iteration in an array. Be careful to store result of each iteration in a separate array slot. An easy way to do this is to assign an array slot number, 0 to n-1, to each iteration. When that iteration is finished, it updates its own respective array slot. After that we iterate through the array in a separate loop and find the max score. There are different language constructs that allow you to do this but that depends upon which language you use.

A key thing to note here is that we are explicitly avoiding locks. Instead we have accepted the overhead of a linear search through the array for the maximum score but that turns out to be a small price compared the to the overhead of locking and the nuances of it.

Transposition Tables

Before going into transposition tables, let’s do a quick recap of what we have covered. So we have a game tree which a root at the top. Every node represents a board position and every branch represents a move. The root node represents current board position. So far so good. Now, in a real chess game, same board position can be reach more than one sequence of moves. Moreover, those sequences don’t have to have the same number of moves. What does that mean for our game tree? That means that our game tree isn’t really a tree in technical sense. The tree data structure is defined as the one in which there is only one route to go from current node to a destination node. In other words, there are no cycles in a tree. In our game tree, each node represents a board position. Since a same board position can be reached by different sequences of moves (i.e. routes), our game tree has cycles in it. Now this is actually a good thing and we can exploit the cyclic nature of our tree to speed up our search. The way to do it is by using a data structure called transposition table.

A transposition table is nothing more than a lookup table. It contains keys and values corresponding to they keys. In case of a chess search, they are called transposition tables. The key identifies a board position and value stores search results associated with that board position. Here’s how to use transposition tables to speed up negamax search. When we search a position, we get a score associated with that position and that score is dependent upon the depth that we searched that position to. We store the position as key and the score, best move and depth as value. Every time we search a position if we will check the transposition table first. If that position is already in the table, we don’t need to perform the full search and return with the results stored against that position. That saves us the whole search.