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

Søren Riis

cs.AINov 10, 2024

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

Authors: Søren Riis

Organizations: Centre for Fundamentals of AI and Computational Theory, Queen Mary University of London, London, United Kingdom.

Abstract

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 $\mathrm{AC}^0$ , 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: $\mathrm{AC}^0$ 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/.

Figures & tables

Panel of Figure 1 — Figure 1: The parity barrier and three structural bypasses. (a) Fixed-scale quantised inference (FSQI) with fixed latency cannot compute global parity across arbitrarily large boards. Here fixed latency means a bounded number of sequential computation steps, independent of board size. (b) Two frames expose $\Delta$ for restoration when the predecessor has nim-sum zero. (c) Distinct policy heads recover complementary information through complete rollouts. (d) Persistent recurrence accumulates the nim-sum row by row and retains summaries across positions. Each update has constant depth; the full scan has depth growing with $N$ .

Panel of Figure 2 — Figure 2: A worked restoration example (three heaps). Starting from a $P$ -position $Q$ (green), the opponent changes heap 2 ( $5\to 4$ ), creating a nimber difference $\delta=1$ . The agent instantly restores the $P$ -position by changing heap 1 ( $3\to 2$ ), which imposes the matching difference $3\oplus 2=1$ .

Panel of Figure 3 — Figure 3: A simple finite-state shootout controller for deciding whether $\sigma(P)=\operatorname{nim}(P)$ is zero using the $B$ rollout heads of Proposition 5.9 . The controller queries heads sequentially and halts as soon as it can certify $\sigma(P)\neq 0$ . Reaching the final transition to $\sigma(P)=0$ implicitly means $r_{0}=\cdots=r_{B-1}=0$ .

Resource	What stays in $\mathrm{AC}^{0}$	Additional information or time
One structured channel	Policy step and final readout	One complete rollout; one invariant bit
$B$ structured channels	Each policy step; reconstruction and move selection	$B$ complete rollouts supply all invariant bits
Two-frame transition	Local difference and binary move selection	Previous zero-nim-sum board and a legal transition
Persistent row scan	One state update and its output bits	Two scans per decision; $O(B+\log N)$ state bits

Figure 4: The three bypasses use different resources. Conditional restoration does not classify arbitrary starting positions; the rollout and recurrent constructions supply additional sequential computation.

Component	Type	Dimensions	Activation/Normalisation
Input	State representation	Two-frame: $2Nk$ bits (1F: $Nk$ )	None
Hidden 1	Fully Connected	1F: $Nk\to H$ ; 2F: $2Nk\to H$	LayerNorm + ReLU
Hidden 2	Fully Connected	$H\to H$	ReLU
Policy Head	Linear Output	$H\to N\cdot 2^{k}$	Raw logits; Log-Softmax in loss

Table 1: Neural network architecture used in the experiments.

H

denotes the hidden width (a fixed hyperparameter).

Figure 5: Validation restoration accuracy vs. epoch on the restoration dataset (

N=20

k=4

D=10^{6}

). In this saved run, the 1F model has low accuracy while the 2F model passes through an intermediate plateau around 0.54 before improving sharply towards near-perfect accuracy. The transition suggests a learning bottleneck that training eventually overcomes; it is distinct from the representational lower bound. Values use the saved batch-mean metric.

Figure 6: Test restoration accuracy of checkpointed agents (

N=20

k=4

D=10^{6}

). Checkpoints are saved at epochs

\{1,23,45,67,89,112,134,156,178,200\}

. The 2F checkpoints confirm the improvement beyond the intermediate plateau; the more densely sampled validation curve in Figure 5 shows its timing.

Method	Heads	Rollouts	Accuracy	Recall
Single head (model)	1	1.00	0.768	0.536
Multi-head + FSM (model)	4	2.87	1.000	1.000
Single head (teacher)	1	1.00	0.768	0.536
Multi-head + FSM (teacher)	4	2.87	1.000	1.000

Table 2: Single-frame

P/N

evaluation by FSM-controlled shootouts (

N=20

k=4

), reporting overall

P/N

accuracy and

N

-position recall.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 7 — Figure 7: A schematic of the checked two-frame construction on one legal transition. Boxes group operations, not individual network layers. The general selector also handles multiple candidates, fallback moves and terminal boards.

Panel of Figure 8 — Figure 8: The checked Boolean-to-threshold compiler, shown schematically. Negated input literals are permitted. AND uses an OR of negated inputs followed by negation, keeping weights and thresholds in $\{0,1\}$ . Copying and output stages give a uniform depth bound.

Circuit Complexity

See all 13 papers

Jul 9, 2026

AlphaZero in Sparsely Rewarded Games: Limits and Auxiliary Supervision

AlphaZero has demonstrated that a neural-guided Monte Carlo Tree Search can achieve superhuman performance, but strong play does not necessarily imply perfect play. We study this gap in two oracle-evaluable domains with contrasting structure: Connect Four, a solved partisan game with exact game-theoretic values, and Chomp, an impartial game whose optimal play is governed by Grundy-number structure. Under a unified self-play

+

MCTS pipeline, we compare vanilla AlphaZero, a multi-frame variant (limited to Chomp), and an AlphaZero Auxiliary Loss (AZAL) that adds oracle-derived policy supervision. We find that vanilla AlphaZero achieves strong play across both domains but cannot preserve the exact trajectories required for optimal play: in Connect Four, it fails to maintain the optimal line of play, while in Chomp, it fails to consistently restore the

g=0

invariant. On rectangular Chomp boards, multi-frame inputs alone do not remove this gap. Nevertheless, AZAL substantially improves oracle consistency across multi-seeded full-game traces and sampled-state evaluations. On Chomp, AZAL reaches perfect full-game oracle consistency on 10x11 and high but not complete consistency on 9x10; on Connect Four, AZAL improves oracle-match rate and delays the first oracle mistake, but does not reach perfect play.

Brent Kong, Tejas Ram, Tony Yue Yu

Department of Mathematics · California Institute of Technology · Department of Computer Science

Game-Playing Agents Self-Play RL Game Theory Monte Carlo Tree Search Sparse-Reward RL

Ask PDF

Jul 7, 2026

FootsiesGym: A Fighting Game Benchmark for Two-Player Zero-Sum Imperfect-Information Games

We present FootsiesGym, an open-source environment for learning in a non-trivial two-player, zero-sum, imperfect-information game. Built on HiFight's minimalist 2D fighting game Footsies, it isolates the cyclic, non-transitive strategic interactions of fighting game neutral play while remaining simple enough for efficient analysis. We provide a vectorized simulator that enables high-throughput training on standard hardware, making the environment accessible and reproducible. We describe the design of the environment, benchmark several reinforcement learning algorithms, and discuss open research directions it enables. The code is available at https://github.com/como-research/FootsiesGym.

Chase McDonald, Nathan Tsang, Wesley N. Kerr

Como Research · Riot Games

RL Benchmarks Game-Playing Agents Imperfect-Information Games Zero-Sum Games Agent Benchmarks

Ask PDF

May 16, 2026

From Imitation to Interaction: Mastering Game of Schnapsen with Shallow Reinforcement Learning

This paper investigates whether shallow neural network agents can master the card game Schnapsen and challenge a strong search-based baseline, RdeepBot, which uses Monte Carlo sampling and lookahead search. Guided by a progressively more complex experimental design, we first evaluate a supervised learning agent (MLPBot) trained on replay data and then a reinforcement learning agent (RLBot) with the same shallow architecture trained through asynchronous Monte Carlo updates and experience replay. The results show that supervised imitation does not generalize well enough to defeat strong RdeepBot opponents, whereas reinforcement learning produces substantially stronger agents. In the setting that focuses on the depth parameter of RdeepBot, the best performance is achieved when the learned value function is combined with deeper lookahead during gameplay, allowing RLBot to achieve statistically significant higher winning rates against the strongest evaluated RdeepBot baseline. In the sample-based setting, the gains are more conditional: the strongest performance appears at a relatively lower training num_samples parameter rather than increasing uniformly with stronger sampling.

Ján Klačan, Sizhong Zhang

Vrije Universiteit Amsterdam

Reinforcement Learning Game-Playing Agents Imperfect-Information Games Imitation Learning

Ask PDF

Abstract

Circuit Complexity

Explore similar work

AlphaZero in Sparsely Rewarded Games: Limits and Auxiliary Supervision

FootsiesGym: A Fighting Game Benchmark for Two-Player Zero-Sum Imperfect-Information Games

From Imitation to Interaction: Mastering Game of Schnapsen with Shallow Reinforcement Learning