RetroChessBench: A Benchmark for Reconstructing and Proving Chess Histories

Tidor-Vlad PricopearXiv 2026 · arXiv

TL;DR

RetroChessBench is a new benchmark designed to test the limits of frontier language models like GPT-6 Astra through retrograde chess analysis—the art of reconstructing a game's history from a final position. Despite their prowess in mathematics and forward-play chess, these models struggle significantly with historical reasoning, often mistaking temporary board obstructions for permanent constraints and failing to prove the uniqueness of their solutions.

What Problem Does This Paper Address?

While large language models (LLMs) have shown remarkable progress in mathematical reasoning, there is a lingering question: are they truly reasoning from first principles, or are they just very good at recognizing familiar solution patterns?

The authors propose retrograde chess as a "playground for pure reasoning." Unlike standard chess, which focuses on finding the best next move, retrograde analysis asks: How did we get here? This requires a model to reason consistently over hidden histories, distinguish between what could have happened and what must have happened, and strictly adhere to the rules of chess in reverse.

The core challenge is historical exclusion. To prove a specific move was the last one made, a model must not only find a legal history for that move but also prove that no other legal history exists. As shown in the paper, even the most advanced models often fail this "standard of proof."

Table 1: An example of a model failing to account for alternative event orders.

Methods

The researchers introduced RetroChessBench, a 12-task benchmark consisting of three distinct proof obligations:

  1. Exact-length constructive proof games: Reconstruct a legal sequence of a specific number of plies (half-moves) that leads to the target position.
  2. Unique suffixes: Determine the final few moves of a game, proving that no other sequence is legally possible.
  3. Exhaustive alternative endings: Identify all possible last moves and provide a feasible history for each.

The evaluation uses a terminal-reward Reinforcement Learning (RL) environment. Models are tested in two conditions: "no code" (pure text reasoning) and "code enabled" (access to a Python interpreter). To grade the quality of the natural-language proofs, the authors employed an "LLM-as-a-judge" (using GPT-6 Astra High) guided by frozen, expert-reviewed rubrics.

Datasets

  • RetroChessBench: The primary dataset, featuring 12 tasks selected from a candidate pool of 48. These tasks were adapted from StrateGems compositions, including modifications to reduce the chance of models relying on memorized solutions from training data.
  • Comparison Benchmarks: The paper situates RetroChessBench alongside other reasoning benchmarks like LongCoT (reverse chess), PlanBench (planning), and MathConstruct.
Table 2: How RetroChessBench compares to existing evaluation settings.

Key Insights and Ideas

  • The "Temporary Lock" Fallacy: A recurring failure mode is when models treat a piece currently occupying a square as a permanent obstruction. For example, a model might claim a Bishop couldn't have reached a certain square because a Pawn is in the way, forgetting that the Bishop could have passed through that square before the Pawn arrived.
  • Existence vs. Uniqueness: Models are much better at finding one possible history (existence) than they are at proving it is the only history (uniqueness).
  • Training Data Gaps: The authors hypothesize that while the web contains many chess puzzles and their solutions, it lacks detailed, step-by-step retrograde derivations. This lack of "worked examples" in training data exposes the models' inability to transfer general principles to novel, rule-governed domains.
  • Code is Not a Panacea: While code execution improved the success rate for constructive tasks, it did not significantly help models with the analytical "exclusion" arguments required for uniqueness proofs.

Key Results

The researchers evaluated GPT-6 Astra High, a model with a reported Elo of 1745 in forward chess. The results were sobering:

  • Failure Rates: Without tools, the model failed to provide the correct final answer in 22 out of 24 attempts. With code execution, it still failed in 18 out of 24 attempts.
  • Mean Rewards: The mean terminal RL rewards were just 14.75% (no code) and 27.19% (code enabled).
  • Constructive Tasks: The model failed all 14 attempts at exact-length game construction without code. With code, it successfully completed only 2 out of 14.
  • Proof Quality: Even when the model correctly identified a unique suffix, it often failed to provide a complete proof. Only 1 out of 8 correct code-enabled suffix answers received full proof credit.
Figure 1: Two adapted short-answer tasks. R01 changes Frolkin’s R0185 from eight to six single moves and relocates White’s rook from h8 to g8. R02 changes Beluhov’s R0176 from forty to five single moves, with no change to the diagram. Both retain the central historical proof challenge and assume legal reachability. The solver receives both the diagram and its FEN placement.

Limitations and Future Work

The authors acknowledge several limitations:

  • Scale: The benchmark is small (12 tasks), and the tasks were adaptively selected based on observed model failures, which might introduce selection bias.
  • Compute Unmatched: The "code enabled" runs used significantly more tokens and compute than the "no code" runs, making a direct causal comparison difficult.
  • Ground Truth: While constructive games can be automatically verified, uniqueness proofs still rely on natural-language rubrics and human-reviewed AI judges.

Future Work includes expanding the benchmark with newly composed problems to eliminate the possibility of memorization, and developing "supplied-suffix" diagnostics to test if models can justify a forced ending even when the answer is given to them.

Summary updated

Abstract

Frontier language models such as GPT 6 Astra have contributed to research mathematics, demonstrating substantial reasoning capabilities. Yet serious reasoning failures persist even in tasks governed by explicit rules. We demonstrate this in retrograde chess which is a playground for pure reasoning, where solvers reconstruct legal histories and distinguish possible events from forced ones. We introduce RetroChessBench, a 12-task benchmark covering exact-length constructions, unique endings, and exhaustive answer sets, with references, rubrics, and a terminal-reward environment. In two trials per task and condition, GPT 6 Astra High fails to produce the required final answer in 22/24 attempts without tools and 18/24 with code execution; mean terminal RL rewards are 14.75% and 27.19%, respectively. The examples identify faulty deductions: failed responses reject legal histories and treat temporary obstructions as permanent. Online retrograde archives often provide puzzles and final move sequences without detailed derivations. We hypothesize that limited exposure to these missing explanations in web-derived training data contributes to the observed reasoning failures. This questions how far frontier mathematical reasoning really generalizes beyond familiar solution patterns. Claims of general intelligence require evidence that models can transfer learnt principles to areas with few worked examples.
BibTeX
@misc{pricope2026retrochessbench,
  author = {Tidor-Vlad Pricope},
  title = {{RetroChessBench: A Benchmark for Reconstructing and Proving Chess Histories}},
  year = {2026},
  eprint = {2610.39341},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.39341},
}
Figure