Learning Chess Blindfolded: Evaluating Language Models on State Tracking

Shubham Toshniwal, Sam Wiseman, Karen Livescu, Kevin Gimpel

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.

Introduction

Large language models (LLMs) demonstrate remarkable generative capabilities, yet it remains unclear whether they truly track the underlying "world state" or merely memorize surface-level linguistic patterns. In natural language, the world state is often ambiguous and difficult to define. This study utilizes chess as a "miniature world" to investigate this phenomenon. Chess provides a constrained, deterministic domain where the world state (the board configuration) is perfectly known at every step, allowing researchers to precisely probe a model's internal state tracking by analyzing its ability to predict legal moves and locate pieces.

Methodology

The researchers trained a GPT-2 (small) architecture from scratch using chess games represented in Universal Chess Interface (UCI) notation (e.g., e2e4, e7e5). To enhance the model's ability to learn the board state, they introduced a novel technique called Randomly Annotated Piece type (RAP). During training, piece types are occasionally inserted before a move (e.g., N g1 f3 instead of g1 f3), providing a form of supervision for state tracking that is removed during inference.

Table 1: Comparison of standard UCI notation and various RAP annotation strategies used during training and inference.

The models were evaluated on two primary probing tasks: identifying legal destination squares for a given start square and identifying the current location of a specific piece type. The study utilized the Millionbase dataset, categorized into three training tiers: Train-S (15k games), Train-M (50k games), and Train-L (200k games).

Results and Analysis

Experimental results indicate that Transformers are highly effective state trackers when provided with sufficient data. On the Train-L dataset, the model achieved 97.7% accuracy in predicting legal moves and near-perfect accuracy (99.6% to 100%) in piece tracking.

A key finding was the impact of the RAP technique. As shown in Figure 1, adding piece annotations during training significantly lowered perplexity, particularly for smaller datasets (Train-S and Train-M). This suggests that explicit state information helps the model learn the underlying rules more efficiently, even when that information is absent during testing.

Figure 1: Perplexity vs. RAP probability across different training set sizes. Lower perplexity indicates better predictive performance.

Furthermore, the study highlighted the necessity of "full attention." Despite the Markovian nature of chess, models performed significantly worse when their view of the game history was restricted (e.g., using a sliding window). This implies the model utilizes the entire history to reconstruct the current board state rather than relying on a compressed representation. The most significant bottleneck observed was the "check" constraint; models struggled to recognize moves as illegal if they left the King in check, indicating a difficulty in capturing high-level multi-piece coordination.

Conclusion

This research demonstrates that Transformer language models can learn to track complex world states from simple sequence data, provided they have sufficient scale and full historical context. While the models excel at learning the "physics" or rules of the board, a gap remains between tracking legal moves and mastering optimal strategy. This framework serves as a robust benchmark for evaluating the state-tracking capabilities of future architectural variants.

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{toshniwal2022learning,
  author = {Shubham Toshniwal and Sam Wiseman and Karen Livescu and Kevin Gimpel},
  title = {{Learning Chess Blindfolded: Evaluating Language Models on State Tracking}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i10.21390},
}

Loading related content...

Figure