Search

A basic chess engine finds the best move in a position by recursively looking at all the moves possible in a position until it hits a terminal node, i.e. a position that is a win, loss or draw. For an ideal chess engine, we can give each of those cases an evaluation of 1, 0, and -1 and backpropagate to find the evaluation of non-terminal nodes. In any position, we can assume that the side to move will play the best possible move for itself. Thus in nodes where all the children are terminal nodes, we can use the score of the move with the best evaluation for the side to move as that node's score. This way, we can backpropagate to find the scores of all nodes.

In the ideal case, every leaf node of an engine’s search tree would be a terminal node, corresponding to a win, loss, or draw. The Shannon number, 10^120, is a conservative bound on the necessary size of the search tree from the start of the game needed in order to have all leaf nodes be terminal. This number far exceeds the number of atoms in the universe. Thus, the majority of nodes in the search tree are not terminal and must be handled via a static evaluation function. This function converts the board to an integer value, where a positive value indicates an advantage for the side to move. Thus after looking at all the moves a certain distance away from the root position, we can give all the non-terminal nodes their static evaluation as their score. Note in this case the mate score must be very large, so as to not confuse it with a static score.

Negamax Search

This basic type of search can be implemented using the Negamax algorithm. Since one side's advantage is the other side's disadvantage, we can simply negate the score from the child's move to get its score from the opposite perspective.

func (position *Position) Negamax(depth, plys int, pv *[]move.Move) eval.Eval {
    switch {
    // terminal node checks
    case position.IsMate():
        // player got mated so a negative score
        // adding plys from root gives longer
        // mates better scores
        return -eval.Mate + plays

    case position.IsDraw():
        return eval.Draw

    // depth limit reached: return static eval
    case depth <= 0:
        return position.StaticEval()
    }

    // variables to keep track of
    // the best move and its score
    bestMove := move.Null
    bestEval := -eval.Inf

    moves := position.GenerateMoves()

    // move search loop
    for _, move := range moves {
        var childPV []move.Move

        position.MakeMove(move)
        // recursively do a negamax search with
        // a shorter depth. The score is negated
        // to change its perspective from the
        // opponent to the side to move
        score := -position.Negamax(depth-1, plys+1, &childPV)
        position.UnmakeMove()

        if score > bestEval {
            // better move found
            bestMove = move
            bestEval = score

            // update pv
            *pv = append([]move.Move{bestMove}, childPV...)
        }
    }
    return bestMove, bestScore
}

This is the basic search algorithm used by most modern alpha-beta chess engines, including all of the top-level engines. This algorithm is however very basic and can be extensively improved upon with various pruning techniques.

Alpha-Beta Pruning

The Alpha-Beta Pruning is a significant enhancement to the Negamax search algorithm that eliminates the need to search large portions of the search tree by applying a branch and bound technique. Remarkably, it does this without any potential of overlooking a better move. If one already has found a quite good move and searched for alternatives, one refutation is enough to avoid it. No need to look for even stronger refutations. The algorithm maintains two values, alpha and beta. They represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively.

If while searching a node, a best move is found which is better than beta(the maximum score of the minimizing player), we know that the minimizing player will tend to avoid it, given that they have a sequence which will lead to a better position for them. Therefore we can safely prune any remaining moves in that node. This is known as a beta cutoff or failing high.

Note that the same technique cannot be applied to perform alpha cutoffs since the maximizing player is the one making the move and even if a move is worse than alpha, they can just not play it. On the other hand, for beta cutoffs, the minimizing player can't control the moves and thus has to avoid that position.

Adding Alpha-Beta pruning in our Negamax can be achieved simply:

func (position *Position) Negamax(depth, plys int, alpha, beta eval.Eval, pv *[]move.Move) move.Move {

// ...snip...

// maximizing player becomes minimising player and
// minimizing player becomes maximizing player
// so alpha = beta and beta = alpha, which are negated
// since the perspective is changing
score := -position.Negamax(depth-1, plys+1, -beta, -alpha, &childPV)

// ...snip...

if score > bestEval {
    // better move found
    bestMove = move
    bestEval = score

    // try to update bounds
    if score > alpha {
        alpha = score

        // update pv
        *pv = append([]move.Move{bestMove}, childPV...)

        if score >= beta {
            break // beta cutoff
        }
    }
}

// ...snip...

The root call to an Alpha-Beta Negamax Search should be:

position.Negamax(
    depth, // search depth
    0, // 0 plys from root since this is root
    -eval.Inf, eval.Inf, // assume the worst for max player
    &pv, // principal variation variable
)