# Impartial Games: A Challenge for Reinforcement Learning

arXiv: https://arxiv.org/abs/2205.12787 · HTML: https://mlsanity.com/paper/2205.12787/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 77 references that are in the map.
- First posted on arXiv 25 May 2022.

## Builds on (most cited first, 23 of 23)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Ray: A Distributed Framework for Emerging AI Applications](https://mlsanity.com/paper/1712.05889/) (2017)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [PonderNet: Learning to Ponder](https://mlsanity.com/paper/2107.05407/) (2021)
- [Transformer Language Models without Positional Encodings Still Learn Positional Information](https://mlsanity.com/paper/2203.16634/) (2022)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [Learning Parities with Neural Networks](https://mlsanity.com/paper/2002.07400/) (2020)
- [Accelerating Self-Play Learning in Go](https://mlsanity.com/paper/1902.10565/) (2019)
- [Do RNN and LSTM have Long Memory?](https://mlsanity.com/paper/2006.03860/) (2020)
- [ELF OpenGo: An Analysis and Open Reimplementation of AlphaZero](https://mlsanity.com/paper/1902.04522/) (2019)
- [Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning](https://mlsanity.com/paper/1602.05161/) (2016)
- [Regularizing Towards Permutation Invariance in Recurrent Models](https://mlsanity.com/paper/2010.13055/) (2020)
- [Polygames: Improved Zero Learning](https://mlsanity.com/paper/2001.09832/) (2020)
- [Chess AI: Competing Paradigms for Machine Intelligence](https://mlsanity.com/paper/2109.11602/) (2021)
- [A Novel Approach to Solving Goal-Achieving Problems for Board Games](https://mlsanity.com/paper/2112.02563/) (2021)

## Built on by (most cited first, 3 of 3)

- [Exploring Parity Challenges in Reinforcement Learning through Curriculum Learning with Noisy Labels](https://mlsanity.com/paper/2312.05379/) (2023)
- [Overcoming a Learning Bottleneck in Impartial Games: A Circuit Complexity Approach](https://mlsanity.com/paper/2411.06403/) (2024)
- [AlphaZero in Sparsely Rewarded Games: Limits and Auxiliary Supervision](https://mlsanity.com/paper/2607.08984/) (2026)

## Abstract (arXiv)

AlphaZero-style reinforcement learning (RL) algorithms have achieved superhuman performance in many complex board games such as Chess, Shogi, and Go. However, we showcase that these algorithms encounter significant and fundamental challenges when applied to impartial games, a class where players share game pieces and optimal strategy often relies on abstract mathematical principles. Specifically, we utilise the game of Nim as a concrete and illustrative case study to reveal critical limitations of AlphaZero-style and similar self-play RL algorithms. We introduce a novel conceptual framework distinguishing between champion and expert mastery to evaluate RL agent performance. Our findings reveal that while AlphaZero-style agents can achieve champion-level play on very small Nim boards, their learning progression severely degrades as the board size increases. This difficulty stems not merely from complex data distributions or noisy labels, but from a deeper representational bottleneck: the inherent struggle of generic neural networks to implicitly learn abstract, non-associative functions like parity, which are crucial for optimal play in impartial games. This limitation causes a critical breakdown in the positive feedback loop essential for self-play RL, preventing effective learning beyond rote memorisation of frequently observed states. These results align with broader concerns regarding AlphaZero-style algorithms' vulnerability to adversarial attacks, highlighting their inability to truly master all legal game states. Our work underscores that simple hyperparameter adjustments are insufficient to overcome these challenges, establishing a crucial foundation for the development of fundamentally novel algorithmic approaches, potentially involving neuro-symbolic or meta-learning paradigms, to bridge the gap towards true expert-level AI in combinatorial games.