Abstract
CHUNKER is a chess program that utilizes chunked knowledge to achieve success in complex king and pawn endings. By employing a library of chunk instances with specific property lists, the program reasons about positions that would otherwise require massive search depth. CHUNKER can solve problems requiring 45 ply of search—estimated to take $10^{13}$ years for standard brute-force engines—in just 18 ply and one minute of CPU time. The program has even corrected errors in authoritative chess literature and helped discover new theorems for position assessment.
Introduction
In the early 1980s, computer chess was defined by the "brute-force" paradigm: searching as many moves (ply) as possible using alpha-beta pruning. However, certain endgames, particularly king and pawn endings, present "search horizons" far beyond the capabilities of contemporary hardware. This paper presents CHUNKER, a program developed at Carnegie-Mellon University that trades raw computational power for human-like pattern recognition.
The Problem of Search Horizons
A position in a king and pawn endgame might require 45 ply of search to resolve. The authors estimated that a state-of-the-art program of the time, such as Belle, would require roughly $10^{13}$ years of CPU time to solve such a problem. Humans, by contrast, solve these by "chunking" — grouping pieces into logical units like "connected passed pawns" and reasoning about their functional properties rather than calculating every possible move.
The CHUNKER Architecture
CHUNKER operates on a hierarchical system that moves from standard search to increasingly abstract knowledge:
- Level 0: A standard full-width, depth-limited alpha-beta search.
- Levels 1-3 (The Libraries): The core innovation. Using retrograde enumeration, the authors pre-calculated properties of specific piece configurations (chunks). These libraries handle "Alternating Moves" (AM), "Pawns-Can-Pass" (PCP), and "King-Can-Pass" (KCP) scenarios.
- Level 4 (Spare Tempi): Uses library values to calculate the number of free moves a king has before a pawn breakthrough occurs.
- Level 5 (Z-Configurations): Implements mathematical theorems regarding "double-win" positions where pawns win regardless of whose turn it is.
The program "parses" a board into these chunks, looks up their properties in the libraries, and uses that data to terminate search branches early or evaluate positions with near-perfect accuracy.
Key Results and Insights
CHUNKER's performance in the domain of King vs. 3 Connected Passed Pawns (Kv3CPP) was transformative:
- Massive Speedups: In the most difficult test position (547), CHUNKER solved in 18 ply and one minute what would have required 45 ply for a standard program.
- Node Reduction: For position 545, the Level 0 search required 940,534 nodes. With Level 5 knowledge, it required only 25 nodes.
- Correcting the Masters: CHUNKER proved its expert status by finding two errors in Averbakh and Maizelis’s Pawn Endings (1974), positions that human masters had misanalyzed for years.
- Functional Chunking: Chunks are defined by "functional considerations" — assemblages required to assess a specific outcome — rather than arbitrary groupings.
Conclusion and Future Work
CHUNKER demonstrates the "Knowledge Power" hypothesis: adding relevant schemas can drop the search space for specific problems from hundreds of thousands of nodes to a single node. While CHUNKER was a narrow expert, the authors estimated that covering the entire domain of king and pawn endings would require 60 to 100 reasoning schemas and about 30 distinct piece properties. This work highlights a path for AI to move beyond brute force toward conceptual expertise.
Summary updated