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

Keywords: Impartial games; NIM; circuit complexity; quantised inference; learning bottlenecks.

1 Introduction

Game play has historically served as the “Formula 1” of artificial intelligence: a high-speed, controlled proving ground where engineering limits are tested and new paradigms are born. From Deep Blue in chess to AlphaGo in Go, games have repeatedly driven advances in search, planning, and reinforcement learning (Silver et al., 2016, 2017, 2018; Schrittwieser et al., 2020). Minsky and Papert’s analysis of perceptron limitations illustrates how representational restrictions can motivate architectural changes (Minsky and Papert, 1969).

In NIM, two players take turns removing any positive number of tokens from a single heap; the player taking the last token wins. It belongs to the broad class of impartial games: both players have the same legal moves from a given position. Many such board games can be thought of as games with shared pieces, whereas in partisan games, such as chess, legal moves depend on which player is to move. NIM is central to impartial-game theory because every finite terminating impartial position under the last-move-wins convention is equivalent, in sums of games, to a single NIM heap (Section 4).

NIM poses a particularly revealing challenge: optimal moves can be found by a simple, efficient algorithm, yet learning that algorithm can be difficult. The puzzle is the gap between the ease of computing the solution once the rule is known and the difficulty of discovering it through training. Friedman’s 2017 AI challenge asked whether a system could discover perfect NIM play without being given the winning strategy (Friedman, 2017a).

Our earlier work with Bei Zhou provides the empirical starting point. In Impartial Games: A Challenge for Reinforcement Learning, Zhou and Riis found that AlphaZero-style learning deteriorated as NIM boards grew (Zhou and Riis, 2026). Subsequent parity experiments examined how noisy labels can obstruct curriculum learning (Zhou and Riis, 2023); see also Zhou’s thesis (Zhou, 2024). These findings make parity a useful test of the gap between learning familiar patterns and discovering an exact rule that works across positions.

Here we turn that difficulty into a question about computation. The class $\AC^0$ consists of polynomial-size Boolean circuits built from AND, OR and NOT gates, with a number of layers that remains fixed as the input grows. Such circuits can combine many local tests, but cannot compute global parity: whether the total number of input 1s is odd or even. This is the feature that makes the class useful here: it provides a precise model with a provable version of the parity limitation seen in the experiments. We establish the connection for an explicitly restricted neural model, rather than assuming that all neural networks lie in $\AC^0$.

The value of identifying a bottleneck is that it tells us what an architectural change must supply. Instead of asking a shallow network to rediscover a global invariant from every board, we can expose a useful transition, obtain complementary information from rollouts, or accumulate the invariant over time. Our contribution is this barrier-to-bypass approach: a computational obstruction guides three concrete constructions. Representability in $\AC^0$ is a necessary condition for a fixed-latency computation in our restricted model; it is neither sufficient for successful training nor a universal condition on what neural networks can learn.

NIM itself does not depend on game history: the current position completely determines its legal moves and optimal play. History can nevertheless supply useful computational context to a restricted network. The first and third bypasses use such context in different ways: an earlier board exposes a local change, while recurrent memory retains information accumulated during row processing and across positions.

The central observation is that while the state can be hard to process, the transition can be easy: under the promise that the preceding position has nim-sum zero, short history converts winning-move selection into local difference computation and restoration. A second route uses distinct rollout policies to extract complementary bits of the invariant. A third route processes each position sequentially, retaining recurrent state as rows and then successive positions arrive. Here a sequence of simple updates computes the global invariant, and memory connects the new position to the preceding one. These mechanisms use different resources: explicit transition information, multiple rollout channels, or a growing recurrent computation horizon. The distinction between a shallow component and the complete computation is essential. Two-frame restoration is a shallow map on a promised pair of boards. In the other two constructions, each policy step or recurrent update is shallow, but generating the information needed for a decision takes a sequence of such steps. Thus the bypasses preserve simple network components while changing the input information or total processing time. The complete sequential computation need not itself lie in $\AC^0$. Figure 1 summarises the three routes for NIM.

1.1 Contributions

The results follow a single question: what must be added to a shallow learner to make the required strategy representable? We first identify the obstruction, then show how each bypass supplies a different missing resource.

• $\AC^0$ containment for fixed-scale quantised inference. We formalise a fixed-grid Boolean literal-threshold model and its bounded-unrolling recurrent extension. Both are simulable by $\AC^0$ circuits (Theorem 2.4). An attention-style extension is covered only if its scoring, selection and aggregation operations can each be implemented by the permitted Boolean threshold gates. This is a restriction on the computation, not a requirement that every game have the same board size. Within a play sequence we use a fixed layout of $N$ heap rows and $B$ bits per heap, retaining empty heaps as zero rows. The asymptotic statements concern families of networks for growing input lengths $NB$.

• Single-frame impossibility for strong mastery. Under this model, no single-frame policy/value network can strongly master NIM in the worst case (Theorem 5.2).

• Two-frame bypass via local differences and restoration. With two consecutive frames, the agent can compute $\Delta(P,P')$ in $\AC^0$ (Lemma 5.4). When $P$ has nim-sum zero, an $\AC^0$ move selector restores zero after the opponent’s move (Proposition 5.5). This is conditional restoration mastery, not an arbitrary-start verifier.

• Planning analysis and the single-policy bottleneck. We analyse a restricted measurement interface inspired by rollouts, rather than a general model of MCTS. With $B$ structured policies one can recover all nim-sum bits (Proposition 5.9). Root and one-heap-modification queries to one fixed member of that family expose only one unknown linear functional (Proposition 5.10). With an explicitly bounded readout, this yields the distributional bound in Theorem 5.12.

• Persistent recurrence via sequential row updates. A constant-depth recurrent update accumulates the nim-sum over $N$ heap rows and retains a summary across position separators (Proposition 5.13). With a replay of the current board or stored heap rows, this supports optimal move selection. The construction relaxes fixed total latency, not fixed-scale quantisation (Section 5.5).

• Controlled empirical comparison and learnability discussion. On 20-heap, 4-bit NIM with $10^6$ supervised restoration examples, a one-frame model has low restoration accuracy while a two-frame model learns restoration (Section 7.2). In a complementary single-frame experiment, multi-head FSM-controlled shootouts achieve perfect win/loss position classification while the single-head baseline remains bottlenecked by one-bit information (Section 7.3). We also discuss why $\AC^0$ is a useful abstraction for what is robustly feasible under fixed-scale quantised inference (Section 6.3).

1.2 Scope and limitations

Our theorems are worst-case representational statements about what can be computed under explicit architectural constraints. They are not training-complexity results, and they intentionally abstract away from several practical details, such as continuous-valued activations, floating-point arithmetic, normalisation layers and the dynamics of optimisation.

• Fixed-scale quantisation / fixed latency. The $\AC^0$ simulation (Theorem 2.4) assumes constant depth and a fixed-scale, bounded-range quantisation regime: weights/thresholds lie on a fixed grid whose range/resolution do not scale with the input length (cf. Remark 2.2). Architectures that rely on fan-in dependent re-normalisation, biases/thresholds growing with dimension, or depth growing with $n$ fall outside this abstraction. In particular, a fixed recurrent update rule need not have fixed total latency: the third bypass deliberately allows $N$ successive row updates per position.

• Formal model vs. experimental networks. The formal units have nonnegative weights on Boolean literals and bounded thresholds. The experiments instead use ordinary floating-point signed linear layers, ReLU and LayerNorm, with Log-Softmax in the loss. They test the benefit of transition information under the reported training protocol, not the asymptotic lower bound or the deployment behaviour of quantised networks.

• Stylised planning interface. The single-channel lower bound permits only root and one-heap-modification queries to a fixed structured policy, and requires a polynomial-size, constant-depth final readout. It is not a bound on arbitrary rollout policies, unrestricted query transformations, or an unbounded adaptive MCTS controller.

• No guarantee of learnability. The multi-policy-head and recurrent constructions concern existence of suitable computations; we do not claim that self-play efficiently discovers the structured heads or an exact recurrent accumulator. Our experiments use controlled supervised restoration and policy imitation; self-play discovery is left for a separate study.

1.3 Paper organisation

Section 2 introduces the fixed-scale quantised inference model and the $\AC^0$ simulation theorem. Section 3 situates our contribution in circuit complexity, modern sequence models, and reinforcement learning for combinatorial games. Section 4 recalls NIM and the nim-sum characterisation. Section 5 presents the main impossibility and bypass results: two-frame restoration, rollout channels (Section 5.4), and persistent recurrence (Section 5.5). Section 6 discusses modelling choices and learnability considerations. Section 7 reports experiments. Appendices contain formal model definitions and proofs.

2 Theoretical framework and neural network models

2.1 Fixed-scale quantised inference and $\AC^0$ simulation

We consider neural inference models that are (i) bounded depth, (ii) polynomial size, and (iii) operate in a fixed-scale quantised regime: all weights and thresholds lie on a fixed quantisation grid of bounded dynamic range that does not change with the input length. The fixed scale is motivated by limits on the effective precision of neural computation, including sensitivity to noise: distinctions that can be used reliably may be much coarser than the rounding resolution of 32-bit floating-point arithmetic. Noise motivates this abstraction; it does not by itself imply the gate and threshold assumptions below.

Our Boolean threshold gates sum nonnegative weights on inputs that may be negated. Negation allows inhibitory as well as excitatory effects: for a Boolean input $x$, the identity $-ax=a(1-x)-a$ replaces a negative coefficient by a positive weight on the negated input, with an adjustment to the threshold. The substantive restriction is that the resulting weights and thresholds remain on the fixed, bounded grid; this is not a model of arbitrary signed-weight or INT8/fixed-point inference.

Concretely, we fix constants:

• a quantisation resolution parameter captured by a fixed denominator $D\in\N$ (grid step $1/D$),

• a dynamic-range bound $W\in\N$ (maximum magnitude $W/D$),

• and (for recurrent/attention models) a finite time window $T\in\N$.

We define $$\Qset_{W,D} \;=\; \Big\{ \frac{\ell}{D}\ :\ \ell\in\{0,1,2,\dots,W\}\Big\},$$ a finite set independent of input length. The threshold bound applies after choosing the literal representation. Replacing a signed term $-a x$ by $a(1-x)$ raises the threshold by $a$. With many such terms, the adjusted threshold may grow with the input length. What matters is the amount of evidence needed to activate a gate: our model bounds the number of satisfied input literals that suffice, whereas an unrestricted majority gate needs a number that grows with its inputs. Negative coefficients themselves are not the obstruction; the bound on the adjusted threshold is essential to the simulation.

Each neuron computes a thresholded weighted sum of Boolean inputs. Formal definitions for $\NN$, $\RNN$ and $\LTST$ are in Appendix A.

A bound on the number of preceding states consulted by one update is insufficient: even $h_{r+1}=h_r\oplus x_r$ can accumulate parity over an arbitrarily long stream. Section 5.5 exploits precisely this distinction by allowing the number of recurrent updates to grow with the number of rows.

Why fixed-scale quantisation suggests an $\AC^0$ abstraction. The key structural property is fixed scale: the smallest nonzero weight is $1/D$ and the largest threshold is $W/D$, with $W,D$ independent of the input length. Consequently, whenever a threshold unit outputs $1$, there is a satisfying witness consisting of at most $W$ input literals whose contributions already cross the threshold. This yields a constant-width DNF expansion for each unit (Lemma B.1), and composing a constant number of layers yields an $\AC^0$ simulation (Theorem 2.4).

We emphasise that this is not a statement about floating-point arithmetic per se. The abstraction intentionally excludes scale-adaptive regimes where thresholds/biases grow with fan-in or where weights shrink with dimension (e.g. $1/n$ or $1/\sqrt{n}$ normalisations), which move the analysis toward threshold-circuit classes such as $\TC^0$. This class allows constant-depth, polynomial-size circuits with general threshold gates, including majority gates; unlike $\AC^0$, it can compute parity.

Notation convention (input length). We write $N$ for the number of heaps and $B$ (or $k$ in experiments) for the bit-width used to encode each heap size. The resulting Boolean input length is $n := NB$. When we discuss $\AC^0$ circuit size/depth, $n$ always refers to this Boolean input length.

Circuit complexity primer. $\AC^0$ is the class of Boolean functions computable by constant-depth, polynomial-size circuits with unbounded fan-in AND/OR/NOT gates. A classical result is that $\mathrm{PARITY}\notin\AC^0$. In contrast, $\TC^0$ augments $\AC^0$ with unbounded fan-in threshold gates and can compute parity. Our focus here is a fixed-scale quantised regime in which thresholds do not scale with fan-in; in that regime, each threshold unit admits a constant-witness DNF expansion and the overall computation collapses to $\AC^0$ (Theorem 2.4).

2.2 Simulation by circuits

We state the simulation theorem for the literal-threshold model and its explicitly gate-realised extensions.

3 Related Work

Circuit complexity and neural networks. Parity is outside $\AC^0$ (Furst et al., 1984; Håstad, 1986), while constant-depth threshold circuits ($\TC^0$) can compute it. Attention results depend on the precise model: Hao, Angluin and Frank analyse hard-attention variants, including $\AC^0$ restrictions for unique hard attention (Hao et al., 2022). Merrill and Sabharwal study the additional power of intermediate decoding over a $\TC^0$ baseline (Merrill and Sabharwal, 2024); that containment does not rule out parity. Their sequential-computation perspective is relevant to our recurrent bypass, although the architectures and formal assumptions differ. Our contribution applies these distinctions to NIM policies and a restricted rollout-measurement interface.

Quantised inference and deployment constraints. Low-bit inference motivates studying bounded numerical resources (Jacob et al., 2018; Dettmers et al., 2022). Our constant-witness proof additionally requires nonnegative literal weights, bounded thresholds and Boolean intermediate states. These are explicit mathematical assumptions, not properties inferred merely from a quantisation format. Standard signed linear layers and scale-adaptive normalisation are outside the theorem unless separately reduced to the permitted gates.

Reinforcement learning in combinatorial games. While RL has mastered domains such as Go and chess, impartial games remain a useful stress test because optimality is governed by exact algebraic invariants rather than approximate pattern matching. Zhou and Riis (Zhou and Riis, 2026, 2023) studied reinforcement-learning difficulties in impartial games. Our lower bound identifies a representational obstruction in a restricted model; determining which mechanisms explain failures in ordinary neural training requires separate experiments.

History and memory in RL. Using short history windows is standard in partially observable settings, where stacked frames recover hidden variables such as velocity (Mnih et al., 2015). Our point is different and perhaps surprising: even in Markovian, fully observable games—where the current state is informationally sufficient and the past is theoretically irrelevant—history can reduce computational complexity by exposing local differences that would otherwise require expensive search or unbounded-depth inference to extract from the current state alone. In our restoration setting, the previous frame carries a promise established by an earlier successful move: its nim-sum is zero. That promise makes a local difference sufficient for the next response. Establishing the promise initially remains a separate computational task.

4 Impartial games and NIM

We briefly recall standard definitions; see (Berlekamp et al., 2001–2004) for extensive background.

4.1 Impartial games

A position with no legal moves is terminal.

The last-move-wins convention also provides a convenient encoding of other decisive endings. A move that wins by capturing a designated piece or creating a specified configuration can simply lead to a position with no further legal moves. If instead reaching a special position loses for the player who made the move, give the opponent one forced move to a new terminal position. These encodings preserve the winner of the individual play; they must retain player-independent move rules to remain impartial. The theory below concerns the resulting normal-play game.

4.2 NIM

4.3 Sprague–Grundy theory and nim-sum

The breadth of impartial games makes the Sprague–Grundy theorem remarkable: every finite terminating impartial position under normal play is equivalent to a single NIM heap of some size, called its nimber or Grundy value. Equivalence here means that replacing the position by that heap preserves the winning or losing status of its sum with any other such game. In a disjunctive sum, a move is made in exactly one component. The nimber of a sum is the bitwise XOR of the component nimbers; in particular, the nimber of a NIM board is the XOR of its heap sizes.

Why NIM is a useful barrier example. For a disjunctive sum of independent impartial components, the Grundy value is the XOR of the component nimbers. If these nimbers can vary independently so that their aggregation contains an unbounded parity subproblem, NIM isolates the resulting aggregation obstruction. Learning NIM would therefore address a fundamental component of impartial-game play, but would not by itself solve self-play learning for the wider class: determining component nimbers can be computationally difficult (Section 8.3). Nor does every impartial game contain a hard parity aggregation task. Our unconditional lower bound concerns NIM; extensions require an explicit encoding and reduction.

5 Main results: impossibility and possibility

We first establish the single-frame barrier under fixed total latency, then develop three bypasses: recent-history inputs, multiple rollout channels, and persistent row-wise recurrence.

5.1 Mastery notions

We distinguish three notions of mastery:

We use standard impartial-game terminology: a $P$-position is losing for the player to move, and an $N$-position is winning. For NIM, Theorem 4.4 says that $P$-positions are exactly the positions with nim-sum $0$. Equivalently, weak mastery requires the agent to move to a $P$-position at every one of its decision histories consistent with its own earlier actions, starting from an initial position winnable in its designated role. This distinction allows a simple strategy to master a family without solving positions it never encounters under its own play; Appendix D gives examples.

5.2 Single-frame impossibility results

In a single-frame representation, the network sees only the current position. To play optimally, it must in effect determine whether the nim-sum is zero and, if not, find a move producing nim-sum zero. The core obstacle is that global nim-sum computation requires parity-like behaviour across many bits, and parity is not in $\AC^0$ (Furst et al., 1984; Håstad, 1986; Smolensky, 1987; Razborov, 1987).

5.3 First bypass: two-frame restoration

The fundamental idea is to avoid computing the global nim-sum from scratch. Instead, we exploit that each move changes only one heap, so the nimber difference between consecutive positions is locally computable.

In NIM, if $P'$ is obtained from $P$ by changing heap $i$ from $x_i$ to $x_i'$, then $$\Delta(P,P') \;=\; x_i \oplus x_i',$$ a purely local computation on the changed heap.

Membership in $\AC^0$ does not guarantee a small or readily learnable network. For the complete two-frame move selector built on this difference computation, our modular construction gives an upper bound of 42 threshold layers; one shootout-controller step has a bound of 70 (Appendix C). These are constructive bounds, not necessary depths. Any Boolean function has a depth-two AND–OR representation with negated inputs, but its size can be exponential; $\AC^0$ requires polynomial size as the input grows. We have not optimised this depth–size trade-off. Removing the expressivity obstruction therefore leaves practical network design, training procedures and hyperparameter choices open. The layer bounds do not establish the cause of the experimental learning plateaus.

5.3.1 Two-frame local restoration rule

The next observation is that if, after our move, we make the opponent face a zero nim-sum position, then the opponent’s next move produces some nimber difference $\delta$. If we respond with a move that produces the same nimber difference $\delta$, we restore nim-sum zero.

Moreover, a concrete restoration move can be selected in $\AC^0$ from $(Q,Q')$ by computing $\delta=\Delta(Q,Q')$ and then choosing (with a fixed tie-break rule) a heap $i$ such that $x_i' = x_i \oplus \delta < x_i$ (Appendix C).

Interpretation (“mirror the delta”). Once we have made the opponent face a $P$-position, we do not need to recompute $\operatorname{nim}(\cdot)$ from scratch. We only need to mirror the observed change $\Delta(Q,Q')$ in our response move. Figure 2 illustrates this mechanism on a concrete three-heap instance.

Proposition 5.5 is structural: it describes a response pattern that keeps returning the game to nim-sum zero, provided the player can (i) compute $\delta=\Delta(Q,Q')$ from the last two frames and (ii) choose a legal move $Q'\to R$ that realises the same $\delta$. In NIM, when the opponent changes exactly one heap, $\delta$ is simply $x_i\oplus x_i'$, and testing whether a candidate response move realises $\delta$ is a local check on the heap being changed.

The significance for learnability is representational. A two-frame policy network can condition its response on $(Q,Q')$ and hence on the locally computable $\delta$, while a single-frame policy must reconstruct the relevant global information from $Q'$ alone. The experiments in Section 7 examine this contrast through supervised restoration learning and imitation-trained rollout policies. The reported networks are policy-only; these results do not establish that self-play discovers the constructions.

5.3.2 Implementation overview

An $\AC^0$ implementation of the two-frame delta and restoration components can be organised into:

• a binary encoding scheme for heap vectors (Appendix C),

• a constant-depth detection of which heaps changed between frames,

• an $\AC^0$ circuit computing $\Delta$ on those changed heaps (Lemma 5.4),

• an $\AC^0$ selection mechanism for a response move realising a target $\delta$.

5.4 Second bypass: structured rollout policies

Theorem 5.2 shows that no $\AC^0$ circuit can evaluate the nim-sum in a single forward pass. A natural follow-up is whether planning—testing candidate moves and simulating play, as in Monte-Carlo Tree Search (MCTS)—can compensate.

We analyse a stylised rollout interface: a planning algorithm queries a rollout policy $\pi$ by simulating a complete game in which both players follow $\pi$ from a start position, and it observes only the terminal win/loss bit. This abstraction isolates the information that a weak policy can expose through repeated simulation; it is not a claim about the optimisation dynamics of AlphaZero-style training (cf. Section 1.2).

Allowing arbitrary start positions would defeat the single-channel restriction: querying $\pi_0$ on heaps consisting of the $k$th bits of $P$ returns $\sigma_k(P)$. Likewise, an unrestricted sequential controller could compute the nim-sum itself. The lower bound therefore concerns the stated measurement/readout model, not general MCTS or all single-policy algorithms.

Finite-state shootout controller (FSM over policy heads). The multi-channel classifier can stop early after a nonzero channel outcome, without changing its Boolean decision rule (the OR of all channel bits). This limited scheduling optimisation does not give the single-channel readout an unrestricted sequential controller. To make this adaptivity explicit (without changing the $\AC^0$ constraints on each head), it is convenient to view head-selection as a small finite-state controller that sits outside the heads and only sees the terminal win/loss bit of each rollout.

Formally, fix rollout heads $\pi_0,\dots,\pi_{k-1}$. A finite-state shootout controller is a tuple $$\mathcal{C} = (\mathcal{S}, s_{\mathrm{init}}, g, \delta, \mathsf{halt}),$$ where $\mathcal{S}$ is a finite set of controller states, $s_{\mathrm{init}}\in\mathcal{S}$ is the initial state, $g\colon \mathcal{S}\to\{0,\dots,k-1\}$ selects which head to use for the next rollout query, $\delta\colon \mathcal{S}\times\{0,1\}\to\mathcal{S}$ updates the controller state after observing a rollout outcome bit $r=\mathrm{RO}_{\pi_{g(s)}}(P)$, and $\mathsf{halt}\subseteq \mathcal{S}$ is a set of halting states associated with an output decision. (When $\mathsf{halt}=\emptyset$, the controller simply runs for a fixed number of queries and outputs a decision at the end.)

This viewpoint does not increase the per-step computational power of the rollout heads: each $\pi_j$ remains $\AC^0$-bounded. Instead, the controller organises which $\AC^0$ head is iterated in a shootout and when to stop querying. Figure 3 depicts a particularly simple controller that turns the $B$ structured rollout heads from Proposition 5.9 into a sequential “bit-query” procedure for deciding whether $\sigma(P)=\operatorname{nim}(P)$ is zero (and hence whether $P$ is a $P$-position).

The checked implementation includes the outer controller: it selects a head, executes its rollout, records the outcome and either reloads the original board for the next head or halts. For classification it stops at the first outcome 1. For move selection our implementation runs all $B$ heads, since an early classification decision need not supply the invariant bits required by the move readout. Each controller tick is itself an $\AC^0$ map. The original board remains available as a read-only input throughout; it is not an oracle for its nim-sum. Appendix C specifies the storage and update costs.

Integration (channels vs. protocol). It is helpful to reinterpret Part (ii) of Theorem 5.12 in an “information-channel” language: each policy head $\pi_j$ defines a distinct rollout measurement channel which, when iterated to termination, returns a single bit $r_j=\mathrm{RO}_{\pi_j}(P)$ that depends on the hidden $B$-bit invariant $\sigma(P)$ (cf. the identities in Proposition 5.9). With a single head, repeated deterministic root rollouts return the same linear functional $\ell(\sigma)$; admissible one-heap modifications give its known affine corrections (Proposition 5.10). These measurements supply no further unknown invariant bit. With multiple heads, the agent has access to linearly independent invariant measurements and can reconstruct $\sigma(P)$ from their outcomes (Proposition 5.9). The finite-state shootout controller introduced above is the natural generalisation of this idea: it does not change what any head can compute, but organises the heads into an adaptive querying protocol—the controller decides which channel to query next (and when to stop, or when to re-query for robustness) based on previously observed rollout outcomes. In this view, multi-head provides the channels, while the FSM provides the sequential control that turns those channels into a practical evaluation procedure.

Depth amplification. Although a single $\AC^0$ circuit cannot compute parity, iterating an $\AC^0$ policy for $L$ game steps yields an effective depth $\Theta(L)$ computation, which can reveal parity information. The next proposition makes this explicit by exhibiting $B$ simple $\AC^0$ rollout heads whose outcomes recover all $B$ bits of the nim-sum.

A single policy head yields only one bit. The preceding result relies on having multiple rollout channels. For one fixed member of this structured policy family, admissible queries reveal known affine functions of the same invariant bit. This statement does not concern arbitrary rollout policies.

The initialisation boundary for restoration. Matching two successive differences yields $\operatorname{nim}(R)=\operatorname{nim}(Q)$, whether or not that value is zero. Thus Proposition 5.5 does not supply a classifier for an arbitrary starting position. For example, complete a matching-delta policy by subtracting one from the first nonempty heap whenever no matching response exists or no previous frame is available. Starting from $(2)$, it plays $(2)\to(1)\to(0)$ and the first player loses, although $(2)$ is winning. The fallback after the first move is needed because its delta is $2\oplus1=3$, which cannot be realised from $(1)$. This counterexample does not rule out every possible verifier construction; it shows that conditional restoration and an unspecified fallback do not establish one. We make no universal-verifier claim. Initial winning-move selection can instead use the multi-channel construction above or the growing recurrent scan in Section 5.5.

5.5 Third bypass: persistent row-wise recurrence

The two-frame construction supplies the relevant history explicitly, while the multi-head construction obtains additional information through complete rollouts. A third possibility is to let the agent build and retain its own state by processing the board sequentially. The recurrent update remains simple, but the number of updates is allowed to grow with the input. The construction uses the elementary running-XOR algorithm. In correspondence reproduced by Friedman (Friedman, 2017b), John Schulman proposed feeding NIM heaps one at a time to a recurrent network and reported preliminary supervised nim-sum experiments. Here we make the shallow updates, separator and state protocols, and move-selection constructions explicit, distinguishing their representational guarantees from learning through self-play.

Serialising positions and retaining state. Write position $P_t=(x_{t,1},\ldots,x_{t,N})$, with each heap represented by one $B$-bit row. Feed successive positions as the stream $$\underbrace{x_{1,1},\ldots,x_{1,N}}_{P_1},\ \mathtt{SEP},\quad \underbrace{x_{2,1},\ldots,x_{2,N}}_{P_2},\ \mathtt{SEP},\quad\ldots .$$ Each row arrives as a block of $B$ bits together with a row/separator tag. A separator marks the end of a complete position; the agent chooses a move only after that position has been read. The next observed position is then appended to the stream. For comparisons of individual heaps, indices remain aligned across positions, including rows for empty heaps. A scan of the current board suffices for nim-sum evaluation without earlier game positions; cross-position memory additionally supports the comparisons below. The hidden state is carried across rows and position boundaries. A separator resets the accumulator for the next scan while preserving selected information about the completed position; it does not reset the entire memory.

From a summary to a move. Computing $\sigma_t$ does not by itself retain the heap rows needed to choose a move. One implementation replays the current position after the first scan. If $\sigma_t\ne0$, select the first row $i$ for which $$x_{t,i}'=x_{t,i}\oplus\sigma_t<x_{t,i}.$$ Such a row exists: choose a heap containing the highest set bit of $\sigma_t$. Replacing that heap by $x_{t,i}'$ leaves nim-sum zero. XOR, binary comparison and conditional selection are constant-depth operations; the replay uses $O(B+\log N)$ state bits to retain the summary, a selected move and its row index. The explicit protocol is $$\mathtt{rows}(P_t),\ \mathtt{SEP},\ \mathtt{rows}(P_t),\ \mathtt{SEP}.$$ The first separator stores the summary and switches to replay; the second emits the move and returns to scan mode. This takes exactly $2N+2$ updates, with one additional reset token at the start of a game. If $\sigma_t=0$, choose the first nonempty heap and decrement it, or report termination when all heaps are empty. Lean verifies the complete replay controller, including its binary move output and its fixed-scale threshold implementation. With an $r$-bit counter satisfying $N<2^r$, its state uses $4+5B+3r$ bits. The strict inequality allows the counter to hold the end value $N$, whereas an output index alone only needs $N\le2^r$. Alternatively, store the current board in $O(NB)$ bits during the initial scan and use a constant-depth selector at the separator, as in Appendix C. This avoids replay at the cost of board-sized memory. The distinction matters for a stream in which each position is supplied only once. Both variants have checked bit-level circuits, fixed-scale network implementations and winning-play guarantees. The board-storage variant uses $NB+B+r$ state bits and $N+1$ updates per decision, with $N<2^r$, plus a reset update when initialising the controller.

Connecting recurrence to the history bypass. The retained summaries allow the agent to compare consecutive positions through $$\sigma_{t-1}\oplus\sigma_t =\operatorname{nim}(P_{t-1})\oplus\operatorname{nim}(P_t) =\Delta(P_{t-1},P_t).$$ When one heap changes from $a$ to $b$, this equals $a\oplus b$. If the preceding position has nim-sum zero, the difference is exactly the invariant that the restoration rule must cancel. Storing the preceding board additionally permits direct row-by-row comparison as the new board arrives. A summary of $O(B)$ bits preserves the invariant, rather than the full game history; arbitrary access to old positions requires additional storage or replay. The difference always refers to consecutive completed boards actually supplied to the controller. If these are only the boards at the player’s decision times, they usually span two game moves. Comparing just the opponent’s move instead requires the player’s own post-move board as the preceding frame. The initial scan also computes the invariant from an arbitrary starting position, without assuming an earlier zero-nim-sum frame. Thus memory across row updates is sufficient for this route; an earlier game position is useful for transition comparisons but is not required to compute the current nim-sum. This initialisation uses the growing recurrent horizon and is therefore an additional resource beyond the fixed-latency two-frame construction.

Why the lower bound is respected. Unrolling $N$ constant-depth updates gives a computation of depth $O(N)$, so Proposition 5.13 lies outside the fixed-$T$ premise of Theorem 2.4. A one-step recurrent dependency can nevertheless carry information accumulated over the whole stream. Merely appending positions and separators to a fixed-depth input does not supply this growing computation horizon. The bypass comes from sequential computation with retained state, not from the delimiter itself. For growing heap bit-width, the accumulator also needs $O(B)$ bits; a fixed-width hidden state is not claimed to store arbitrary-size invariants or histories. The construction establishes representational sufficiency for NIM, but does not establish that training a recurrent network will discover the update or preserve it reliably over long games. We do not report recurrent training experiments here.

5.6 What the three bypasses establish

These are three ways around the same restricted inference problem, not three shallow algorithms for unrestricted parity. The two-frame construction changes the input and imposes a promise. The other constructions allow processing time to grow. Their complete board-to-winning-move maps cannot themselves form an $\AC^0$ family: otherwise applying either to $(2,b_1,\ldots,b_m)$ would contradict Theorem 5.2. Parallel output heads alone do not supply the rollout computation, and separators alone do not supply a recurrent scan. Appendix C illustrates the explicit network constructions and explains their conservative depth and layer bounds.

6 Learning impartial games with neural networks

The results above are primarily representational: they identify what information a bounded-depth, fixed-scale quantised model can or cannot compute from its input, and how history, multiple rollout heads, or a growing recurrent horizon can supply the missing information. This section connects the theory to the training protocols used in Section 7 and highlights the main modelling choice ($\AC^0$ vs. $\TC^0$).

6.1 Practical takeaways

• Single-frame is brittle to parity. In the worst case, fixed-scale quantised bounded-depth inference cannot reliably represent the nim-sum or a winning move selector (Section 5.2).

• Three bypasses with different resources. A two-frame input exposes the transition signal $\Delta(P,P')$ and supports restoration (Section 5.3.1); multiple rollout heads recover the missing nim-sum bits through depth amplification (Section 5.4); persistent recurrence accumulates the invariant over sequential row updates and retains summaries across positions (Section 5.5). The last route trades fixed total latency for a growing processing horizon.

• Optimisation remains nontrivial. Even when a solution is expressible in $\AC^0$, discovering it from sparse win/loss rewards can be difficult; our experiments therefore isolate a dense restoration supervision signal and separately report rollout-based classification.

6.2 Teacher-guided data as a controlled source of transitions

Let $\pi_{\mathrm{opt}}$ denote an optimal NIM policy (move to nim-sum $0$ whenever possible). For a noise parameter $\varepsilon\in[0,1]$, define a noisy teacher $\pi_T^{\varepsilon}$ that plays according to $\pi_{\mathrm{opt}}$ with probability $1-\varepsilon$ and otherwise chooses a uniformly random legal move. Occasional random moves broaden state coverage and, crucially for two-frame agents, generate diverse transition pairs $(Q,Q')$ from which the local difference signal $\Delta(Q,Q')$ can be inferred.

6.3 Approximate majority, parity, and the $\AC^0$ abstraction

One might object that modern networks can implement majority-like decisions, suggesting $\TC^0$ (threshold circuits) as the “right” complexity class. Indeed, if one allows scale-adaptive thresholds/biases or fan-in dependent re-scaling, constant-depth threshold models can represent parity-type computations.

Our focus is a restricted literal-threshold regime: fixed total depth, nonnegative weights on Boolean literals, and thresholds bounded in units of the smallest nonzero weight. In this regime, each gate has a constant-size witness and collapses to a constant-width DNF, yielding an $\AC^0$ abstraction (Theorem 2.4). Constant-depth $\AC^0$ circuits can implement approximate counting (Ajtai, 1993), yet they have exponentially small correlation with parity (Furst et al., 1984; Håstad, 1986; Smolensky, 1987; Razborov, 1987). Learning parity depends on the architecture and training setting; both difficulties and positive results have been studied (Thornton, 1996b,a; Daniely and Malach, 2020). The representational lower bound here applies only to the explicit gate model. Section 6.4 gives a complementary Fourier/spectral interpretation of this local-versus-global parity separation.

6.4 A spectral viewpoint: low-degree Fourier mass vs. parity

A useful complementary lens is Fourier analysis on the Boolean hypercube. Let $f:\bits^{n}\to\mathbb{R}$ and define the Walsh–Hadamard characters $$\chi_S(x) \;=\; (-1)^{\sum_{i\in S} x_i}, \qquad S\subseteq[n].$$ The set $\{\chi_S\}_{S\subseteq[n]}$ is an orthonormal basis with respect to the uniform distribution on $\bits^n$. The Fourier coefficients are $$\hat f(S)\;=\;\mathbb{E}_{x\sim U(\bits^n)}\bigl[f(x)\chi_S(x)\bigr], \qquad\text{and}\qquad f(x)=\sum_{S\subseteq[n]}\hat f(S)\chi_S(x).$$ We refer to $|S|$ as the Fourier degree (or “frequency”) of the coefficient $\hat f(S)$.

Parity is a pure high-frequency character. For any nonempty $S\subseteq[n]$, the parity function $\mathrm{PARITY}_S(x)=\chi_S(x)$ has Fourier expansion supported on a single set: $\widehat{\mathrm{PARITY}_S}(S)=1$ and $\widehat{\mathrm{PARITY}_S}(T)=0$ for $T\neq S$. Thus its spectral “frequency” is exactly $|S|$. More generally, if $f$ is $(k,\varepsilon)$-spectrally band-limited and $|S|>k$, then $$\bigl|\mathbb{E}[f(x)\chi_S(x)]\bigr|^2=\hat f(S)^2\le\mathrm{Tail}_{>k}(f)\le\varepsilon.$$(6.1) This elementary inequality is the link between concentration at low degree and small correlation with a high-degree parity.

$\AC^0$ has little high-frequency mass. A seminal theorem of Linial–Mansour–Nisan shows that $\AC^0$ functions have almost all Fourier mass on low degrees: for $f$ computed by an $\AC^0_d$ circuit of size $M$, the tail above degree $k$ decays rapidly with $k$ (see (Linial et al., 1993), and sharper bounds in (Tal, 2015)). For fixed depth and polynomial size, correlation with full parity under the uniform distribution is negligible in $n$. Applying this statement to other subsets requires specifying their size relative to circuit depth and size, and it does not automatically apply under a nonuniform training distribution.

Local vs. global parity in NIM. In our encoding, the $j$th bit of the nim-sum is the parity of the $j$th bits across all $N$ heaps, hence a degree-$N$ character. Conditional on a specified changed heap $i$, the sign encoding of the $j$th delta bit is the two-coordinate character $(-1)^{x_{i,j}+x'_{i,j}}$. When the changed index is unknown, the delta bit is specified on pairs of boards differing in at most one heap. A shallow extension to all pairs is $$d_j(P,P')=\bigvee_{i=1}^{N}(x_{i,j}\oplus x'_{i,j}).$$(6.2) On the promised domain this is the required delta bit. For $N\ge2$, its sign encoding $(-1)^{d_j}$ is not a single character, even up to sign; for $N=1$ it is exactly a degree-two character. Thus local computability does not mean that the full unknown-index map has degree two. It follows from the explicit $\AC^0$ construction in Lemma 5.4.