# Overcoming a Learning Bottleneck in Impartial Games: A Circuit Complexity Approach

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 57 references that are in the map.
- First posted on arXiv 10 Nov 2024.

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

- [Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference](https://mlsanity.com/paper/1712.05877/) (2017)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [On the Spectral Bias of Neural Networks](https://mlsanity.com/paper/1806.08734/) (2018)
- [LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale](https://mlsanity.com/paper/2208.07339/) (2022)
- [Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks](https://mlsanity.com/paper/1901.06523/) (2019)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [Learning Parities with Neural Networks](https://mlsanity.com/paper/2002.07400/) (2020)
- [Impartial Games: A Challenge for Reinforcement Learning](https://mlsanity.com/paper/2205.12787/) (2022)
- [Exploring Parity Challenges in Reinforcement Learning through Curriculum Learning with Noisy Labels](https://mlsanity.com/paper/2312.05379/) (2023)

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

- [AlphaZero in Sparsely Rewarded Games: Limits and Auxiliary Supervision](https://mlsanity.com/paper/2607.08984/) (2026)

## Abstract (arXiv)

Why can neural networks struggle to learn optimal play in a game with a simple, efficient solution algorithm? Motivated by empirical difficulties with parity in impartial games, we use NIM to study a representational bottleneck and three ways around it. We show that a restricted model of shallow, fixed-scale quantised networks lies in AC0, a circuit class unable to compute parity on arbitrarily large inputs. This prevents optimal single-position play across all board sizes within the model. The obstruction also guides architectural design: two-frame inputs allow restoration from a known zero-nim-sum position; complementary rollout policies reveal the missing invariant; and persistent recurrence accumulates it row by row. Each route retains shallow network components while supplying additional information or processing time. Supervised experiments illustrate the benefits of two-frame restoration and multiple rollout heads; recurrence is a theoretical construction. These results establish representational possibilities, not guarantees of successful training: AC0 does not characterise practical learnability. Core mathematical results and constructions have been checked in Lean, with classical complexity results as explicit external inputs. The interactive edition and complete Lean sources are available online at https://sr123.github.io/impartial-games-learning-lean/.