arXiv preprint ·
Solving Go under Positional Superko: Sound Proof Transfer and New Board Values
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Positional superko (PSK) forbids recreating any earlier whole-board position. It is part of the Chinese rules as written and of the rules used in computer Go. Yet almost all solved Go boards were computed under a simpler basic-ko rule set. PSK makes solving hard: legality depends on the whole game history, and this breaks the three tools that make solving tractable, namely transposition tables (the graph-history interaction problem), static life-and-death recognition, and safe move pruning. We present Sanko, a parallel depth-first proof-number solver that restores all three soundly. Its core is a cheap proof-transfer theorem: a stored proof stays valid on a new path unless a board that the proof's winner must create has already occurred. Sanko proves 5x5 Go in 16 minutes with six threads, where the previous state of the art needed 5.25 hours with six processes, and in about a minute and a half on one 192-thread machine. It also establishes the first PSK values of twenty-three further boards, eleven of which were unsolved under any rules. Superko changes game-theoretic values: 4x7, a full-board win under basic ko, is worth only 12 points under PSK, and we pinpoint the move at which the previously published optimal line fails. Unlike earlier solutions of empty Go boards, we release the solver source together with the command line and outcome of every run behind our values and measurements, so that all reported values can be reproduced.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
VeriEvolve: Evaluator-First Evolution for Tool-Using Agents
Governed Self-Evolution for Autonomous Investing: A Multi-Agent LLM System with an Invariant Core
Enhancing Cross-Grade Generalization in Banana Variety Classification via Hybrid CNN-Transformers and Knowledge Self-Distillation
Lifetime-valid decisions by continually evolving AI analysts
An Evidence-Driven Multi-Agent Compound AI System for Head and Neck Proton Radiotherapy Planning
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.