Lecture 19: Leiserchess Codewalk

What this lecture covers

This session is a project orientation rather than a standard lecture: TA Helen Xu introduces Leiserchess, a laser-tag variant of chess that is the subject of the course's final project, then walks through the roughly 4,500-line reference codebase students will optimize. It covers the game rules, the testing infrastructure (scrimmage server, cloud autotester), the board and move representation, and the search algorithm used to pick moves.

This video sits at the start of the final project in MIT's performance engineering course, after lectures on parallelism and synchronization that the project will draw on. After watching, you'll understand how Leiserchess is played and scored, how moves are represented and generated, how alpha-beta and principal variation search prune the game tree, and which optimization structures (transposition table, killer moves, opening book) already exist in the starter code.

Key ideas

• Leiserchess rules: two teams of pawns and a king move and rotate on a board, and each turn ends with the king firing a laser that reflects off the long edge of pawns and kills them on the short edge; a side loses if its king is hit.
• Move representation: moves are packed into a compact struct with piece type, orientation, and from/intermediate/to squares, since a "swap" move touches an opposing piece before a following non-swap move.
• Board representation: the reference implementation uses a 16x16 array (an 8x8 board padded with sentinel squares) to simplify detecting when a move goes off the board.
• Static evaluation: the eval.c heuristics (king facing, king aggressiveness, king mobility, pawn centrality, pawn-between, laser coverage) score a position without searching further, and the lecture recommends tuning these existing heuristics before inventing new ones.
• Alpha-beta pruning: searching a game tree with a [alpha, beta] window lets a search skip subtrees it proves cannot change the outcome, cutting the nodes examined from b^d toward roughly b^(d/2) when moves are well ordered.
• Principal variation search: an alpha-beta variant that assumes the first move is best and verifies the rest with cheap zero-window "scout" searches, only doing a full search when a scout search disproves the assumption.
• Search infrastructure: a transposition table (indexed via incrementally updatable Zobrist hashing) avoids re-searching repeated positions, while killer-move and best-move tables help order moves to trigger earlier cutoffs.
• Elo-based grading: bots are compared by Elo rating from many games rather than raw search speed, since faster search only helps insofar as it lets the bot search deeper and play better moves.
• Correctness-first testing: the instructor stresses fixed-depth, deterministic testing (node counts, perft) and keeping old and new board representations side by side during migration, warning that "30 changes with something broken" is a common and painful failure mode.

Walkthrough

Game rules and example plays (1:03)

Helen Xu introduces Leiserchess pieces, orientations, basic and swap moves, the Ko rule (borrowed from Go, preventing immediate reversal of the opponent's last move), and draw conditions. Working through a board example, she shows students how firing the king's laser to kill an opposing pawn can expose their own king to a counter-shot, illustrating that naive captures can lose the game.

Notation, tooling, and grading (10:21)

The lecture covers Forsythe-Edwards-style position notation and game logs, then demonstrates the scrimmage server for one-off matches and the cloud autotester for running many games with a chosen time control and set of binaries. Bots are ranked by Elo rating rather than raw speed, though the lecture notes that searching deeper (i.e., being faster) does tend to raise Elo.

Board and move representation, and move generation (21:38)

The lecture details the position struct (padded 16x16 board, move history, Zobrist hash key, ply, king locations) and the packed move representation. It introduces perft, a debugging function that enumerates all moves to a given depth, as a way to confirm that optimizations to move generation haven't changed which moves are produced.

Static evaluation heuristics (24:39)

Xu walks through the heuristics in eval.c that score a position: bonuses for the king facing the opponent, being central, and having free adjacent squares; bonuses for pawns near the center or between the two kings; and laser coverage, a heuristic estimating how much of the board a side's laser could threaten from its possible moves.

Search: game trees, alpha-beta, and principal variation search (26:41)

The lecture builds up from a naive full game-tree search, explains quiescence search (extending search past captures to avoid stopping mid-exchange), then walks through a worked alpha-beta example showing how a beta cutoff lets a search skip entire subtrees, backed by the theorem that best-ordered alpha-beta search examines roughly b^(d/2) nodes instead of b^d. It then extends this to principal variation search, where cheap zero-window scout searches verify (or disprove) the assumption that the first move considered is best.

Search optimizations and correctness discipline (45:27)

The lecture surveys existing optimizations in the codebase: move ordering via a sort key, the transposition table with Zobrist hashing, killer-move and best-move tables, null-move pruning, futility pruning, late-move reduction, opening books, and endgame databases. The professor then emphasizes testing discipline for this large, non-trivial codebase: use fixed-depth, deterministic searches and node counts to verify optimizations haven't changed behavior, and keep old and new board representations running side by side during any migration so assertions can catch mismatches before removing the old code.

Live code walkthrough (55:39)

The session closes with a live look at eval.c and the UCI command interface in leiserchess.c, showing how heuristic weights can be tuned through UCI commands without recompiling, and how perft and depth-limited search reveal node counts useful for regression testing.

Before you watch

• Familiarity with alpha-beta pruning or minimax search from a prior algorithms course is helpful but not required, since the lecture explains it from scratch.
• Earlier lectures in this course on parallelism, races, and synchronization are directly relevant, since the final project parallelizes this search.
• This video assumes you have access to the course's Leiserchess project handout to follow the code references.

Check your understanding

1. Why can naively killing an opposing pawn with the laser sometimes lose the game for the player who fired it?
2. What problem does the Ko rule solve, and how does it do so?
3. How does alpha-beta pruning reduce the number of nodes searched compared to a naive full-tree search, and why does move ordering matter for that reduction?
4. What is the core idea behind principal variation search's "scout" (zero-window) searches, and when does it fall back to a full search?
5. Why does the lecture recommend keeping both old and new board representations active during a migration, rather than replacing one outright?