Overcoming a Learning Bottleneck in Impartial Games: A Circuit Complexity Approach
Søren Riis
cs.AI
Nov 10, 2024 · v4
TL;DR
Core theorems and circuit constructions about NIM, AC^0 simulation and bypass architectures are formalised in Lean (about 24k lines, 1,588 declarations), with classical complexity results assumed as inputs.
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/.
Problem
Neural networks struggle to learn optimal NIM play even though a simple nim-sum algorithm solves it. The paper asks whether this difficulty is a representational bottleneck tied to computing parity.
Approach
Shallow, fixed-scale quantised threshold networks are shown to be simulable in AC^0, which cannot compute parity on unbounded inputs. Three bypasses are then constructed: two-frame inputs for restoration from zero-nim-sum positions, multiple complementary rollout heads, and persistent row-wise recurrence. The core mathematical results and explicit circuit constructions are checked in Lean, with classical complexity results treated as explicit external inputs.
Results
Under fixed latency, single-frame quantised models cannot achieve optimal play at all board sizes, while each bypass restores the needed information or computation using AC^0 components. Supervised experiments show benefits from two-frame restoration and from multiple rollout heads. The Lean development checks 1,588 declarations across 38 files and gives explicit depth bounds for the constructed circuits.
| Component | Boolean depth | Threshold layers |
|---|
| Two-frame binary move selector | ≤ 20 | ≤ 42 |
| Multi-head binary readout, given outcomes | ≤ 19 | ≤ 40 |
| One structured policy's binary move output | ≤ 17 | ≤ 36 |
| One recurrent state update and output | ≤ 8 | ≤ 18 |
| One shootout controller tick | ≤ 34 | ≤ 70 |
Lean-checked depth bounds for constructed components