Equation (H.1)Under the stated correlation premise η_N: success ≤ 2/(q−1) + (q−1)η_N

Proof. Part (i). Fix $B\ge2$, $N\ge1$ and put $q=2^B$. Let $U$ be the uniform distribution on all $N$ independent $B$-bit heaps, before conditioning on a nonzero nim-sum. For any fixed values of $N-1$ heaps and any target nim-sum, exactly one value of the remaining heap gives that target. Thus $\sigma$ is exactly uniform on $\mathbb F_2^B$, and $\Pr_U[\sigma\ne0]=(q-1)/q$. Let $\ell=\ell_j$ be the nonzero linear functional returned by the fixed structured head, and let $\beta=\ell(\sigma)$.

For each fixed $b\in\{0,1\}$, decode $F_N(P,b)$ as a proposed move $(i,v)$. On legal outputs define $g_b(P)=h_i\oplus v$, and set $g_b(P)=0$ on invalid outputs. Selecting an indexed input block, checking legality and taking its XOR with the output use polynomial-size, constant-depth circuits. Thus for each $a\in\mathbb F_2^B$, the indicator $$H_{b,a}(P)=\mathbf1\{g_b(P)=a\}$$ is in $\AC^0$. On $\sigma\ne0$, a legal move wins exactly when $g_\beta(P)=\sigma(P)$; invalid outputs cannot satisfy that equality.

For $u\in\mathbb F_2^B$, write $\chi_u(P)=(-1)^{\langle u,\sigma(P)\rangle}$. First consider the finite probability calculation under the explicit assumption that some $\eta_N\ge0$ satisfies $$\bigl|\mathbb E_U[H_{b,a}(P)\chi_u(P)]\bigr| \le \eta_N$$ for every $b\in\{0,1\}$, $a\in\mathbb F_2^B$ and nonzero $u\in\mathbb F_2^B$. This is a two-sided correlation bound under the unconditioned distribution $U$; it does not assume independence between the readout and the nim-sum. Expanding the exact-value indicator gives $$\mathbf1\{\sigma=a\}=q^{-1}\sum_{u\in\mathbb F_2^B} (-1)^{\langle u,a\rangle}\chi_u(P),$$ so $$\left|\mathbb E_U[H_{b,a}\mathbf1\{\sigma=a\}] -q^{-1}\mathbb E_U H_{b,a}\right| \le \frac{q-1}{q}\eta_N.$$ For each fixed $b$, the events $g_b(P)=a$ are disjoint. Therefore $$\begin{aligned}\Pr_U[\text{winning move and }\sigma\ne0] &=\sum_{a\ne0}\mathbb E_U[H_{\ell(a),a}\mathbf1\{\sigma=a\}]\\ &\le q^{-1}\sum_{b\in\{0,1\}}\sum_{\substack{a\ne0\\\ell(a)=b}} \mathbb E_U H_{b,a}+\frac{(q-1)^2}{q}\eta_N\\ &\le \frac{2}{q}+\frac{(q-1)^2}{q}\eta_N.\end{aligned}$$ Dividing by $\Pr_U[\sigma\ne0]=(q-1)/q$ gives the finite bound $$\Pr_U[\text{legal winning move}\mid\sigma\ne0] \le \frac{2}{q-1}+(q-1)\eta_N.$$(H.1)

It remains to supply the correlation estimate for the circuit class. For $u\ne0$, $\chi_u$ is parity on $N$ times the number of nonzero coordinates of $u$, hence on at least $N$ input bits. Fix all coordinates outside this support. The restricted indicator remains a polynomial-size, fixed-depth $\AC^0$ circuit, so the standard parity-correlation bound applies uniformly to every such restriction; averaging over the fixed coordinates preserves the bound (Håstad, 1986, 2014). Taking the maximum over the finitely many $a,b,u\ne0$ gives a nonnegative negligible $\eta_N$. Since $B$, the circuit depth and the polynomial size exponent are fixed, $(q-1)\eta_N$ is also negligible. This yields the asserted asymptotic bound. The fixed-$B$ assumption is essential to this stated asymptotic conclusion.

For attainability of the leading constant, choose a nonzero $a_b$ from each fibre $\ell(a)=b$, possible because $B\ge2$. After observing $b$, try to cancel $a_b$ using the first heap $h_i$ with $h_i\oplus a_b<h_i$, with any legal fallback if none exists. This is an $\AC^0$ readout and wins whenever $\sigma=a_0$ or $a_1$, an event of conditional probability $2/(q-1)$. Any additional success is at most negligible by the upper bound. For $B=2$ and $\pi_0$, the choices $a_0=2,a_1=1$ give exactly $2/3$: the case $\sigma=3$ is assigned a legal delta-1 move and cannot win.

Part (ii). The $B$ root rollout bits reconstruct $\sigma$. If it is nonzero, a heap containing its highest set bit can be decreased to $h_i\oplus\sigma$, leaving zero nim-sum. An $\AC^0$ first-qualifying-heap selector implements this choice. With zero nim-sum, any legal move is optimal in the game-theoretic sense that no winning move exists. Each root rollout has at most $N(2^B-1)$ moves. Hence $B$ rollouts use $O(BN2^B)$ simulated moves, each with polynomial circuit work; no successor enumeration or unrestricted controller is used.

Part (iii). If the predecessor $Q$ has nim-sum zero and the opponent legally reaches $Q'$, then $\delta=\Delta(Q,Q')=\operatorname{nim}(Q')\ne0$. Select a decreasing heap $h_i\to h_i\oplus\delta$ as above. The two-frame difference and move selector are $\AC^0$, and the response returns nim-sum zero. Repeating this response after the player’s own successful moves wins from the established invariant. No assertion about establishing it from an arbitrary start is used.□