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

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.