Section 4.3, “Why NIM is a useful barrier example”NIM isolates the XOR aggregation obstruction; extensions to other games need explicit reductions
Informal interpretation Motivation, interpretation or scope; not a formal claim.
1 Paper text
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.
Generated from paper_jmlr.tex, lines 438–440.
2 Explain this
NIM isolates one obstruction cleanly: for a sum of independent impartial games the Grundy value is the XOR of the components' values, so whenever those values can vary independently, the aggregation step contains a parity problem. NIM is that aggregation step with nothing else around it.
Caveats stated in the paper: Sprague–Grundy theory does not give an efficient way to compute component nimbers, and not every impartial game has a hard parity aggregation. The lower bound is proved for NIM; other games need an explicit encoding and reduction.
3 How this is formalised
A motivating paragraph. The only formal statement is about NIM, Theorem 5.2 (barrier); no claim about other games is made or checked.
| Paper anchor | par-why-nim-is-a-useful-barrier-example-p1 (website anchor; the manuscript has no label here) |
|---|---|
| Displayed as | Section 4.3, “Why NIM is a useful barrier example” |
| Claim | NIM isolates the XOR aggregation obstruction; extensions to other games need explicit reductions |
| Coverage category | Informal interpretation |
| Statement source | paper_jmlr.tex lines 438–440; SHA-256 of the normalised block source fc9b51e83d97cdd0… |
| Explanations | explain/c-why-nim, formal/c-why-nim |
| Build evidence | fresh isolated rebuild, audit report |
4 Lean statement and source
No Lean statement corresponds to this claim. This is interpretation or motivation, not a formal mathematical claim.
Build evidence: fresh isolated rebuild of all 38 bundled modules with Lean (version 4.26.0, started 2026-10-10T15:21:56Z, finished 2026-10-10T15:27:00Z: 38/38 modules compiled, 1588 axiom reports, no errors. See Build for the commands and the independent audit of 2026-10-10 (dated evidence).