CS Paper Radar

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

Sami Kharma, Florian Schintke

cs.AI ·submitted 2026-10-21 08:37 UTC · v1
theoryunusual

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.

Comment
15 pages, 7 figures, 12 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Go under Chinese Rules with a Succinct Game History is Complete for Exponential Space

cs.GT cs.CC ·2026-11-13 ·Markus Bläser, Felix Czerner
top venuetheory similarity 0.60
Abstract · A preliminary version of this paper appears in the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)

The complexity of games is a central topic in combinatorics, algorithms, and computational complexity theory. It asks how difficult it is to determine the winner of a combinatorial game under optimal play. Many games, such as Hex or Othello, are PSPACE-complete: the game tree has polynomial depth, so the game can be decided in PSPACE. However, some games allow exponentially long plays, for instance Chess (without a generalized 50-move rule) or Go under Japanese rules; these are complete for exponential time. To prevent infinite games, some games employ a no-repetition rule (super-ko rule), for instance Go under Chinese rules. Robson (1984) proved that Chess and Checkers with a no-repetition rule are even harder: deciding whether the first player has a winning strategy is EXPSPACE-complete. Since then, it has been an open problem whether Go with a no-repetition rule is EXPSPACE-complete, too. The complexity of a game under a no-repetition rule is typically interpreted as follows: given a board position, decide whether the first player has a winning strategy such that no repetition occurs from that position on. We introduce the concept of a succinct game history: a Boolean circuit that, given a board position, outputs 1 if the position is in the game history and 0 otherwise. It serves as a "judge" that tells the players whether a move is illegal because it creates a repetition. We prove that deciding whether Black has a winning strategy in Go with a no-repetition rule is EXPSPACE-complete when the game history is given succinctly. Moreover, the starting position in our hardness proof is reachable by legal gameplay, which has not always been the case in prior proofs.

0.45

Zero-Shot Weight-Space Programming Across a Difficulty-Graded Ladder of Two-Player Games

cs.AI ·2026-11-06 ·Eduardo C. Garrido-Merchán
similarity 0.58
Abstract

Weight-space programming sets every weight of a feed-forward network by hand, from an explicit specification of the desired computation, with no gradient descent and no training data anywhere in the construction. We ask how far a large language model can carry this practice, zero-shot, across games of deliberately increasing difficulty. We design a four-rung ladder (Nim, tic-tac-toe, two sizes of Connect Four, and a chess endgame) spanning four axes of difficulty, and build a second, independent network at each rung, using a structurally unrelated game at matched difficulty, to separate what a rung's finding says about the difficulty level from what it says about the one game used to measure it. Ten networks are built and independently verified. Six admit a complete, non-statistical proof of correctness against an independent oracle. The chess-endgame rung is exact where correctness is cheap, move legality and, in one network, an exact one-ply mate detector, and collapses where it is expensive, composing a multi-move mating plan, from 84.1-100% success at the one-ply tactics it was built to get right down to 0.57-9.13% in full adversarial play; its replicate shows this collapse is an order of magnitude less severe under a shorter required plan and exact rather than heuristic safety checks. The standard-sized rung confirms, by holding hand-set evaluation weights fixed and adding only shallow search, that the remaining gap is an architectural ceiling rather than a matter of engineering effort, and this exact collapse reproduces across two structurally unrelated games. We release all ten networks, their independent oracles, construction-cost measurements, and a cold-prompt protocol for a future cross-model comparison

0.37

Sowing the Seeds of Intractability: Kalah is PSPACE-complete

cs.CC cs.GTmath.CO ·2026-11-12 ·Ethan Dickey, Ethan Mader
similarity 0.55
Abstract · 55 pages, 6 figures, 5 tables

Kalah is a classic two-player game in the mancala family of sowing games. Computers have solved several standard-size starting positions, but the complexity of the game on boards of growing size has remained open. We study the natural generalization in which the number of pits per side is part of the input and an arbitrary position is given, with the stone counts given in unary. We show that deciding whether a designated player can force a win from such a position is PSPACE-complete. The hard positions have Alice to move first and both stores initially empty. The same positions are hard under either common convention for capture opposite an empty pit, and with or without the bonus rule, which gives a player another turn when the last stone is sown into their own store. We introduce Line Kalah as an intermediate problem, a game on a line in which stones that leave the line effectively disappear and Alice must save each of her target pits before Bob captures it, and we reduce quantified Boolean formulas to it. The reduction uses a set of sequential timer piles whose last stones approach a group of targets, forcing Alice to choose between two captures in order to set the truth value of a variable, and a final capture gadget to test a clause chosen by Bob (only one is needed adversarially). Since either player may move any pile at any time, the stages are placed so that premature timer firings protect earlier potential targets. For a true formula, Alice's strategy against arbitrary opposing play either gains enough time to save the remaining targets (after Bob deviates from the intended play) or reaches the final test with a correctly encoded, protected input. Finally, the line positions are embedded in Kalah with both stores empty. A separate Bob pit holds the score adjustment, so the winner takes a strict majority of the stones.

0.24

Solving Streett and Emerson-Lei Games with Universal Trees

cs.GT cs.LO ·2026-08-17 ·Daniel Hausmann, Marcin Jurdzinski, Nir Piterman
similarity 0.52
Abstract

Nearly a decade ago, Calude et al. showed that parity games can be solved in quasi-polynomial time. This result is now understood in terms of universal trees. By reduction to parity games, the quasi-polymonial result can benefit all omega-regular games. However, beyond such reductions, and with the exception of Rabin games, our understanding of the role of universal trees in direct solutions is still quite limited. In this work, we refute the common view that universal trees are relevant only for games that admit memoryless winning strategies. We contribute a full understanding of how universal trees interact with Zielonka trees for the solution of Streett and Emerson-Lei games. As a consequence, we show that winning regions and strategies in Streett games with $n$ vertices, $m$ edges, and $k$ pairs can be computed in time $O(mk\log(k)k!|U(n,k)|)$, where $U(n,k)$ is a universal tree for $n$ leaves and depth $k$. This improves upon the best previously known complexity result for Streett games, which relied on reduction to parity games and their quasi-polynomial solution. Furthermore, we show that winning regions and strategies for Emerson-Lei games with $n$ vertices, $m$ edges, and $c$ colors can be computed in time $O(mc\log(c)c!|U(n,c/2)|)$, again improving over reductions to parity games. Notably, our approach yields memory-optimal strategies, in contrast to those obtained via reductions to parity games. Finally, we show how universal trees can be used to bound the recursion tree of the Zielonka-McNaughton algorithm for Emerson-Lei games. This leads to a symbolic algorithm that replaces the factor $n^c$ in the time complexity of existing symbolic approaches with $|U(n,c)|$.

0.18

Rózsa: Certified Equational Reasoning

cs.LO ·2026-10-19 ·Georgios Kissas
similarity 0.52
Abstract

When does one equation imply another? Stage 2 of the SAIR Mathematics Distillation Challenge required teams to submit solvers to answer this question for sets equipped with a binary operation. For these sets, associativity, commutativity, or any other algebraic property was not assumed. Each answer required a proof or counterexample that could be verified by Lean. Programs also had to respect fixed resource limits. We present Rózsa, a Python solver that searches for both kinds of evidence. It begins with simple tests and considers more extensive searches when those fail. To find a proof, it applies a given equation and derives any further equations as needed, keeping a record of each step. To find a counterexample, it searches for operations on finite sets. It also tests one fixed infinite model. The given equation must hold for every assignment, while the target equation must fail for at least one. In either case, Rózsa turns the evidence into a Lean certificate. The submitted solver solved 199/200 problems (99.5%) in the official main evaluation getting the 6th overall position. Additional tests show that the solver can prove many implications linked by long chains of known results, but has limited success with infinite counterexamples. We explain the search methods, how they fit together, and what the unsolved cases reveal about their limits.

0.16

Rabin Games Revisited

cs.FL ·2026-10-11 ·Antonio Di Stasio, Moshe Y. Vardi
published similarity 0.51
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898

Rabin games have their roots in Michael Rabin's seminal work on automata over infinite trees and form a classical model for infinite-round games with ω-regular winning conditions. They play a central role in automata theory and temporal synthesis: translating an LTL specification into an equivalent deterministic Rabin automaton reduces synthesis to solving a Rabin game. In practice, however, Rabin games are typically solved indirectly, via parity games. One possible reason is that many direct algorithms have a factorial dependence on the Rabin index k, the number of Rabin pairs. In this work, we revisit Rabin's 1972 recursive algorithm. The algorithm is implicit in Rabin's proof and intertwined with finite-state determinacy. First, we "excavate" it as an explicit arena-based solver using standard reachability- and Büchi-game solving as basic building blocks, thus avoiding the exponential dependence on the alphabet in Rabin's original presentation. Second, we show that memoization removes the factorial term from the recursion-tree analysis. Finally, we introduce a variation that recurses on the Rabin index. These results provide a modern analysis of Rabin's recursive method and a basis for studying direct Rabin-game solvers for temporal synthesis.

0.37

A Certificate-Producing Cascade for Equational Implication: The SAIR EQT2 Stage 2 Solver

cs.CL ·2026-09-01 ·Haobo Ma, Wenlin Zhang, Manuel Israel Cázares
benchmark similarity 0.51
Abstract · 12 pages

The SAIR Mathematics Distillation Challenge on Equational Theories asks a solver to classify whether one magma identity implies another and, for either verdict, to return a certificate accepted by a deterministic Lean judge. We present a single-file solver organized as a cheapest-first cascade. Its false branch combines coefficient tests over structured algebra families, bounded finite-model search, an explicit central-groupoid witness, and several infinite-carrier witnesses. Its true branch is a proof-producing ordered unit superposition procedure with Knuth-Bendix ordering, bidirectional demodulation, indexing, memoised substitution, and anytime size deepening. Search results remain outside the trusted base: successful derivations are replayed as small Lean terms, and countermodels are rechecked by the competition judge. The frozen solver is a 189,504-byte Python file with SHA-256 f2392533c9f4c03b.... In local runs through official judge revision 2848228, it produced accepted certificates for all 1,889 rows of the six public sets with no language-model calls. Separate measurements recorded full agreement on the 800 published Stage 1 evaluation-distribution problems, 100 accepted rows in the canonical Marathon manifest without tokens, and 200 accepted rows in the hosted playground. These are regression and playground measurements, not a leaderboard result and not evidence about a hidden set. All quantitative claims are tied to immutable result ledgers; the paper makes no completeness or comparative-superiority claim.

0.25

Causal Resolution of Undefined Answers in Datalog with Negation

cs.DB ·2026-11-09 ·Ratan Bahadur Thapa
similarity 0.50
Abstract

Unstratified negation may leave the answer to a Boolean Datalog query undefined under the well-founded semantics. We study database causality in this setting by asking which fact insertions and deletions realize a prescribed transition and which other changes preserve the observed query answer while making a designated fact pivotal. Such a set of changes to other facts is a contingency for the designated fact and the prescribed transition. Our game representation assigns one shared move to each mutable fact and preserves query values and intervention distances. Pairing source and target certificates characterizes all minimum contingencies for the six transitions among true, false, and undefined. When inserting or deleting a move resolves a draw, a directed tree traces the newly winning and losing positions along alternating paths to the source of that move. For the fixed one-rule win--move program, deciding whether a contingency of size at most $k$ exists is $\mathrm{NP}$-complete for each transition, even on bounded-degree graphs. Computing the minimum size is $\mathrm{FP}^{\mathrm{NP}[\log]}$-complete, and counting minimum contingencies is $\#\mathrm{P}$-hard under polynomial-time Turing reductions. When only one of true and false is reachable, the prime implicants of undefinedness satisfied at the observation cover every undefined state, and their supports induce nonempty subtrees of a common tree, we compute a minimum resolving intervention in polynomial time from the game instance. From the explicit tree and these implicants, we construct an equally large family of disjoint supports, certifying optimality.

0.28