A Chess Program That Chunks

Murray Campbell, Hans J. BerlinerAAAI 1983 · OpenReview

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.

A typical complex king and pawn endgame position handled by CHUNKER.

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.
Examples of specific pawn and king configurations (chunks) used to evaluate positions without deep search.

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

Abstract

CHUNKHR is a chess program that uses chunked knowledge to achieve success. Its domain is a subset of king and pawn endings in chess that has been studied for over 300 years. CHUNKHR has a large library of chunk instances where each chunk type has a property list and each instance has a set of values for these properties. This allows CHUNKHR to reason about positions that come up in the search that would otherwise have to handled by means of additional search. Thus the program is able to solve die most difficult problem of its present domain (a problem that would require 45 ply of search and on the order of 10l3 years of CPU time to be solved by the best of present day chess programs) in 18 ply and one minute of CPU time. Further, CHLINKER is undoubtedly the world's foremost expert in its domain, and has discovered 2 mistakes in the literature and has been instrumental in discovering a new theorem about the domain that allows the assessing of positions with a new degree of ease and confidence. In this paper we describe CHUNKER's structure and performance, and discuss our plans for extending it to play the whole domain of king and pawn endings.1
BibTeX
@inproceedings{campbell1983chess,
  author = {Murray Campbell and Hans J. Berliner},
  title = {{A Chess Program That Chunks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
  url = {https://openreview.net/forum?id=HJZQ5Red-B},
}
Figure