arXiv：cs.AI· S{\o}ren Riis·· 5 小时前
用电路复杂度方法克服无偏博弈中的学习瓶颈：基于 NIM 的研究
Overcoming a Learning Bottleneck in Impartial Games: A Circuit Complexity Approach
AI 导读
研究以 NIM 为例，揭示浅层固定规模量化网络属于 AC⁰ 电路类，无法计算任意大输入的奇偶性，因而无法在所有棋盘规模上实现最优单步走法。论文提出两条架构设计思路（双帧输入与互补 rollout 策略）并给出持久循环的理论构造，监督实验验证了双帧恢复与多 rollout 头的效果。核心数学结果与构造已在 Lean 中形式化验证，交互版论文与 Lean 源码已在线公布。
正文
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 this https URL.
| Comments: | 48 pages, 8 figures. Substantially revised and retitled; adds persistent recurrence, Lean-checked constructions and an interactive edition. Interactive paper and Lean sources: this https URL |
| Subjects: | Artificial Intelligence (cs.AI) |
| MSC classes: | 91A46, 68Q15, 68T05, 03D15 |
| ACM classes: | F.1.1; I.2.6; I.2.8 |
| Cite as: | arXiv:2411.06403 [cs.AI] |
| (or arXiv:2411.06403v4 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2411.06403 arXiv-issued DOI via DataCite |
Submission history
From: Soren Riis [view email]
[v1]
Sun, 10 Nov 2024 09:34:26 UTC (33 KB)
[v2]
Sun, 1 Feb 2026 09:12:48 UTC (171 KB)
[v3]
Sun, 15 Feb 2026 20:38:55 UTC (119 KB)
[v4]
Sun, 11 Oct 2026 08:22:57 UTC (93 KB)
来源：arXiv：cs.AI · arxiv.org