Evaluation

The evaluation function assigns a numerical score to a position from the perspective of the side to move. Positive scores are good for the side to move; negative scores are bad. This is the static assessment the engine uses when it stops searching - at a leaf node, the evaluation tells the search how promising the position is.

The evaluation here is extremely simple: material plus piece-square tables. No pawn structure, no king safety, no mobility. Simple evaluations are surprisingly competitive because the search tree compensates for a lot of what the evaluation misses - a deeper search with a simple eval often beats a shallow search with a complex eval. Both the material and PST tables values are taken from chess programming wiki - simple evaluation function.

Material values

The piece values used are in centipawns (hundredths of a pawn), a standard unit in chess programming:

Piece	Value (cp)
Pawn	100
Knight	320
Bishop	330
Rook	500
Queen	900
King	20,000

Note bishop (330) is valued slightly higher than knight (320). This reflects the general principle that bishops are slightly better than knights in open positions, though the difference is small. The king value (20,000) is chosen to be larger than any material gain the engine could calculate, ensuring the king is never traded.

Piece-square tables

Material alone tells the engine that a queen is worth a queen regardless of where it sits. Piece-square tables add positional nuance by assigning a bonus or penalty to each piece depending on which square it occupies. The bonus is added to the material value.

Piece-square tables encode human chess knowledge directly into the evaluation in the form of square bonuses. Rather than writing explicit rules ("knights should be in the centre", "rooks belong on open files"), you express the preference as a 64-entry table of bonuses and penalties.

All six tables are defined as compile-time constexpr arrays in eval.hpp, written from black's perspective (A8 at index 0, H1 at index 63). For black pieces the table is indexed directly. For white pieces, the square is XOR'd with 56, which flips the board vertically so rank 1 maps to rank 8 and vice versa - making the same table work symmetrically for both colors.

int Eval::evaluate(const Board& board){
    int white{0}, black{0};
    for (int p = PAWN; p <= KING; ++p){
        uint64_t w = board.pieces[WHITE][p];
        while (w){
            int sq = popLSB(w);
            white += PIECE_VALUES[p] + PST[p][sq ^ 56];
        }
        uint64_t b = board.pieces[BLACK][p];
        while (b){
            int sq = popLSB(b);
            black += PIECE_VALUES[p] + PST[p][sq];
        }
    }
    int score = white - black;
    return board.turn == WHITE ? score : -score;
}

The final score is returned relative to the side to move, not always from white's perspective. This is the convention that negamax requires - more on that in the search section.

Search: Negamax and Alpha-Beta

The search is the brain of the engine. Given a position, it looks ahead a fixed number of moves, evaluates the resulting positions, and works backwards to find the move that leads to the best outcome assuming both sides play optimally.

Minimax and the negamax formulation

The fundamental algorithm is minimax: at each node, the maximising player picks the move with the highest score, and the minimising player picks the move with the lowest score. White wants to maximise; black wants to minimise.

Negamax is an elegant reformulation: instead of tracking which side is maximising and which is minimising, every node maximises. The trick is that the score is always relative to the side to move, and when you recurse you negate the child's score. If a position is +300 for the side to move, it's -300 for the opponent. Recursing with -negamax(next, depth-1, ...) flips the perspective automatically.

Alpha-beta pruning

Plain negamax is exponential in the branching factor. A chess position has roughly 30 legal moves on average, so depth 6 means 30^6 = 729 million nodes. Alpha-beta pruning eliminates branches that cannot possibly affect the result.

The two parameters, alpha and beta, represent a window of scores that matter. Alpha is the best score the current player is already guaranteed to achieve from a parent node. Beta is the best score the opponent is already guaranteed - it's a ceiling, because if the current position scores above beta, the opponent would never allow it to be reached in the first place.

When a move scores above beta, we immediately stop searching this node. The opponent won't choose this line because they already have something better. This is the cutoff, and in well-ordered positions it severely reduces the effective branching factor.

int Search::negamax(const Board& board, int depth, int alpha, int beta){
    if (depth == 0) return Eval::evaluate(board);
    MoveGen gen(board);
    auto moves = gen.generateMoves();
    if (moves.empty()){
        if (board.inCheck(board.turn)) return -MATE_VAL - depth;
        return 0;
    }
    int bestScore = -INF;
    for(const Move& m : moves){
        Board next = board;
        next.makeMove(m);
        int score = -negamax(next, depth-1, -beta, -alpha);
        bestScore  = std::max(bestScore, score);
        alpha      = std::max(alpha, score);
        if (alpha >= beta) break;
    }
    return bestScore;
}

Mate scoring

Checkmate scores use -MATE_VAL - depth. The subtraction of depth is important: it makes a faster checkmate score higher than a slower one. Without it, the engine would be indifferent between mating in 1 and mating in 10, and might play aimlessly once it "knows" it's winning.

The mate value (900,000) is chosen to be larger than any material score the engine could compute, ensuring checkmate always dominates material considerations.

The root call

getBestMove handles the search root separately from the recursive negamax. The root needs to track not just the best score but the actual best move, so it maintains a bestMove variable updated whenever a child score exceeds the current best.

SearchResult Search::getBestMove(const Board& board, int depth){
    MoveGen gen(board);
    auto moves = gen.generateMoves();
    Move bestMove;
    int  bestScore{-INF};
    int  alpha = -INF, beta = INF;
    for(const auto& m : moves){
        Board next = board;
        next.makeMove(m);
        int score = -negamax(next, depth-1, -beta, -alpha);
        if (score > bestScore){ bestMove = m; bestScore = score; }
        alpha = std::max(alpha, score);
    }
    return {bestMove, bestScore, nodes};
}

Building a Chess Engine, Part 4