Chess as a Testbed for Language Model State Tracking

Shubham Toshniwal, Sam Wiseman, Karen Livescu, Kevin Gimpel

This research, presented at AAAI-22, investigates a fundamental question in natural language processing: Do large language models (LLMs) truly "understand" the world state described in a text, or are they merely performing sophisticated surface-level pattern matching? By using chess as a deterministic, constrained "world," the authors demonstrate that Transformers can indeed track complex internal states—provided they have the right training and sufficient attention mechanisms.

The Problem: Measuring "Understanding"

In natural language, the "world state" is often ambiguous. If a model reads a story about a character moving an object, it is difficult to evaluate if the model internally tracks the object's new location without building complex, potentially biased, probing machinery.

Chess offers a perfect alternative. The world state (the board) is 100% known, deterministic, and discrete. By training a model on chess moves, researchers can ask precise questions: Where is the white bishop? Is this move legal? Accuracy in these answers provides concrete evidence of internal state tracking.

Methodology: UCI and RAP

The researchers trained a GPT-2 Small architecture (12 layers, 12 heads) from scratch to predict the next token in a sequence of chess moves. To facilitate this, they employed two key innovations:

  1. UCI Notation: Instead of standard algebraic notation (e.g., Nf3), they used Universal Chess Interface (UCI) notation (e.g., g1f3). This explicitly names the starting and ending squares, allowing the model to be "probed" by providing a starting square and observing if it predicts a legal ending square.
  2. Randomly Annotated Piece type (RAP): To help the model learn piece locations, they occasionally inserted piece identifiers during training (e.g., P, e2, e4).
Table showing the difference between standard UCI and the RAP training notation.

Crucially, RAP tokens create a "scaffold" effect: they are used during training but removed during inference. This tests whether the model has internalized the piece-tracking logic rather than relying on the tokens as crutches.

Experimental Setup and Results

The models were trained on three subsets of the Millionbase dataset: Train-S (15k games), Train-M (50k games), and Train-L (200k games). Evaluation focused on games between 51 and 100 moves long to ensure board complexity.

RAP as a Performance Multiplier

On the smallest dataset (Train-S), standard training resulted in poor state tracking. However, adding RAP tokens during training acted as a powerful supervisory signal. As shown in the data, the RAP method significantly reduced perplexity—a measure of how well the model predicts the data—even when those tokens were absent at test time.

Graph showing how increasing RAP probability reduces perplexity, particularly for smaller datasets (Train-S).

Emergent State Tracking

On the largest dataset (Train-L), the Transformer learned to track piece locations with near-perfect accuracy without ever being explicitly programmed with the rules of chess. Key performance metrics include:

  • Legal Move Accuracy: 97.7% accuracy in predicting a legal ending square for a given piece.
  • Piece Location Tracking: 100% accuracy in identifying the starting square of a piece when trained with RAP.

Key Insights

  • The Necessity of Full Attention: Although chess is technically Markovian (the current board state is sufficient to determine the next move), the Transformer relies on the entire game history to reconstruct that state. Limiting the attention window to the last 50 tokens caused a significant drop in performance.
  • Robustness to Distribution Shift: Unlike LSTMs, Transformers proved remarkably robust to the "distribution shift" caused by training with RAP tokens and testing without them.
  • Strategy vs. Rules: While the model mastered the rules of the world (legal moves), it struggled more with strategy. "Exact Move" accuracy (matching human play) was only around 52%.

Conclusion and Future Work

The findings suggest that "RAP-like" tokens—such as coreference labels or entity tracking markers—could be used during the pre-training of standard LLMs to improve their ability to track the "world state" in natural language documents. However, the reliance on full attention suggests that efficient Transformer variants (like Reformer) might struggle with high-precision state tracking over long sequences.

Summary updated

Abstract

Transformer language models have made tremendous strides in natural language understanding tasks. However, the complexity of natural language makes it challenging to ascertain how accurately these models are tracking the world state underlying the text. Motivated by this issue, we consider the task of language modeling for the game of chess. Unlike natural language, chess notations describe a simple, constrained, and deterministic domain. Moreover, we observe that the appropriate choice of chess notation allows for directly probing the world state, without requiring any additional probing-related machinery. We find that: (a) With enough training data, transformer language models can learn to track pieces and predict legal moves with high accuracy when trained solely on move sequences. (b) For small training sets providing access to board state information during training can yield significant improvements. (c) The success of transformer language models is dependent on access to the entire game history i.e. “full attention”. Approximating this full attention results in a significant performance drop. We propose this testbed as a benchmark for future work on the development and analysis of transformer language models.
BibTeX
@inproceedings{toshniwal2022chess,
  author = {Shubham Toshniwal and Sam Wiseman and Karen Livescu and Kevin Gimpel},
  title = {{Chess as a Testbed for Language Model State Tracking}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i10.21390},
}
Figure