Chess Programming Guide

These pages are my notes from building ChessML, a chess engine I write in OCaml for fun and to learn. Each page explains one technique the way I understand it and then shows what ChessML actually does, including its shortcuts. I am a novice at this, so treat them as study notes, not as a reference; the real reference is the Chess Programming Wiki, and each page links the articles it leans on.

I have not measured how much each technique is worth in ChessML, so the pages do not put numbers on it. The only strength figure I have is the rough estimate in the README.

Representing the board

  • Bitboards: the board as 64-bit integers, one bit per square, and the handful of bit tricks that make them useful.
  • Magic Bitboards: how rook and bishop attacks, which depend on what is in the way, become a single table lookup.
  • Zobrist Hashing: a 64-bit key per position that is cheap to update move by move. ChessML uses the Polyglot keys, so the same key works for the opening book.

Searching

  • Alpha-Beta Pruning: searching the game tree while skipping moves that cannot change the result. With good move ordering it visits roughly the square root of the positions plain minimax would, which is why everything else on this list matters.
  • Transposition Tables: remembering positions already searched, since the same position is often reached by different move orders.
  • Quiescence Search: continuing with captures at the end of the search, so the engine does not stop counting in the middle of an exchange.
  • Null Move Pruning: if passing the turn still leaves me winning, the position is probably good enough to stop searching.
  • Late Move Reductions: searching the moves that come late in the ordering less deeply, and re-searching if one turns out to be good.

Choosing which move to try first

  • Move Ordering: the hash move, captures, killer moves, history and countermoves, in that kind of order. Alpha-beta only prunes well if the best move tends to come first.
  • Static Exchange Evaluation: working out whether a capture wins or loses material without searching it.

Judging a position

  • Evaluation Function: turning a position into a score: material, piece-square tables, pawn structure, king safety and some endgame knowledge.

Openings

  • Opening Books: the Polyglot book format and how ChessML builds its own book from a collection of games.

Endgames

  • Basic Endgames: recognizing the basic endgames by their material, the mates against a lone king, and a computed table for king and pawn against king.

The order I would read them in

If you are new to this too, this is the order that made sense to me:

  1. Bitboards
  2. Alpha-Beta Pruning
  3. Evaluation Function
  4. Quiescence Search
  5. Move Ordering
  6. Zobrist Hashing and Transposition Tables
  7. Magic Bitboards
  8. Static Exchange Evaluation
  9. Null Move Pruning and Late Move Reductions
  10. Opening Books
  11. Basic Endgames

For how the code itself is organized, see the Developer Guide.

Sources

Table of contents