In 2007, Jonathan Schaeffer and his research team at the University of Alberta announced a monumental breakthrough in computational game theory: the complete mathematical solution of English draughts (8x8 checkers). With a state space cardinality of 5.002 × 1020, checkers represents the largest game solved to date. The formal proof established that optimal play by both adversaries inexorably leads to a draw.
1. 32-Bit Bitboard Representation and SIMD Operations
Because the 32 playable dark squares on an 8x8 checkers board map compactly into four 8-bit octets, a complete board state can be encoded within a single 32-bit unsigned integer (uint32) or four 32-bit registers representing Black Men, Black Kings, White Men, and White Kings:
typedef struct {
uint32_t bm; // Black men
uint32_t bk; // Black kings
uint32_t wm; // White men
uint32_t wk; // White kings
} BoardState;Jumps and diagonal shifts are computed in parallel across the entire board using bitwise shifts (shifts of 3, 4, and 5 bits across alternating rows). This representation maximizes CPU cache locality and eliminates branch overhead during legal move generation.
2. Retrograde Analysis and Endgame Database Construction
The linchpin of solving checkers was retrograde analysis—working backward from terminal game positions (checkmate, draw by rule, or material exhaustion) to determine exact theoretical outcomes for precursor states. Schaeffer’s team computed complete endgame databases for all configurations containing up to 10 pieces, comprising 39 trillion positions (3.9 × 1013).
Each position in the retrograde tablebase stores distance-to-conversion metrics, compressed using Huffman encoding and run-length schemes that reduce memory footprint to sub-byte averages per state.
3. Proof-Number Search and Transposition Table Optimization
For positions beyond the 10-piece endgame tablebases, the Chinook solver employed Proof-Number Search (PNS), an algorithm explicitly designed for finding game-theoretic values in AND/OR game trees. Unlike heuristic minimax search which estimates static evaluation scores, PNS tracks two properties for every node:
- Proof Number (p): The minimum number of leaf nodes that must be proven true to establish the node's value.
- Disproof Number (d): The minimum number of leaf nodes that must be disproven to refute the node.
Modern browser implementations, such as the Checkers Crown web platform, leverage optimized 32-bit bitboard state evaluation and opening book heuristics to provide low-latency, master-strength play directly across mobile and desktop clients.
Conclusion
The computational solution of checkers bridges combinatorial game theory and large-scale distributed computing. It remains a masterclass in how bitboard architectures, retrograde indexing, and proof-number pruning can conquer astronomical state spaces.