Implementing Killer Heuristic in Alpha-Beta Search in Chess

Question

I understand the idea behind killer heuristic and why it helps. What I am struggling with is how to implement it in an Alpha-Beta search routine. In particular, how to ensure that only the killer moves of sibling nodes are tried first? Pseudo code will be of great help.

Answer 1

A killer move is likely to be a good refutation move at many parts of the search tree. So trying killer moves for other positions might be a good idea.

You may have different arrays of killer moves for each ply and clear the array for (ply+1) when entering (ply), this will give you a 'siblings-only' killers. I'd say that the '+1' offset is something like a parameter to tune: try clearing the array for (ply+N) instead and see where the performance is the best (I guess increasing N would improve things).

By the way, evaluation of engine's performance is a different rather resource-consuming task: usually an engine tries to solve a test suite, or two engines with different parameters are playing matches (the matches should be long enough, e.g. 100 games) between themselves to determine which is better.

Answer 2

I'll address the implementation. To get killer moves of sibling nodes, use a scheme like this

killerMoves[ply][slot]

where ply is the distance from root (not depth of search) and slot is the number of killer moves you want. This ensures that sibling nodes are tried first because sibling nodes are at the same ply.

To insert a killer move when you get a beta cutoff, you would shift the moves at the given ply to the right, possibly discarding an old move, and then insert the new move. Normally you don't store captures or hash moves as killer moves as they are ordered through other mechanisms.

for (int i = killerMoves[ply].Length - 2; i >= 0; i--) 
    killerMoves[ply][i + 1] = killerMoves[ply][i];
killerMoves[ply][0] = move;

Now when you are performing move ordering (before iterating through the move list), you can determine whether a move is a killer move:

for (int slot = 0; slot < killerMoves[ply].Length; slot++) {
    int killerMove = killerMoves[ply][slot];

    for (int i = 0; i < movesCount; i++)
        if (moves[i] == killerMove) {
            // moves[i] is a killer move so move it up the list
            break;
    }
}

You do not need to clear the killer moves for a ply or anything like that as it's quite possible that killer moves are good moves across a range of similar positions that arise at the same ply.

Since the other answer brought it up, you may not need to perform rigorous testing as the killer heuristic is theoretically sound. You can experiment with the number of killer moves you use (2 or 3 is the norm) and their ordering relative to other good moves such as captures.