Building a Chess Engine and AI Bot

Chess has served as a benchmark problem for artificial intelligence since the very birth of the field. Alan Turing described a paper chess-playing algorithm in 1950, and Claude Shannon published the foundational framework for computer chess the same year. Today, engines like Stockfish and Leela Chess Zero play at levels far beyond any human grandmaster, but the algorithmic ideas they are built upon, such as board representation, legal move generation, alpha-beta search, and positional evaluation, are surprisingly accessible. Building a chess engine from scratch is one of the most complete exercises in applied computer science: it demands careful data structure design, recursive search, hashing, and incremental state management all in a single coherent program.

In this chapter we implement a fully playable chess engine and AI bot in Gerbil Scheme that consists of three modules totaling roughly 900 lines of code. The engine correctly handles every rule of chess, including en passant, castling, pawn promotion, and the fifty-move draw rule. The AI opponent uses iterative deepening negamax search with alpha-beta pruning, a transposition table for caching previously evaluated positions, a quiescence search to avoid the horizon effect on captures, and piece-square tables that encode positional knowledge. The interactive command-line interface renders a coloured Unicode board in the terminal and accepts moves in Universal Chess Interface (UCI) notation.

The first design decision in any chess engine is how to represent the board in memory. The two dominant approaches are bitboards (one 64-bit integer per piece type, with bits corresponding to occupied squares) and mailbox representation (an array mapping square index to piece). Bitboards enable parallelism via bitwise operations and are used in professional engines, but they make the code significantly harder to read. For this chapter we use an 8×8 mailbox encoded as a flat 64-element vector. Each element holds a small integer encoding both the piece type (bits 0–2) and the piece color (bits 3–4) using bitwise OR:

The type codes are 0 (empty) through 6 (king). White is encoded as 8 and black as 16. To extract the type from a piece value p we compute p AND 7; to extract the color we compute p AND 24. This simple two-field encoding eliminates branch-heavy conditionals and maps naturally to Gerbil’s bitwise-and, bitwise-ior, and bitwise-xor primitives.

In addition to the board grid, the engine maintains an active piece list consisting of two lists of occupied square indices, one per color. This means that when generating moves for white, the engine iterates only over white’s active squares rather than all 64 squares, a constant-factor speedup that matters at high search depths.

A naive move generator re-derives the set of reachable squares for each piece on every call. Precomputed tables eliminate that work by computing, at startup, every possible knight target, king target, and sliding-piece ray from each of the 64 squares. A ray is an ordered list of squares in one direction from a given square, stopping at the board edge. During move generation the engine walks each ray until it hits a friendly piece (stop) or an enemy piece (stop after capture). Because the tables are fixed arrays, this lookup is O(1) per ray and allocates no new memory.

Searching a chess position requires quickly comparing positions to detect repetitions and to look up previously evaluated results in a transposition table. A naive equality check over all 64 squares is O(64); Zobrist hashing reduces this to O(1) by maintaining a 64-bit integer that uniquely identifies (with overwhelmingly high probability) the current board state.

The Zobrist scheme assigns a random 64-bit number to each (square, piece) combination at startup that consists of 64 squares times 32 possible piece encodings gives 2048 numbers. The board hash is the XOR of all the numbers corresponding to occupied squares. Critically, XOR is self-inverse: making a move that removes a piece from square s simply XORs out zobrist[s][piece], and placing the new piece XORs in the new value. Additional random numbers encode whose turn it is, the four castling rights, and the en-passant file. This incremental update strategy keeps the hash cost per move to a handful of XOR operations.

A chess engine evaluates a position by searching forward through possible move sequences. The minimax algorithm assigns a score to the root position by assuming both players play optimally: the side to move maximizes the score, while the opponent minimizes it. Negamax is a clean reformulation of minimax that exploits the zero-sum nature of chess: the score for the side to move equals the negation of the score for the opponent. Every recursive call always maximizes, and scores are negated at each level.

Searching the full game tree is computationally infeasible. Alpha-beta pruning cuts large portions of the tree without affecting the result. Two bounds are passed through the recursion:

• alpha: the best score the maximizer can guarantee so far.
• beta: the best score the minimizer can guarantee so far.

Whenever alpha >= beta, the current subtree cannot influence the final result, and search is abandoned. In the best case, with perfect move ordering, alpha-beta reduces the effective branching factor from b to sqrt(b), roughly doubling the searchable depth within the same time budget.

Iterative deepening runs alpha-beta repeatedly at depths 1, 2, 3, … up to the target depth. At each depth, the best move found is stored in the transposition table and used to order moves at the next depth. Because better-ordered moves produce more cutoffs, iterative deepening with transposition table hints typically outperforms a single deep search in the same time window.

Quiescence search is a fix for the “horizon effect”: at the maximum depth, a position may look quiet but have a hanging piece about to be captured. The quiescence extension continues the search past the nominal depth, but only for captures and promotions. It terminates when the board is “quiet” (no forcing tactics available), making the static evaluation far more reliable.

When search reaches a leaf node, it calls a static evaluation function that returns a score in centipawns (one hundredth of a pawn value). The evaluation in this engine has two components:

1. Material count: the sum of piece values: pawn=100, knight=320, bishop=330, rook=500, queen=900, king=20000 (effectively infinite).
2. Piece-square table (PST) bonuses: each piece type has an 8×8 table of bonus/penalty values expressing positional preferences. Knights are penalized on the rim and rewarded in the center. Pawns are rewarded for advancement toward the seventh rank. Kings are penalized for exposure in the middlegame but rewarded for active central play in the endgame.

The engine detects the endgame by summing non-pawn, non-king material; when it falls below 3000 centipawns, the king PST switches to an endgame table that favors central activity.

The project directory source_code/chess-game contains the following files:

The engine module is the foundation of the entire project. It exports every primitive needed by the AI and CLI layers: piece constants, board structures, move structures, move generators, and the make/unmake functions.

The module begins by aliasing Gambit’s long-form bitwise function names to shorter Lisp-style names, then defining the piece encoding constants.

The piece-type and piece-color helpers simply mask out the relevant bits of a combined piece integer. For example, a white queen is encoded as logior WHITE QUEEN = logior 8 5 = 13. Calling piece-type 13 returns logand 13 7 = 5 (QUEEN), and piece-color 13 returns logand 13 24 = 8 (WHITE). Castling rights are stored as a four-bit mask: bit 0 = white kingside, bit 1 = white queenside, bit 2 = black kingside, bit 3 = black queenside.

The board uses a linear index where square sq = rank * 8 + file, with rank 0 being the first rank (White’s back rank) and file 0 being the a file. The square-names vector maps 0–63 to UCI strings like "a1", and name-to-square is the reverse hash table.

The precomputed tables are filled by a startup loop. For knights and kings the loop generates the short fixed offsets. For sliding pieces (rook, bishop, queen), it generates rays that are ordered lists of squares in each direction, stopping at the board boundary:

Each element of rook-rays at index sq is a list of four rays, each ray being a list of square indices in order from sq outward. When the move generator walks a ray and hits a piece, it stops so no squares past that piece are accessible.

The engine uses a deterministic 64-bit linear congruential generator (LCG) to produce the Zobrist random numbers at startup. Using a seeded RNG ensures that the numbers are identical across runs (important for debugging) without requiring a hardcoded table.

The board-compute-zobrist-hash function builds the full hash from scratch by iterating over occupied squares. In practice this is only called once, when a position is loaded from FEN. All subsequent hash updates are incremental: the board-make-move! function XORs out moved/captured pieces and XORs in their new values before updating the board state.

Gerbil’s defstruct macro creates transparent structures with automatic accessors and setters. The move structure records every attribute needed to fully undo a move:

The board structure holds the complete game state. A separate board-state snapshot records the fields that are difficult to recompute during undo (the Zobrist hash, castling rights, en-passant square, and half-move clock):

The Forsyth-Edwards Notation (FEN) is the standard format for encoding chess positions as strings. A typical starting position FEN is:

The six space-separated fields encode: piece placement (ranks 8 to 1, files a to h), active color, castling availability, en passant target square, half-move clock, and full-move number. Uppercase letters are white pieces, lowercase are black.

The board-from-fen! function mutates an existing board in place, making it suitable for use as a reset operation. It uses pregexp-split to tokenize the FEN string, then walks the piece placement character by character:

Move generation is a two-phase process. First, get-pseudo-legal-moves generates all moves that obey piece movement rules but may leave the king in check. Then get-legal-moves filters this list by actually making each move, checking whether the king is attacked after the move, and unmaking it.

The pseudo-legal generator iterates over the active piece list for the side to move and dispatches on piece type:

The pawn case is the most complex, handling both pushes and diagonal captures, each possibly resulting in four promotion moves if the destination rank is the back rank. En-passant captures store the captured pawn’s square (not the destination square) in piece-captured by looking one square behind the en-passant target.

Castling is appended after the main loop. The engine checks that the king and rook are on their original squares, the intermediate squares are empty, and none of the king’s transit squares are under attack:

The is-square-attacked? function checks all attack vectors from a given square: pawn attacks (reverse-engineering from the target’s perspective), knight jumps, king proximity, and sliding rays for rooks/queens and bishops/queens.

The board-make-move! function returns a board-state snapshot before modifying the board. The board-unmake-move! function restores the board using that snapshot. This design avoids allocating a new board object for every node in the search tree.

The Zobrist hash is restored simply by copying it from the snapshot so there is no need to re-derive it, since it was saved before any move was applied. Castling unmake moves the rook back from its castled position; en-passant unmake restores the captured pawn to its original square.

The AI module imports the engine and adds everything needed to select a strong move: position evaluation, move ordering, and the search algorithm.

Each piece type has an 8×8 table of centipawn bonus/penalty values expressing positional preferences. The tables are written from White’s perspective (rank 1 at the bottom), and Black’s scores are looked up with logxor sq 56 that is a simple XOR that mirrors the square index vertically.

The PAWN_PST rewards pawns that have advanced toward promotion, bonuses pawns on the d and e files in the center, and penalizes doubled pawns in front of the king. The KNIGHT_PST heavily penalizes edge squares (-50 in the corners) and rewards the central cluster. Two separate king tables, KING_MIDDLE_PST and KING_END_PST, are applied based on whether the position is an endgame (total non-pawn, non-king material below 3000 centipawns):

The static evaluator returns a score in centipawns from the perspective of the side to move. Positive is good for the moving side, negative is bad:

The final line negates the score when black is to move, converting from an absolute white-perspective score to a side-to-move-perspective score as required by negamax.

Alpha-beta pruning is most effective when the best move is searched first. The move-value function assigns a priority to each move before sorting:

MVV-LVA (Most Valuable Victim, Least Valuable Attacker) is a classic heuristic: capturing a queen with a pawn scores much higher than capturing a pawn with a queen, both because the queen is worth more and because risking a queen to capture a pawn is strategically suspect.

The transposition table is a hash table mapping Zobrist hashes to cached search results. Each entry records the search depth, the score, a flag indicating whether the score is exact or a bound, and the best move found:

When the table has more than 500,000 entries, it is flushed to prevent memory exhaustion between games.

The core search function implements negamax with alpha-beta pruning and transposition table lookup:

Checkmate is detected by an empty legal move list combined with the king being in check. The score (- -30000 (- max-depth depth)) encodes “checkmate in N moves” so positions with faster checkmates score higher (closer to -30000) because (- max-depth depth) is smaller when the mate happens sooner. This allows the engine to prefer forced mates over equivalent material wins.

The quiescence extension searches only captures (and promotions) past the nominal depth, continuing until the position is “quiet”:

The stand-pat score is the static evaluation without making any further capture. If the stand-pat already beats beta, the position is returned immediately because the opponent would not have allowed reaching this node in the first place. This is the quiescence equivalent of alpha-beta pruning.

The top-level get-best-move function wraps the search in an iterative deepening loop:

At each depth the transposition table best move from the previous depth is used to order the root moves. This “hash move” ordering is the single most effective pruning technique in practice.

The CLI module handles display and user input. It defines Unicode glyphs for each piece and renders the board using ANSI escape codes for colored squares.

The Unicode piece codepoints (U+2654 through U+265F) are the standard chess symbols present in most modern terminal fonts. The vector is indexed by piece encoding (e.g., logior WHITE KING = 14), giving O(1) glyph lookup.

The checkerboard pattern is produced by checking whether (rank + file) is even or odd, selecting between ANSI 256-color codes for dark grey (237) and brown (94). Each square is three characters wide: a space, the piece glyph, and a space.

Moves are entered in UCI notation: the source square followed by the destination square, with an optional promotion character (e.g., e2e4, e7e8q). The parse-move function looks the UCI string up in the legal move list rather than constructing a move object directly, ensuring the engine only executes genuinely legal moves:

The game loop handles three modes: human vs. bot, bot vs. human, and bot vs. bot. In bot-vs-bot mode a 500ms sleep between moves makes the game watchable at full speed. In-check detection, checkmate, stalemate, and the fifty-move rule are all tested before each move.

Perft (performance test) is the standard correctness benchmark for chess engines. It counts the number of leaf nodes reachable from a starting position at a given depth and compares the result against known-correct values. Any deviation indicates a bug in move generation.

The perft function doubles as a Zobrist hash integrity checker: after every make/unmake pair it verifies that the incremental hash equals a freshly recomputed hash. This catches any bug in the incremental update logic immediately.

The test runner checks three depths against known values:

The expected node counts (20, 400, 8902) are universally accepted reference values for the standard starting position. Depth 1 checks that exactly 20 opening moves are generated. Depth 2 verifies that each of those 20 positions generates exactly 20 responses (20 × 20 = 400). Depth 3 is where errors in promotion, en passant, and castling handling typically appear.

All targets are available through the Makefile. Make sure Gerbil Scheme (gxi and gxc) is installed and on your PATH.

All three depths pass, confirming that the move generator produces exactly the correct number of positions and that the Zobrist hash remains consistent through every make/unmake pair. The nodes-per-second (nps) figure reflects the interpreted speed of gxi; compiling with gxc typically doubles or triples this figure.

You enter moves in UCI notation. The sidebar updates after each move to show whose turn it is, the full-move number, the fifty-move counter, the en-passant target square, castling availability, and the static evaluation in pawn units.

Available in-game commands:

Choosing mode 3 plays both sides automatically at the selected depth. This is useful for watching the engine’s opening and middlegame tendencies:

The perft numbers are not arbitrary. At depth 1, exactly 20 moves are legal from the starting position: 16 pawn moves (two squares or one square for each of the eight pawns) and 4 knight moves. At depth 2, all 20 of white’s replies also have 20 legal responses (by symmetry of the starting position), giving 400. At depth 3, 8902 nodes are reached. Note that the divergence from 20^3 = 8000 arises because of en-passant possibilities created by the depth-2 double pawn pushes, and because some positions at depth 2 allow more than 20 responses.

A perft FAIL at depth 1 almost always indicates an error in basic piece movement. A FAIL at depth 3 that passes depths 1 and 2 typically points to a bug in en-passant, castling, or promotion handling, since those edge cases first appear at depth 3.

The evaluation sidebar shows the position score in pawn units, from White’s perspective. A score of +0.5 means White has a slight material or positional advantage worth half a pawn. A score of +3.0 corresponds to a full rook advantage. Scores above +20.0 indicate a forced checkmate has been found (the engine uses 30000 as the base checkmate value, scaled by distance).

The nodes count in the bot output reflects how many positions the engine examined. At depth 3, a typical middlegame position has around 10,000–50,000 nodes. At depth 4, expect 100,000–500,000. The dramatic reduction compared to a full minimax tree (~30^depth) is the combined effect of alpha-beta pruning, move ordering, and the transposition table.

The nps figure from the perft run is a measure of raw engine speed in the Gerbil interpreter. Typical interpreted throughput is 50,000–100,000 nodes per second. Running make compile first to produce optimized Gambit bytecode usually doubles this to 100,000–200,000 nps, sufficient for a responsive depth-4 or depth-5 search in under two seconds per move.

In this chapter we built a complete chess engine and AI bot in Gerbil Scheme. Starting from first principles, we designed a mailbox board representation with bitwise piece encoding, precomputed move tables for knights, kings, and sliding pieces, and an incremental Zobrist hashing scheme that provides O(1) position identity checks. The legal move generator handles all of chess’s special cases: pawn double pushes, en-passant captures, pawn promotions to any piece, and kingside and queenside castling with transit square attack checks.

On top of this engine we layered an AI search that combines iterative deepening negamax with alpha-beta pruning, a transposition table keyed on Zobrist hashes, MVV-LVA and PST-delta move ordering, and a quiescence extension that resolves captures before evaluating leaf nodes. The static evaluator combines material counts with piece-square tables that encode positional knowledge, switching between middlegame and endgame king tables based on remaining material.

The project demonstrates several Gerbil Scheme idioms worth carrying into other programs: aliasing long function names for readability, using defstruct with transparent: #t for easily printed structures, combining do loops for startup initialization with recursive lambda for runtime logic, and the make/unmake pattern for reversible state mutation that avoids copying large data structures during search.

The perft suite provides a disciplined correctness gate and a chess engine that passes all three depths is move-generation correct. The bot at depth 4 produces recognizable opening play (1. e4 e5 2. Nf3 followed by natural development) and will consistently defeat beginners, making this a satisfying demonstration of how much strategic behavior emerges from a relatively simple evaluation function combined with deep search.

A natural next step is to extend the search with null move pruning (trying a pass move to detect positions where the opponent has no effective threats) and late move reductions (searching the last few moves at a reduced depth), which together can double the effective search depth at no additional node cost.

Exercise 1: Display Board State as Unicode Art

Write a Gerbil Scheme function board->string that returns the current board position as a multi-line string of Unicode chess glyphs with rank numbers and file letters, but without any ANSI color codes. The function should be suitable for logging or writing the board to a file. Use the glyphs vector from cli.ss for piece rendering.

Expected output for the starting position:

Exercise 2: Count Attacked Squares

Using is-square-attacked? from engine.ss, write a function count-attacked-squares that takes a board b and a color (WHITE or BLACK) and returns the number of squares on the board that are attacked by that color. Run it on the starting position for both colors and verify that the results are equal (by symmetry).

Exercise 3: Perft Divide

Implement perft-divide, a variant of perft that prints, for each legal move from the root position, the number of leaf nodes reachable via that move at depth d-1. This “divide” output is the standard tool for isolating which move produces an incorrect node count. The starting position at depth 3 should show 20 moves, each with its node count, summing to 8902.

Exercise 4: Material Balance Reporter

Write a function material-report that takes a board and returns a formatted string breaking down the material count for each side by piece type. For example:

If one side is ahead, print the advantage in pawn units (e.g., White +1.5). Use this function to instrument the bot-vs-bot loop, printing the material report after every ten moves.

Exercise 5: Opening Book Integration

Create a simple opening book as a Gerbil hash table mapping FEN strings (of positions after 0, 1, and 2 moves) to a list of UCI move strings. Modify get-best-move in ai.ss to check the book first and, if the current position is in the book, pick a random move from the list rather than running the search. Seed the book with at least three openings (e.g., 1. e4, 1. d4, and 1. Nf3) and their most common replies. Verify that the bot plays book moves from the starting position.