Solving Go under Positional Superko: Sound Proof Transfer and New Board Values

Sami Kharma; Florian Schintke

cs.AIOct 21, 2026

Solving Go under Positional Superko: Sound Proof Transfer and New Board Values

Authors: Sami Kharma, Florian Schintke

Organizations: Zuse Institute Berlin Berlin, Germany

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.

Figures & tables

Panel of Figure 1 — Figure 1: Values under positional superko of all boards with four to 30 points and at most 18 columns. The value is Black’s winning margin with optimal play. Besides $2{\times}2$ , whose superko value was known van der Werf et al. (2003) , $4{\times}7$ (framed) is the one board whose value differs from its basic-ko value. The smaller boards agree with earlier results. Linear boards from $1{\times}19$ to $1{\times}30$ remain open.

Panel of Figure 2 — Figure 2: A proof $T$ stored at $N$ along history $H$ and reused along $H^{\prime}$ . Both histories start at the empty board $\varnothing$ . A board that occurs both on $H^{\prime}$ and in $T$ (dashed) makes $T$ invalid only if the winner creates it in $T$ , because that winner move becomes illegal. If the loser creates it, the loser merely loses an option.

Panel of Figure 3 — Figure 3: (a) Condition (C2): Black has just passed and White passes back. (b) A region that is vital in Benson’s classic sense, since its empty points all touch the Black chain, but no pure eye, since the White stones do not. (c) The same region after Black captures the intruders: point $a$ touches no Black stone.

Panel of Figure 4 — Figure 4: Expansions per benchmark position with the learned prior against a prior based on the opponent’s eye space (112 positions, serial, node limit $10^{8}$ ). Points below the diagonal favour the learned prior, which needs 2.8 $\times$ fewer expansions in the geometric mean.

$5{\times}5$ , komi 24.5 (Black wins)
Solver	CPU, parallelism	Time	Nodes
EWS	i7-10510U, 6 proc.	5.25 h	2.61 B
Sanko	EPYC 9475F, 6 threads	15.7 min	1.38 B
Sanko	EPYC 9475F, 14 threads	7.4 min	1.54 B
Sanko	EPYC 9475F, 192 threads	1.3–1.6 min	2.0–2.5 B
$4{\times}4$ , komi 1.5 (Black wins), one thread

Table 1: Comparison with EWS Randall et al. (2024) , the previous PSK state of the art. Nodes are expansions for Sanko and best-first tree nodes for EWS. EWS split

5{\times}5

into six processes, one per White reply to C3. We solve the position after C3 in a single search.

Board	PSK	Basic ko	Black proof					White proof
			komi	exp.		time		komi	exp.		time
$1{\times}10$	1	1	0.5	25	k	10	s	1.5	0.12	M	10	s
$1{\times}11$	2	2	1.5	35	k	10	s	2.5	0.34	M	10	s
$1{\times}12$	2	2	1.5	1.5	B	30	s	2.5	26	M	10	s
$1{\times}13$	0	–	$-$ 0.5	0.41	M	10	s	0.5	88	M	11	s
$1{\times}14$	1	–	0.5	4.1	M	10	s	1.5	0.57	B	17	s

Table 2: PSK values established in this work, with the basic-ko values of MIGOS van der Werf and Winands (2009) . Each proof is given by its komi, expansions and time on one 192-thread machine (

1{\times}n

: unpruned, † White proof unpruned). The Black proofs of

5{\times}5

and

5{\times}6

start after Black’s C3, that of

3{\times}10

after Black’s D2. ∗ One part per symmetry-unique first move of Black, each in a fresh process (times added, Tables 6 and 7 in Appendix B ). A full-board value needs no White proof: Black owns every point, and no result can exceed the board size. Bold values are new under PSK. A dash marks boards that were unsolved under any rules. Rows with

\geq

\leq

give the bound proved so far. Smaller boards (

1{\times}4

–

1{\times}9

3{\times}3

4{\times}4

) are consistent with the literature Weninger and Hayward (2017) ; Randall et al. (2024) ; van der Werf et al. (2003) .

Panel of Figure 5 — Figure 5: $3{\times}10$ has value 8. (a) Black’s D2 (1) and the next 21 moves of the principal variation of Black’s proof at komi 7.5. It continues 23 K3 (capturing 8 and 10), 24 J2, 25 F1 (capturing 2 and 6). (b) The position after move 25, where the static analysis proves Black’s win. Whenever it is White’s turn, we follow the reply whose refutation took the most work, so it shows how Black wins rather than the optimal margin. White wins at komi 8.5 against every first move of Black.

Panel of Figure 6 — Figure 6: Proof sizes in expansions versus board area. † At 30 points, the $3{\times}n$ and $5{\times}n$ marks include one White-pruned subproblem per symmetry-unique first stone move of Black. The $1{\times}n$ proofs are unpruned.

Variant (problem)	Effect
No proof transfer ( $3{\times}7$ )	5,952 $\times$
No region solver	2.33 $\times$ (1.02–4.61)
No interior region moves	1.70 $\times$ (1.00–2.60)
Eye-space prior instead of the learned prior	3.19 $\times$ (2.15–4.43)
No prior (uniform initial numbers)	4.72 $\times$ (3.40–6.02)
1 thread vs. 192 threads ( $3{\times}9$ )	42 $\times$ time

Table 3: Ablations. Each component is removed from the full solver. Effects are expansion ratios, except for the thread rows, which compare time. The four knowledge rows give the geometric mean over the 64 positions of five suites (

4{\times}5

, two

5{\times}5

suites after C3, and

4{\times}6

for each side), with the range of the suite means in parentheses. Suites are seeded sets of random positions (12–16 positions, serial, deterministic, node limit

10^{8}

). The transfer row compares two 192-thread solves of

3{\times}7

Panel of Figure 7 — Figure 7: $4{\times}7$ : MIGOS’s published optimal line van der Werf and Winands (2009) , replayed under PSK. (a) MIGOS plays A2 ( a ), after which Black still wins all 28 points. White’s G2 ( b ) holds Black to $+3$ . (b) After G2, the attack B1, C1 (White), A2 ends with White capturing at A1. Black’s recapture at k would recreate an earlier board, so PSK forbids it. Every board-changing Black move ataris Black’s own group, so both players pass and White lives. Under MIGOS’s rules the pass lifts the ko ban and the game needs three passes to end, so Black retakes and kills. (c) Black’s best under PSK is a seki: each group has one eye (B4, F1) and they share the liberty B1.

Source	Per event	Largest run	Campaign
Twin signatures	$3\cdot 10^{-39}$	$3\cdot 10^{-25}$	$6\cdot 10^{-25}$
Mixed slot	$6\cdot 10^{-20}$	${<}10^{-14}$	$1.1\cdot 10^{-12}$
One 64-bit signature ∗	$6\cdot 10^{-20}$	$4\cdot 10^{-6}$	$1.1\cdot 10^{-5}$
Silent CPU errors †	114 FIT	$2\cdot 10^{-6}$
Defective cores ‡		${\sim}10^{-3}$

Table 4: Upper bounds on an accidental hash match, before the factor measured by fault injection, and hardware fault rates. ∗ For comparison only. † An IBM design target for POWER4 systems, cited by Dixit et al. (2021) , for a 20-hour run. ‡ A few per several thousand machines Hochschild et al. (2021) , if the run’s node has one.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

White reply	Black’s answer	Expansions	Time
pass	pass	192	10 s
A5	B4	1.8 B	74 s
B5	D4	2.3 B	89 s
C5	B4	2.0 B	78 s
B4	D2	1.8 B	67 s
C4	B4	1.3 B	53 s

Appendix

Table 5: Independent re-solves of

5{\times}5

after Black C3, one fresh process per symmetry-unique White reply. All are Black wins at komi 24.5, on 192 threads.

Black’s first move	White’s reply	Expansions	Time
pass	pass	192	50 s
A3	D3	60.1 B	42 min
A5	B3	87.4 B	1.1 h
A4	E3	100 B	1.2 h
B5	C3	146 B	1.7 h
C5	C3	166 B	2.0 h

Appendix

Table 6:

5{\times}6

upper bound at komi 4.5, split into one White-pruned proof per symmetry-unique first move of Black.

First move	Reply	Expansions	Time
pass	pass	192	11 s
A3	D2	9.4 B	7 min
B3	H2	10.4 B	8 min
C3	G2	15.3 B	11 min
D3	H2	10.6 B	8 min
E3	G2	10.9 B	8 min

Appendix

Table 7:

3{\times}10

upper bound at komi 8.5, one White-pruned proof per symmetry-unique first move of Black. After D2, Black wins at 7.5 ( Table 2 ), so

3{\times}10

is worth 8.

Komi	Run	Result	Exp.
27.5	White-pruned, one-liberty convention	White	14.6 B
23.5	White-pruned, after Black D3	White (C2)	13.6 B
12.5	unpruned	White	16.4 B
11.5	unpruned	Black (D3)	86.6 B
11.5	Black-pruned	Black (D3)	65.6 B

Appendix

Table 8:

4{\times}7

runs, each on 192 threads. A pruned run proves only a win for its own side.

$n$	Value	Black’s move	Black proof	White proof
4	4	2nd point	207	(full)
5	0	2nd	421	493
6	1	2nd	1,148	1,109
7	2	4th	461	3,334
8	3	2nd	8,177	19,937
9	0	2nd	5,134	20,477

Appendix

Table 9: Linear Go

1{\times}n

under PSK, expansions per proof. All proofs use unpruned search on 192 threads.

Position	Komi	Result	Exp.
after move 31	27.5	Black	9,318
after move 26	27.5	Black (C1)	134,266
after move 24	27.5	unknown	9,660
after move 25	27.5	White (G2)	889
after 25, G2	2.5	Black (A2)	436
after 25, G2	3.5	White	495

Appendix

Table 10: The chain of small proofs for

4{\times}7

. Black results come from Black-pruned runs and White results from White-pruned runs, so each is trusted for its winner.

Check	Result
Selftests, 7 small boards, 3 oracle modes	10,808 positions, 0 mismatches
Threshold probes, 9 boards up to $5{\times}5$	31,622 probes, 0 counterexamples
Brute-force minimax with an exact memo against shared-table solves ( $1{\times}4$ , $1{\times}5$ , $2{\times}3$ )	7,538 positions, 0 mismatches
Large-board selftests ( $4{\times}7$ , $5{\times}6$ , $3{\times}10$ , $2{\times}14$ , $3{\times}9$ , $4{\times}6$ , $5{\times}5$ , $3{\times}7$ , $4{\times}5$ , three solver modes)	28,033 positions, 0 mismatches
Proof entries rejected by the second hash (path-specific collisions or mixed writes)	up to 552 per run ( $1{\times}18$ )

Appendix

Table 11: Validation of the solver used for all reported results.

Work	Result	Public artifact
MIGOS van der Werf et al. [2003]	$5{\times}5$ , basic ko	none known
MIGOS van der Werf and Winands [2009]	most boards up to 30 points, basic ko	none known, selected variations in the paper
Positional Linear Go Weninger and Hayward [2017]	$1{\times}n$ , $n\leq 9$ , PSK	none known
EWS Randall et al. [2024]	$5{\times}5$ , PSK	minimal example 2 2 2 https://github.com/davidowe/EWS-Python that solves up to $3{\times}3$ , $5{\times}5$ solver not released
Killall-Go Wu et al. [2023]	$7{\times}7$ openings	solver and solution trees, different problem
Sanko (this work)	Table 2	solver source, command line and outcome of every run

Appendix

Table 12: Public availability of the solvers behind published Go results.

Feb 24, 2026

High-Precision Estimation of the State-Space Complexity of Shogi via the Monte Carlo Method

Determining the state-space complexity of Shogi (Japanese Chess) has been a challenging problem, with previous combinatorial estimates leaving a gap of five orders of magnitude (

10^{64}

10^{69}

). This gap arises from the difficulty of distinguishing positions reachable from the initial position among the vast number of board configurations. In this paper, we present a high-precision statistical estimate of the number of reachable Shogi positions. Here, a position consists of the side to move, the board configuration, and the pieces in hand, without move history, and positions related by exchanging the two players or by horizontal reflection of the board are counted once. Our method combines Monte Carlo sampling with a reachability test that performs reverse search toward the set of ``King-King only'' (KK) positions rather than toward the single initial position. Since every KK position and the initial position are mutually reachable, reaching any KK position proves reachability, and removing pieces from the board is a much simpler objective than reconstructing the initial position. Based on a sample of five billion positions, we estimate the number of such positions in Shogi to be

6.55 \times 10^{68}

; both ends of the approximate

3σ

confidence interval round to this value at three significant digits. We also applied this method to Mini Shogi, obtaining approximately

2.38 \times 10^{18}

Sotaro Ishii, Tetsuro Tanaka

Graduate School of Arts and Sciences, The University of Tokyo · Information Technology Center, The University of Tokyo

Topic pending

Ask PDF

Jul 22, 2026

Anatomy of a Sound Neural Reasoner: One-Shot Amortization, First-Pass Poisoning, and Search Inertness in Clue-Rich Completion

Neural solvers are built to deduce, branch, and revise intermediate states. The Lattice Deduction Transformer (LDT) appears to do exactly that. In clue-rich Sudoku, it does not: one forward pass commits essentially the entire grid (every blank cell on standard 6x6, 94-96% on augmented 9x9), turning the iterative solver into a one-shot predictor wrapped in an exact verifier. All hard-slice failures are decided before search begins, when the first pass confidently deletes a value required by the true solution. We call this first-pass poisoning. Adding learned branching, MRV, backtracking, value exclusion, and shared nogoods (CoLT) does not change which Sudoku instances are solved; it cuts repeated invalid derivations 1,497-fold. At the frozen training budget, constraint-graph attention alone matches full-CoLT accuracy, while positional tables recover only under substantially longer training, indicating an optimization and sample-efficiency advantage rather than an absolute capacity difference. The diagnosis predicts two effective interventions. Digit-permutation augmentation raises 9x9 accuracy from below 1% to 96.5 +/- 0.3 across three training seeds on a symmetry-disjoint split. Test-time union over symmetry-transformed passes raises all three hard-slice checkpoints from 72.8-78.9% to 100% without retraining. On from-scratch graph coloring, one-shot behavior disappears and search changes accuracy. In clue-rich completion, LDT-like systems are one-shot amortized predictors rather than learned search procedures: accuracy is determined by calibration and symmetry, while search primarily removes computational waste.

Aleksey Komissarov

Neapolis University, Pafos, Cyprus

Sudoku Solving Inference-Time Search Structured Reasoning Constraint Satisfaction Test-Time Augmentation

Ask PDF

Aug 16, 2026

Solvable Sokoban Without a Solver via Diffusion

Deciding whether a Sokoban puzzle is solvable is PSPACE-complete (Culberson, 1997): solutions can be exponentially long and there is no short certificate to check. Solvability is also a fragile property, since even a single misplaced wall can silently render an entire puzzle unsolvable. In this work, we show that a transformer-based discrete diffusion model trained purely on tile completion, with no access to solvers, rewards, or solvability labels, achieves a solvability rate of 77.4%, with 94.5% of the remaining failures rendered solvable by removing a single wall. In other words, a global, search-heavy property follows from a local training objective: trained only to fill in masked cells, the model inherits solvability it was never trained on. An autoregressive model factorizes as

p(c_k \mid c_1 \dots c_{k-1})

, meaning a fixed order, always conditioned on a prefix. Masked diffusion does not: it hides a random subset of cells and learns

p(c_k \mid \text{any subset})

, so at generation time it can reveal cells in any order, each one conditioned on everything already placed, wherever it sits on the board. A puzzle's difficulty comes from exactly this kind of non-local interaction, a decision in one part of the grid constraining what will work somewhere else entirely. A generator that is not locked into a single fixed order is therefore a better structural match for the problem than one that is. The training pipeline is adapted from MD4 (Shi et al., 2024) and the dataset is DeepMind's Boxoban (Guez et al., 2019). The trained model and instructions for generating puzzles are publicly available.

Sina Baghal

Procedural Content Generation Diffusion Models Masked Diffusion Models

Ask PDF

Abstract

Explore similar work

High-Precision Estimation of the State-Space Complexity of Shogi via the Monte Carlo Method

Anatomy of a Sound Neural Reasoner: One-Shot Amortization, First-Pass Poisoning, and Search Inertness in Clue-Rich Completion

Solvable Sokoban Without a Solver via Diffusion