Creating a Chess AI Part 2: Searching

NegaMax

At the center of every chess engine is a search algorithm. This is the bit that actually looks ahead at future positions and decides which move is the best.

One of the simplest, and most commonly used algorithms for this is NegaMax. This is just a cleaner way of writing MiniMax, which you may have already heard of.

What is NegaMax?

NegaMax is a varient of MiniMax. Instead of using a min player and a max player, it just flips the score for the opposing player using a negative sign.

We always assume the current player is trying to get the highest possible score, and just nagate everything from the opponents perspective.

You will likely see code like this everywhere when looking at this topic.

int eval = -Search(depth - 1, -beta, -alpha);

The Flow

1. Generate all legal moves

2. Try each move

3. Recursively search deeper

4. Undo the move

5. Pick the best result

Alpha-Beta Pruning

Without any optimisations, the search will grow exponentially. Alpha-Beta pruning fixes this.

We keep two values:

• Alpha - the best score we can guarantee

• Beta - Worst score the opponent will allow

If we find a move that is too good for the opponent, we just stop searching it.

Alpha Beta pruning when implemented correctly, will never change what move is picked at the end, it just makes us arrive at that move faster by never looking at moves that are mathmatically impossible to be the best option.

The Search Function

This is the main negamax recursive function used.

private int Search(int depth, int alpha, int beta)
{
    if (depth == 0)
        return Evaluate();

    List<Move> moves = GenerateLegalMoves();

    //no moves = checkmate or stalemate
    if (moves.Count == 0)
    {
        if (IsInCheck())
            return -CHECKMATE;
        return 0;
    }

    //improve pruning efficiency by ordering moves
    OrderMoves(moves);

    int bestScore = int.MinValue;

    //try all moves
    foreach (Move move in moves)
    {
        MakeMove(move);

        //negamax recursion
        int score = -Search(depth - 1, -beta, -alpha);

        UndoMove();

        //track best score
        if (score > bestScore)
            bestScore = score;

        //alpha-beta pruning
        if (score >= beta)
            return beta;

        if (score > alpha)
            alpha = score;
    }

    return alpha;
}

Move Ordering

Not all moves are equal.

Good move ordering will mean that:

• Good moves are searched first.

• Bad moves are searched last.

A common question here may be "Why waste computation on this?" The answer is that move ordering greatly benefits alpha-beta pruning to where the benefit greatly outweighs any time spent on actually ordering the move. It just makes our search faster.

The next post will be on this, so I wont go into any more detail on this here.

Checkmates and Stalemates

When no more moves are available:

• If the position is in check - Checkmate (bad for the side to move)

• If not in check - stalemate (draw)

We also add a small distance factor so faster checkmates are prefered=

int dist = (_searchDepth - depth);
return -CHECKMATESCORE + dist;

This makes the engine prefer faster wins and to delay losses.

Conclusion

NegaMax is the foundation of a chess AI. Many things can be built on top of it including

• Alpha-Beta Pruning

• Move Ordering

• Quiescence Search

Together, these turn a basic search into something powerful enough to have some impressive performances.