Agata

One day I lost a game of chess against Stockfish in 11 moves. Eleven. Instead of accepting it and moving on with my life, I decided to build MY OWN Stockfish, and I called it "Agata".

Agata now has an estimated ELO of around 2400. Not to brag, but only 1 in 400,000 people reading this blog would be able to beat her. So let's look at how I did it.

Note for non-technical readers: since this isn't exactly mainstream stuff, I chose to be fairly technical in describing the project. Sorry about that.

Representing the board

First things first: how do you keep a chessboard in memory?

The obvious answer is a 64-element array where each cell is a number indicating which piece sits there. 0 for empty, 1 for white pawn, 2 for white knight, and so on. It works, but for a chess engine it is far too slow, and the reason becomes clear as soon as you understand what kind of operations you actually need.

An engine analyses millions of positions per second. For each one it has to answer questions like: "is the white king in check?" — which requires finding where all the enemy pieces are and computing whether any of them attacks the king's square. With an array you have to scan all 64 elements, filter the opponent's pieces, and compute their attacks. With 35 possible moves per position and searches at depth 10+, every nanosecond counts.

The solution used by every serious engine is bitboards.

The idea exploits the fact that a chessboard has exactly 64 squares — and a 64-bit integer has exactly 64 bits. If you assign one bit to each square, you get a perfect representation: the bit is 1 if the square is "active", 0 otherwise.

typedef unsigned long long U64;
 
U64 bitboards[12];   // P, N, B, R, Q, K, p, n, b, r, q, k
U64 occupancies[3];  // [white, black, both]

Agata keeps 12 separate bitboards, one for each piece type (6 white + 6 black). bitboards[0] is the white pawn bitboard: it has a 1 on every square holding a white pawn and 0 everywhere else. Plus three "occupancy" bitboards tracking which squares are occupied by white pieces, black pieces, or any piece at all.

The square mapping is this: bit 0 is a8 (top-left corner), bit 7 is h8, bit 56 is a1, bit 63 is h1. In binary, a white pawn on e2 is simply bit number 52 set.

The key advantage: board operations become bitwise operations on 64-bit integers, which the CPU executes in a single clock cycle. Want to know whether the fourth rank is completely empty? A single & with a mask. Want to find every square attacked by the white pawns? A single 8-bit left shift (equivalent to "advance one rank").

#define setSquare(bitboard, square)   ((bitboard) |=  (1ULL << (square)))
#define getSquare(bitboard, square)   ((bitboard) &   (1ULL << (square)))
#define popSquare(bitboard, square)   ((bitboard) &= ~(1ULL << (square)))

Two operations come up constantly: counting bits (how many pieces of a given type are there?) and extracting the least significant bit (finding the first occupied square in order to iterate over pieces).

For counting I use __popcnt64(), a hardware instruction available on any modern x86 CPU that counts the set bits in a 64-bit integer in a single cycle — literally a single POPCNT assembly instruction. For extracting the least significant bit, an algebraic trick:

int count_bits(U64 bitboard) {
    return __popcnt64(bitboard);
}
 
int get_lsb_index(U64 bitboard) {
    // bitboard & -bitboard isolates the least significant bit
    // subtracting 1 turns every bit below it into 1
    // counting those bits gives the index
    return count_bits((bitboard & -bitboard) - 1);
}

The pattern for iterating over all pieces of a type then becomes:

U64 bb = bitboards[P]; // white pawns
while (bb) {
    int square = get_lsb_index(bb); // find the square of the next pawn
    // ... process the square ...
    popSquare(bb, square);          // clear that bit and move on
}

Encoding moves

A chess move carries a lot of information: where it starts, where it lands, which piece moves, whether it captures something, whether it is a promotion (and into what), whether it is en passant, whether it is castling. A naive approach would be a struct with all these fields — but move lists get copied, sorted and passed around constantly, and large objects put pressure on the cache.

The solution is to pack everything into a single 32-bit integer:

bits  0- 5  →  source square       (6 bits, values 0-63)
bits  6-11  →  target square       (6 bits, values 0-63)
bits 12-15  →  piece type          (4 bits, values 0-11)
bits 16-19  →  promotion piece     (4 bits, values 0-11)
bit  20     →  capture flag
bit  21     →  double pawn push flag
bit  22     →  en passant flag
bit  23     →  castling flag

For example, e2e4 — the classic central pawn push — is encoded as: source = square 52 (e2), target = square 36 (e4), piece = white pawn (0), no promotion, no capture, double-push flag = 1. All in a single int.

The accessor macros use masks and shifts:

#define get_move_source(move)    ((move) & 0x3f)
#define get_move_target(move)    (((move) >> 6) & 0x3f)
#define get_move_piece(move)     (((move) >> 12) & 0xf)
#define get_move_promoted(move)  (((move) >> 16) & 0xf)
#define get_move_capture(move)   ((move) & 0x100000)

The move list is simply a fixed-size array. 256 elements is always plenty: the theoretical maximum number of legal moves in any chess position is 218 (a particularly chaotic position with many promotions), and in the vast majority of cases it's 30-40.

typedef struct {
    int moves[256];
    int count;
} moves;

Attack tables and magic bitboards

To compute legal moves, the central problem is determining which squares each piece attacks from its position.

For non-sliding pieces (pawns, knights, kings) it's easy: the attacked squares depend only on the starting square, regardless of the other pieces on the board. You precompute them at startup and put them in a table:

U64 pawn_attacks[2][64];   // [colour][square]
U64 knight_attacks[64];
U64 king_attacks[64];

White pawn attacks are computed with shifts and file masks. A pawn on e4 (bit 36) attacks d5 (bit 27) and f5 (bit 29), i.e. bits 36-9 and 36-7. The file masks avoid a subtle bug: without them a pawn on h4 would appear to attack a5 (because the shift "wraps" around the edge of the board, the bit slides from the last column to the first):

attacks |= (bitboard >> 7) & not_a_file;  // capture to the right
attacks |= (bitboard >> 9) & not_h_file;  // capture to the left

For bishops, rooks and queens the problem is fundamentally different. These pieces slide along files, ranks and diagonals, and they stop when they hit another piece. A rook on a1 with the a file clear attacks a2, a3, ..., a8. But if there's a pawn on a4, it stops there (or on a4 itself if it captures it). The attacked squares depend not only on the rook's position but on where all the other pieces are.

The brute-force solution would be: for each rook position, walk along the 4 rays (up, down, left, right) until you hit the edge or a blocker. It works, but inside a search loop calling this function tens of millions of times, it is far too slow.

Magic bitboards

The idea is to precompute every possible attack configuration and index them with a perfect hash function.

Step one: the blocker mask. For each square, identify the squares that can actually block the piece. For a rook on e4 these are the interior squares of the e file and the 4th rank — the edges are excluded because the rook always reaches them anyway (they can't block, at most they stop the slide on the edge itself).

The mask for a rook on e4 has roughly 10-12 bits set. That means there are 2^10 = 1024 or 2^12 = 4096 possible arrangements of blocking pieces on those squares.

Step two: finding the magic number. For each square you look for a 64-bit constant — the "magic number" — such that this formula:

index = (occupancy & mask) * magic >> (64 - relevant_bits)

maps every blocker configuration to a unique index in a compact table. The multiplication + shift acts as a hash function: it mixes the bits of the occupancy so as to compress them into a small index with no collisions.

Magic numbers are found by random search: you generate random constants until one works (no collisions for any of the 4096 configurations). There is no analytic formula — they are simply lucky numbers. The ones found for Agata:

const U64 rook_magic_numbers[64] = {
    0x8a80104000800020ULL,
    0x140002000100040ULL,
    // ... 62 more
};

Step three: filling the tables. At startup, for every square and every blocker configuration, you compute the real attack bitboard (with the slow method, which is fine since you only do it once) and store it in the table indexed by the magic:

U64 rook_attacks[64][4096];   // ~2MB
U64 bishop_attacks[64][512];  // ~256KB

At runtime, finding the squares attacked by a rook becomes a single operation:

U64 get_rook_attacks(int square, U64 occupancy) {
    occupancy &= rook_masks[square];           // keep only the relevant blockers
    occupancy *= rook_magic_numbers[square];   // "mix" the bits
    occupancy >>= 64 - rook_relevant_bits[square]; // compress into the index
    return rook_attacks[square][occupancy];    // O(1) lookup
}

Three operations instead of a loop walking the rays. The queen is simply the union of bishop and rook attacks:

U64 get_queen_attacks(int square, U64 occupancy) {
    return get_bishop_attacks(square, occupancy)
         | get_rook_attacks(square, occupancy);
}

The memory cost is about 800KB — an absolutely worthwhile trade, given that it lets you generate sliding-piece moves as fast as knight moves.

Move generation

With the tables ready, generate_moves() produces every possible move for the side to move. An important clarification: it generates pseudo-legal moves, i.e. geometrically valid ones that might leave the king in check. Full legality is verified afterwards, in make_move().

Why not generate only legal moves directly? Because checking legality requires making the move and seeing whether the king is in check — an expensive operation. It is more efficient to generate everything and discard the illegal ones during the search, where many moves get pruned before they are ever explored.

Castling is the trickiest special case: it requires the intermediate squares to be empty, the king not to be in check, and the king not to pass through an attacked square:

if (castle & wk) {  // if white still has kingside castling rights
    if (!getSquare(occupancies[both], f1) &&
        !getSquare(occupancies[both], g1) &&
        !is_square_attacked(e1, black) &&   // king not in check
        !is_square_attacked(f1, black))     // f1 not attacked (the king passes through it)
        add_move(encode_move(e1, g1, K, 0, 0, 0, 0, 1));
}

The is_square_attacked() function uses an elegant trick: to find out whether a square is attacked by a given side, you pretend there is a "hypothetical" piece on that square and check whether it would attack anything. If you hypothetically place a bishop on e1 and it "sees" an enemy bishop along the diagonal, then e1 is attacked by that bishop — the reasoning works in both directions because attacks are symmetric.

int is_square_attacked(int square, int side) {
    // if a pawn of the opposite side were here, would it see an enemy pawn?
    if (pawn_attacks[side^1][square] & bitboards[side ? P : p])  return 1;
    if (knight_attacks[square]       & bitboards[side ? N : n])  return 1;
    if (get_bishop_attacks(square, occupancies[both]) & bitboards[side ? B : b]) return 1;
    if (get_rook_attacks(square,   occupancies[both]) & bitboards[side ? R : r]) return 1;
    if (get_queen_attacks(square,  occupancies[both]) & bitboards[side ? Q : q]) return 1;
    if (king_attacks[square]        & bitboards[side ? K : k])  return 1;
    return 0;
}

Making and unmaking moves

During the search, the engine applies and then undoes millions of moves. The question is: how do you "go back" after making a move?

There are two approaches. The first — unmake move — reverses every single change made to the board: it puts the piece back where it was, restores the captured piece, restores the previous castling rights, and so on. It is faster but much harder to implement correctly (there are dozens of special cases).

The second — copy-restore — saves the entire board state before applying a move and restores it with a memcpy when it needs to be undone. Simpler, slightly slower, but more than sufficient for a single-threaded engine.

#define copy_board() \
    U64 bitboards_copy[12], occupancies_copy[3]; \
    int side_copy, castle_copy, enpassant_copy; \
    U64 hash_key_copy; \
    memcpy(bitboards_copy, bitboards, sizeof(bitboards)); \
    memcpy(occupancies_copy, occupancies, sizeof(occupancies)); \
    side_copy = side; castle_copy = castle; \
    enpassant_copy = enpassant; hash_key_copy = hash_key;
 
#define take_back() \
    memcpy(bitboards, bitboards_copy, sizeof(bitboards)); \
    memcpy(occupancies, occupancies_copy, sizeof(occupancies)); \
    side = side_copy; castle = castle_copy; \
    enpassant = enpassant_copy; hash_key = hash_key_copy;

Castling rights are encoded in 4 bits (one for each type: white kingside, white queenside, black kingside, black queenside). Instead of writing a series of ifs for every move that might invalidate them, I use a lookup table: every square on the board has a value that, ANDed with the current rights, automatically clears the right bits. Any move from or to e1 removes both of white's rights, any move from h1 removes white kingside, and so on:

const int castling_rights[64] = {
 7, 15, 15, 15,  3, 15, 15, 11,  // rank 8: touching a8 clears black queenside, h8 clears black kingside
 // ...
13, 15, 15, 15, 12, 15, 15, 14   // rank 1: touching a1 clears white queenside, etc.
};
 
castle &= castling_rights[source];
castle &= castling_rights[target];

Zobrist hashing

Every chess position has a 64-bit hash key associated with it. It serves two purposes: recognising when the same position repeats (threefold repetition = draw) and, in future, indexing a transposition table so the same position isn't searched twice.

Zobrist's approach (1970) works like this: at startup, generate a random 64-bit number for every possible combination of (piece type, square) — 12 × 64 = 768 numbers. Plus one number for each combination of castling rights (16 combinations), one for each en passant square (64), and one to indicate "black to move".

The key of a position is the XOR of all the numbers corresponding to the pieces present and to the current state:

U64 piece_keys[12][64];
U64 enpassant_keys[64];
U64 castle_keys[16];
U64 side_key;

The fundamental property of XOR is that it is invertible: if you do A ^ B, you can get back to A by doing ^ B again. This makes key updates incremental — instead of recomputing everything from scratch after each move, you XOR in only the changes:

hash_key ^= piece_keys[piece][source];  // "remove" the piece from the source square
hash_key ^= piece_keys[piece][target];  // "add" the piece on the target square
hash_key ^= side_key;                   // flip the side to move
// update en passant and castling rights with the same mechanism...

With 64 bits, the probability that two different positions share the same key (a "collision") is about 1 in 18 quintillion — effectively zero.

The search: negamax alpha-beta

This is where the engine's real intelligence lives.

To find the best move, the engine has to explore the game tree: from the current position it generates every possible move, then for each of those every opponent reply, then every reply to those replies, and so on down to a certain depth. At the end of each sequence it evaluates the position. The best move is the one leading to the position with the highest score.

The problem is the size of that tree. With roughly 35 possible moves per position and a search at depth 10, you get 35^10 ≈ 2.7 × 10^15 positions. Even at a billion positions per second, that would take years.

Minimax and negamax

The base algorithm is minimax: white wants to maximise the score, black wants to minimise it. They alternate: on white's turn you pick the move with the highest score, on black's turn the one with the lowest (from white's point of view).

Negamax is a more elegant variant that exploits the fact that chess is a zero-sum game: what is good for one side is equally bad for the other. Instead of having two separate cases (maximise/minimise), you simply negate the score at each level and always maximise:

negamax(position, depth):
    if depth == 0: return evaluate(position)
    best_score = -infinity
    for each move:
        make_move()
        score = -negamax(position, depth - 1)  // the "-" flips the perspective
        unmake_move()
        best_score = max(best_score, score)
    return best_score

Alpha-beta pruning

Alpha-beta is the optimisation that makes the search practical. The intuition: if while analysing a move you discover the opponent already has a reply that leaves you worse off than something you can already guarantee with a different move, you can stop analysing that move — it will never change your choice.

You keep two variables:

• Alpha: the best score the side to move can already guarantee with the moves analysed so far. "I already know I can do at least this well."
• Beta: the best score the opponent can guarantee. "The opponent won't let me do better than this."

If at any point a move's score exceeds beta — meaning it is so good that the opponent will never allow it (because they could have avoided reaching this point) — you cut off the entire subtree. That's a beta cutoff.

int negamax(int alpha, int beta, int depth) {
    pv_length[ply] = ply;
 
    if (depth == 0)
        return quiescence(alpha, beta);
 
    if (ply && is_repetition())
        return 0;  // draw by repetition
 
    nodes++;
 
    int in_check = is_square_attacked(
        get_lsb_index(bitboards[side == white ? K : k]),
        side ^ 1
    );
 
    if (in_check) depth++;  // extend the search when in check
 
    int legal_moves = 0;
    moves move_list;
    generate_moves(&move_list);
    sort_moves(&move_list);
 
    for (int i = 0; i < move_list.count; i++) {
        copy_board();
        ply++;
 
        if (!make_move(move_list.moves[i], all_moves)) {
            ply--;
            continue;  // illegal move (leaves the king in check)
        }
        legal_moves++;
 
        int score = -negamax(-beta, -alpha, depth - 1);
 
        ply--;
        take_back();
 
        if (score >= beta)
            return beta;  // beta cutoff: the opponent will avoid this position
 
        if (score > alpha) {
            alpha = score;
            // update the principal variation (the best move sequence found)
            pv_table[ply][ply] = move_list.moves[i];
            for (int j = ply + 1; j < pv_length[ply + 1]; j++)
                pv_table[ply][j] = pv_table[ply + 1][j];
            pv_length[ply] = pv_length[ply + 1];
        }
    }
 
    if (legal_moves == 0)
        return in_check ? -49000 + ply : 0;  // checkmate or stalemate
 
    return alpha;
}

The mate score is ply-dependent: -49000 + ply. If the engine finds a mate in 3 and one in 5, the former scores higher (fewer ply subtracted), so it prefers it. Without this detail the engine would still find the mate but might pick the longer sequence for no reason.

The principal variation (PV) is the sequence of best moves the engine has found. It is kept in a triangular pv_table[ply][ply] and displayed in the info line of the UCI protocol — it's what you see scrolling by when you watch a GUI while the engine analyses.

In the best case, alpha-beta reduces the effective branching factor from 35 to about √35 ≈ 6. That means the same node count reaches twice the depth — the difference between finding a mate in 5 and one in 10.

Quiescence search

Picture this situation: the main search stops at depth 8. The last move examined is Qxe5 — the queen captures a pawn on e5. The engine evaluates the position and sees: "I'm a pawn up, great". It plays that move.

The problem: the engine never saw that on the next turn the opponent plays Bxe5, recapturing the pawn with the bishop. The queen is attacked, it has to move, and in the end the material is simply level. The engine traded a move based on a wrong evaluation because it stopped halfway through an exchange.

This is the horizon effect: the engine only sees up to its depth, and the evaluation at the leaf is often inaccurate because the position is tactically unstable.

Quiescence search solves the problem: instead of calling evaluate() directly at depth 0, you call quiescence(), which keeps searching but considers captures only until the position settles down:

int quiescence(int alpha, int beta) {
    nodes++;
 
    // "Standing pat": the value of the position without making further captures.
    // The engine can always choose not to capture — so this is the guaranteed minimum.
    int stand_pat = evaluate();
 
    if (stand_pat >= beta) return beta;  // already too good, the opponent avoids it
    if (stand_pat > alpha) alpha = stand_pat;
 
    moves capture_list;
    generate_moves(&capture_list);  // generate captures only
    sort_moves(&capture_list);
 
    for (int i = 0; i < capture_list.count; i++) {
        copy_board();
        ply++;
 
        if (!make_move(capture_list.moves[i], only_captures)) {
            ply--;
            continue;
        }
 
        int score = -quiescence(-beta, -alpha);
 
        ply--;
        take_back();
 
        if (score >= beta) return beta;
        if (score > alpha) alpha = score;
    }
 
    return alpha;
}

The "standing pat" is crucial: the engine can always choose not to capture anything, which establishes a lower bound. In a position with 10 possible captures, the engine will only explore the ones that genuinely improve the position.

In practice quiescence adds a relatively small number of nodes but completely solves the half-finished-exchange problem. Without it, any engine would make elementary tactical blunders.

Move ordering

Alpha-beta is only efficient if good moves are analysed first. To see how much this matters, consider: if the best move is always the first one analysed, every node almost certainly produces an immediate cutoff and the tree shrinks to its minimum. If instead moves arrive in random order, many subtrees get explored pointlessly before the cutoff is found.

The difference is not marginal: good ordering can cut the node count by a factor of 10x or more compared to no ordering at all.

Agata uses a scoring system with decreasing priority:

1. PV move (score: 20000) — the best move found in the previous search iteration (iterative deepening is explained further down). It is almost certainly still the best move and almost certainly produces an immediate cutoff.

2. MVV/LVA — Most Valuable Victim, Least Valuable Attacker (10000+) — for captures, the "good" ones are prioritised: capturing a queen with a pawn is a bargain (worth +900 in material), capturing a pawn with a queen is risky. The MVV/LVA table encodes this: rows = attacker, columns = victim.

const int mvv_lva[12][12] = {
//   Pwn  Kni  Bis  Roo  Que  Kng  (victims, from least to most valuable)
    {105, 205, 305, 405, 505, 605, ...},  // pawn attacker
    {104, 204, 304, 404, 504, 604, ...},  // knight attacker
    // ...
};

Pawn captures queen (605) always beats knight captures pawn (104), regardless of anything else.

3. Killer moves (9000 and 8000) — a "killer" move is a non-capture that caused a beta cutoff in another branch of the tree at the same depth (the same "ply"). The intuition: if this move was good enough to cut off the search in another context, it might do the same here.

"Ply" is the distance from the root: ply 0 is the starting position, ply 1 is after one move, ply 2 after two moves, and so on. Two killers are kept per ply in LIFO order:

int killer_moves[2][64];  // [slot 0/1][ply]
 
// after a beta cutoff on a quiet move:
killer_moves[1][ply] = killer_moves[0][ply];  // move the old killer into the second slot
killer_moves[0][ply] = move;                  // store the new killer in the first slot

4. History heuristic — for the remaining quiet moves, a history table is used: every time a non-capture causes a beta cutoff, its "history score" increases in proportion to the search depth (cutoffs at high depth are more meaningful). Moves with a high history score are tried first.

int history_moves[12][64];  // [piece][target square]
 
history_moves[get_move_piece(move)][get_move_target(move)] += depth;

Pruning techniques

Ordering improves alpha-beta by reducing the number of nodes explored. Pruning goes further: it cuts entire subtrees that are unlikely to change the final evaluation.

Null move pruning

The idea rests on an empirical observation: in most positions, making a move is better than passing the turn. If even by "passing" (handing the turn to the opponent without moving anything) the position is still good enough to exceed beta, then our advantage is so obvious that there is no point analysing this line in depth.

It is implemented literally by skipping the turn — you flip the side to move without applying any move, run a reduced search (depth - 1 - R, where R=2 is the reduction factor), and if the result exceeds beta you cut off:

if (depth >= 3 && !in_check && ply > 0) {
    copy_board();
    ply++;
 
    side ^= 1;  // pass the turn
    if (enpassant != no_sq) hash_key ^= enpassant_keys[enpassant];
    enpassant = no_sq;
    hash_key ^= side_key;
 
    int score = -negamax(-beta, -beta + 1, depth - 1 - 2);  // search with R=2
 
    ply--;
    take_back();
 
    if (score >= beta)
        return beta;  // even after passing we're ahead: prune
}

This pruning has to be disabled in zugzwang positions — situations where any move worsens the position (passing would be the best move, but it isn't legal in chess). Zugzwang occurs almost exclusively in king-and-pawn endgames, where every king move gives ground. The !in_check guard is already a partial filter, but more advanced implementations disable null move in endgames.

Late move reduction (LMR)

After good move ordering, the first 3-4 moves are the ones most likely to be good. The later moves — especially non-captures — are statistically much less promising. LMR reduces the search depth for these late moves, betting that they won't change the final evaluation.

if (moves_searched >= 4 &&   // after the first 4 moves
    depth >= 3 &&             // only at meaningful depth
    !in_check &&              // not in check (too forcing)
    !get_move_capture(move) && // not captures
    !get_move_promoted(move))  // not promotions
{
    // reduced search at depth-2 with a zero window (alpha-1, alpha)
    // a "zero window" only checks whether the score exceeds alpha, not by how much
    score = -negamax(-alpha - 1, -alpha, depth - 2);
} else {
    score = alpha + 1;  // force the full search in the block below
}
 
// If LMR finds something promising, re-search at full depth to confirm
if (score > alpha) {
    score = -negamax(-alpha - 1, -alpha, depth - 1);
    // if this zero-window search is also promising, do the full search
    if (score > alpha && score < beta)
        score = -negamax(-beta, -alpha, depth - 1);
}

The "zero window" (-alpha-1, -alpha) is a technique in its own right: a window of width 1 that only answers the question "does this node exceed alpha, yes or no?" without evaluating it precisely. It is faster because it prunes almost everything.

The risk of LMR is reducing a move that is actually good. That's why the re-search mechanism is essential: if the reduced search returns a promising score, you re-search at full depth to be sure. In practice the vast majority of late moves really are poor and the re-search almost never triggers.

Check extension

When you are in check the position is forcing: there are very few legal replies, often one or two. Skipping the search of those replies because the maximum depth has been reached would be a serious mistake — you would risk walking into an unforeseen mate.

if (in_check) depth++;

A single line that guarantees the search never stops in the middle of a checking sequence. The potential tree explosion is kept in check by the fact that the number of legal moves while in check is typically very low (1-5), so the extension adds few nodes in practice.

The evaluation function

When the search stops — or quiescence search finds no more captures — evaluate() assigns a score to the position. This function is called tens or hundreds of millions of times per game: it has to be fast and accurate.

Scores are expressed in centipawns: 100 = the value of one pawn. An advantage of +250 means the engine estimates it is 2.5 pawns ahead in material plus position. A negative score means a disadvantage. The mate score is ±49000 — comfortably above any material advantage, so the engine always prefers finding mate over accumulating material.

Material

const int material_score[12] = {
    100, 300, 350, 500, 1000, 10000,   // white: pawn, knight, bishop, rook, queen, king
   -100,-300,-350,-500,-1000,-10000    // black (negative because white wants to maximise)
};

The bishop is worth 350 against the knight's 300. This reflects the empirical advantage of the "bishop pair" in open positions, where long clear diagonals amplify their range. In closed positions with pawn chains, knights are often more useful. Using 350 instead of 300 makes the engine reluctant to give up a bishop for a knight without compensation.

Piece-square tables

Material alone isn't enough. A knight on a1 is technically worth the same as a knight on e4, but in practice the latter attacks 8 squares and the former only 2. Piece-square tables add a positional bonus or penalty depending on the square:

const int pawn_score[64] = {
     0,   0,   0,   0,   0,   0,   0,   0,
    90,  90,  90,  90,  90,  90,  90,  90,  // rank 7: one move from promotion
    30,  30,  50,  70,  70,  50,  30,  30,  // rank 6: central advance rewarded
    10,  10,  20,  50,  50,  20,  10,  10,  // rank 5: the centre is worth more
     5,   5,  10,  40,  40,  10,   5,   5,  // rank 4
     0,   0,   0,  20,  20,   0,   0,   0,  // rank 3
     5,  -5, -10,   0,   0, -10,  -5,   5,  // rank 2: slight penalty if undeveloped
     0,   0,   0,   0,   0,   0,   0,   0   // rank 1 (unreachable in practice)
};
 
const int knight_score[64] = {
    -50,-40,-30,-30,-30,-30,-40,-50,  // edge: the knight is useless here
    -40,-20,  0,  0,  0,  0,-20,-40,
    -30,  0, 10, 15, 15, 10,  0,-30,
    -30,  5, 15, 20, 20, 15,  5,-30,  // centre: the knight attacks 8 squares here
    -30,  0, 15, 20, 20, 15,  0,-30,
    -30,  5, 10, 15, 15, 10,  5,-30,
    -40,-20,  0,  5,  5,  0,-20,-40,
    -50,-40,-30,-30,-30,-30,-40,-50   // corners: -50, the knight "dies" there
};

These numbers encode fundamental chess principles: pawns are worth more the closer they get to promotion, knights in the centre control far more squares than on the edge ("a knight on the rim is dim"), kings should stay sheltered in the opening and middlegame but centralise in the endgame.

For black pieces a mirror table is used that reflects the board vertically, so the same tables work for both colours without duplicating them. A black pawn on e5 uses the same positional bonus as a white pawn on e4 (the mirrored square).

Accumulating the score

int evaluate() {
    int score = 0;
 
    for (int piece = P; piece <= k; piece++) {
        U64 bb = bitboards[piece];
        while (bb) {
            int square = get_lsb_index(bb);
            score += material_score[piece];  // material (positive for white, negative for black)
 
            switch (piece) {
                case P: score += pawn_score[square];                      break;
                case p: score -= pawn_score[mirror_score[square]];        break;
                case N: score += knight_score[square];                    break;
                case n: score -= knight_score[mirror_score[square]];      break;
                // ... all 12 types
            }
            popSquare(bb, square);
        }
    }
 
    // the score is always from the point of view of the side to move
    return (side == white) ? score : -score;
}

The final negation for black matters: the negamax search expects evaluate() to always return a score where "positive = good for me", regardless of colour. So if it is black's turn and black is ahead, the raw material score would be negative (white has less), but it must be returned as positive.

This evaluation is deliberately simple. Stronger engines add pawn structure analysis (passed, isolated, doubled pawns), mobility scores (how many squares each piece attacks), king safety (pawn shield, open files near the king) and endgame-specific logic. Those are on the roadmap for v3.

Iterative deepening and aspiration windows

A reasonable question: why not just search straight to the maximum available depth?

The answer has to do with time management. In a real game the engine has a limited time budget per move. It doesn't know in advance how deep it will manage to get in the time available. If it starts a depth-12 search and time runs out halfway through the tree, it has no move to play.

Iterative deepening solves this: you search at depth 1, then 2, then 3, and so on. Each iteration completes before the next one starts. When time runs out, you play the best move found in the last completed iteration.

There is a second benefit: move ordering. The best move found at depth d is almost always still the best at depth d+1. Using it as the first move to examine guarantees immediate cutoffs and makes the deeper search far more efficient.

The overhead of repeating work is negligible because the tree grows exponentially: depth 10 takes roughly 35 times more nodes than depth 9, so the entire search up to depth 9 is less than 3% of the total work of depth 10.

Aspiration windows

In iterative deepening, the score from the previous iteration is a good estimate of the next one's score. Aspiration windows exploit this: instead of starting with the full window [-50000, +50000], you use a narrow window centred on the previous score, for example [score-50, score+50].

A narrower window means alpha and beta are closer together, which produces many more cutoffs and makes the search significantly faster. If the score falls outside the window (because the position changed dramatically), you widen it fully and re-search — but in the vast majority of cases the narrow window works:

int alpha = -50000, beta = 50000;  // first iteration: full window
 
for (int current_depth = 1; current_depth <= search_depth; current_depth++) {
    int score = negamax(alpha, beta, current_depth);
 
    if (score <= alpha || score >= beta) {
        // failed outside the window: re-search with the full window
        alpha = -50000;
        beta  =  50000;
        score = negamax(alpha, beta, current_depth);
    }
 
    // set a narrow window for the next iteration (±50 centipawns)
    alpha = score - 50;
    beta  = score + 50;
 
    printf("info score cp %d depth %d nodes %lld pv ", score, current_depth, nodes);
    for (int i = 0; i < pv_length[0]; i++) print_move(pv_table[0][i]);
    printf("\n");
}

The UCI protocol

Agata talks to chess GUIs through the UCI protocol (Universal Chess Interface) — the industry standard. The engine reads commands from stdin and writes responses to stdout, following a specific text protocol:

• The GUI sends uci → the engine responds with its name and uciok
• The GUI sends position startpos moves e2e4 e7e5 ... → the engine updates the board
• The GUI sends go wtime 60000 btime 60000 movestogo 40 → the engine starts searching
• The engine responds with info depth X score cp Y pv ... lines during the search
• The engine responds with bestmove e2e4 when it's done

void uci_loop() {
    printf("id name Agata\n");
    printf("id author Filippo Maretti\n");
    printf("uciok\n");
 
    while (1) {
        fgets(input, sizeof(input), stdin);
 
        if (!strncmp(input, "isready", 7))       printf("readyok\n");
        else if (!strncmp(input, "position", 8)) parse_position(input);
        else if (!strncmp(input, "go", 2))       parse_go(input);
        else if (!strncmp(input, "quit", 4))     break;
    }
}

Time handling: the go command includes wtime and btime (time remaining in ms for white and black), winc/binc (increment per move), and movestogo (moves until the next time control). From these you compute how much time to spend on this move:

stoptime = get_time_ms() + time / movestogo + inc / 2 - 50;

The search checks the clock every 2047 nodes — using a bit mask (nodes & 2047) == 0 instead of a modulo, which is slightly faster. The -50 is a safety margin to avoid overshooting the time because of latency.

The engine also includes a TCP server mode that accepts UCI commands on port 8080 — useful for embedding it in web applications without having to launch it as a subprocess.

Perft: verifying correctness

How do you know your move generator is correct? You can't just play and hope the bugs surface — many bugs in the special cases (en passant, castling out of check, capture promotions) only show up in rare positions.

The solution is perft (performance test): counting the exact number of leaf nodes at a given depth from a given position. These values are known with mathematical certainty — computed and verified by dozens of engines over the years.

void perft_driver(int depth) {
    if (depth == 0) { nodes++; return; }
 
    moves move_list;
    generate_moves(&move_list);
 
    for (int i = 0; i < move_list.count; i++) {
        copy_board();
        if (!make_move(move_list.moves[i], all_moves)) { take_back(); continue; }
        perft_driver(depth - 1);
        take_back();
    }
}

From the starting position the correct values are:

At depth 1 there are exactly 20 legal moves from the starting position (16 pawn moves + 4 knight moves). Any deviation — even by a single unit — means there's a bug.

The debugging technique is to divide by move: you print the count for each move at the root and compare it against the tabulated values. The move with the wrong count is the one containing the bug. You recurse down until you find the exact position generating too many or too few nodes.

I spent a ridiculous amount of time on these numbers. The most common bugs: the en passant square not being cleared after every move (which makes the engine believe en passant is available for many turns), castling-rights updates being wrong for certain pieces, capture promotions not removing the captured piece correctly.

What's still missing

Agata v2 runs at around 2400 Elo, but there are parts I still want to add:

Transposition table. The Zobrist key is computed incrementally but isn't used to store results yet. A TT lets you recognise positions you've already analysed (reachable through different move orders — "transpositions") and reuse the result instead of re-analysing. In a mature engine it can cut nodes by a factor of 2-4x.

Pawn structure. Right now pawns are only evaluated by position and material, but their relationships with each other matter a lot. A passed pawn (no enemy pawn can stop it on its file) is worth far more than its nominal value. An isolated pawn (no friendly pawn on the adjacent files) is structurally weak. A doubled pawn (two pawns on the same file) is almost always a problem.

Mobility. Counting the squares each piece can legally reach is one of the most reliable predictors of position quality. A bishop with 12 free squares is far more active than one with 3 — even though both are worth 350 centipawns in raw material.

King safety. The current king evaluation is fairly crude. Strong engines account for the pawn shield in front of a castled king, open files near the king (attack corridors), and the number of enemy pieces closing in.

Building a chess engine is one of the most instructive projects I have ever done — bit manipulation, algorithmic optimisation, game theory, all at once. The full code is on GitHub.