arXiv cs.AI· S{\o}ren Riis·· 3 天前AI 评分22
如何突破无偏博弈的学习瓶颈：一种电路复杂度方法
Overcoming a Learning Bottleneck in Impartial Games: A Circuit Complexity Approach
AI 导读
针对神经网络在无偏博弈中难以学会最优策略的问题，研究者以 NIM 游戏为例，证明浅层固定规模量化网络属于 AC⁰ 电路类，无法计算任意大输入的奇偶性，因而无法在所有棋盘规模上实现最优单步走子。
正文 · 原文
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