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

arXiv:2411.06403 · cs.AI · Submitted 2024-11-10 · Read on arXiv

cs.AI

Submitted: 2024-11-10

Updated: 2026-10-11

Comments: 48 pages, 8 figures. Substantially revised and retitled; adds persistent recurrence, Lean-checked constructions and an interactive edition. Interactive paper and Lean sources: https://sr123.github.io/impartial-games-learning-lean/

Code: https://github.com/SR123/NIM

Project page: https://sr123.github.io/impartial-games-learning-lean

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Accuracy — 1× in this paper · explained in 1 episode

Sources

• Bipartite peak-pit domains
• The Expressive Power of Transformers with Chain of Thought
• LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale
• Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks
• Impartial Games: A Challenge for Reinforcement Learning

Related papers

• MAVEN-T: Reinforced Heterogeneous Distillation for Real-Time Multi-Agent Trajectory Prediction
• Model Discovery Agent: LLM-assisted Bayesian experiment design for data-efficient discovery of mechanistic world models
• Agents' Last Exam
• The Clinician's Veto: Navigating Trust, Liability, and Uncertainty in Autonomous AI Prescribing
• MindHelper: Closed-Loop Embodied Mental-State Reasoning for Precision Intervention
• Incumbent Advantage: Brand Bias and Cognitive Manipulation Dynamics in LLM Recommendation Systems