CS Paper Radar

Go-Go-Go: the game of Go without turns

Andrea Cambiaghi, Marco Tarini

cs.HC ·submitted 2026-11-04 16:59 UTC · v1

Abstract

The study of variants of classic games has a long history, with chess alone inspiring countless variants that have been proposed, analyzed, and studied. The game of Go, despite rivaling chess in age, cultural relevance, popularity, and strategic depth, has seen drastically fewer variants. We introduce Go-Go-Go, a variant of the classic game of Go where there are no turns, and players play stones simultaneously and asynchronously on the board. The variant (which is to be played through a computer) includes a basic mechanism to avoid excessive spamming of moves, by imposing a minimal delay between moves that depends on their relative spatial distance. Apart from the lack of time discretization, most of the ruleset of the original game is either directly maintained or adapted in a natural way that preserves the original spirit. The first playtesting indicates that this results in the preservation of much of the emerging strategies and "flavor" of Go, while replacing the long strategic reasoning with fast paced, instinctive action fueled by quick reflexes. Play testers also report the need to balance immediate but suboptimal reactions with more reasoned but slower plays. We offer a publicly available, playable, OpenSource, and online reference implementation of Go-Go-Go at http://gogogo.di.unimi.it

Closest papers

Nearest neighbours by meaning across the whole index.

Sowing the Seeds of Intractability: Kalah is PSPACE-complete

cs.CC cs.GTmath.CO ·2026-11-12 ·Ethan Dickey, Ethan Mader
similarity 0.58
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

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.58
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

Test-time Reinforcement Learning in Imperfect Information Games

cs.GT ·2026-08-31 ·Ondrej Kubicek, Viliam Lisy, Tuomas Sandholm
similarity 0.56
Abstract

Test-time reasoning has significantly improved performance in domains ranging from games to language models. However, test-time policy changes with formal guarantees on the performance of the resulting strategy remain a challenge in two-player zero-sum imperfect-information games. Existing solutions are limited to tabular methods or single gradient step updates. In this work, we investigate policy-gradient algorithms as a method for scalable test-time reasoning. We extend the concept of gadget game, tabular technique for test-time search, to the reinforcement learning setting. Unlike prior approaches, we represent the gadget game implicitly by modified sampling and neural policy rather then explicitly by constructing it, thereby removing constraints on subgame size. Furthermore, we formally prove that, unlike prior tabular algorithms, regularized policy-gradient algorithms limit possible strategy degradation caused by test-time reasoning, even without the gadget games. Our evaluation across small- and large-scale games confirms that additional test-time training often substantially improves performance relative to the blueprint strategy.

0.31

AI Teaches Humans to Handle Complexity in the Game of Go

cs.AI ·2026-10-23 ·Adamo Cerioli, Vito D. P. Servedio, Gabriele Cerioli, Antonio Villani, Carlo Metta
similarity 0.56
Abstract

Strategic decision-making in complex environments requires balancing local stability against global coordination. Using the game of Go as a bounded empirical testbed, we investigate how biological and artificial agents navigate this trade-off by formalizing a network-derived metric of strategic tension defined via the spectral radius of spatial dependency matrices. Across human skill progression, tension systematically decays from novices to masters as uncoordinated tactical skirmishes give way to disciplined territorial stabilization. However, a longitudinal analysis of professional play spanning 1980--2026 reveals a striking historical paradox: following the superhuman breakthrough of AlphaGo in 2016, elite human matches display a marked surge in sustained tension. A two-dimensional projection based on move distance and captures places modern professionals close to neural engines, separating their tension from the local contact fighting of novices and from random noise. Consequently, strategic tension acts as a macroscopic order parameter for decision paradigms rather than raw computational strength. Beyond the game of Go, these findings establish a constructive paradigm for human-AI interaction, indicating how artificial systems can act as cognitive scaffolding that expands biological heuristics and elevates human capacity to navigate higher-order complexity across professional training and decision-making domains.

0.31

Rome Wasn't Built in One Turn: Replay-Grounded Reward Signals for Long-Horizon Freeciv Agents

cs.AI ·2026-10-30 ·Yanchen Liu, Xinyu Che, Brihi Joshi, Renzo Fukuda, Junhua Liu +4 more
code/data similarity 0.55
Abstract · 22 pages, 3 figures, 12 tables. Code: https://github.com/jamesnulliu/CivMarshmallow ; Checkpoints: https://huggingface.co/collections/CivMar…

Training language-model agents to play long-horizon strategy games is hard because deterministic feedback is sparse and often arrives only at the end of a game. In-game scores can offer dense signals, but they do not reliably predict future outcomes: in 8-68% of position pairs across eight strategy games, the higher-scoring position leads to the worse outcome. We term this phenomenon scoreboard traps. In Freeciv, an open-source turn-based empire-building game where several players manage units, cities, and diplomacy over hundreds of turns, we look into better reward signals for gameplay agents. To facilitate this, we build CivHarness, an open system that saves current game states, branches on different decisions, and replays the game to future turns to provide measurable long-horizon feedback from saved positions. We use CivHarness to train CivTelescope, an LLM Judge that predicts which one of two game positions will yield the better outcome. On scoreboard-trap pairs, CivTelescope is 1.3-2.0 times more accurate than off-the-shelf language models, and it generalizes to new game starts, later turns, and unseen rules. We then train a Freeciv gameplay agent with CivTelescope as a dense reward, and call this recipe CivMarshmallow. When used in the middle stage of the game where scoreboard traps are common, CivMarshmallow reaches an average training phase gain of 8.94 points, 77% more than the best baseline, the end-of-game reward. Over the full 120-turn game, CivMarshmallow uses a hybrid reward that starts from the scoreboard or the end-of-game reward and shifts to CivTelescope as the game advances; this hybrid reward scores highest among the rewards we compare.

0.39

SAGE: Structured Strategic Reasoning for Efficient LLM Game Playing

cs.AI ·2026-09-28 ·Zhiwei Chen, Tianchun Wang, Zhongtao Rao, Haiming Zhu, Ding Cao +1 more
code/data similarity 0.55
Abstract · 31 pages with multiple figures

A strong LLM strategic agent should reason prospectively over uncertain futures, adapt its strategy to opponents' behavioral tendencies, and continuously recalibrate its decision process from interaction experience. However, incorporating these sources in free-form reasoning could lead to unsupported strategic assumptions, inconsistent opponent estimates, and harmful interference from irrelevant historical interactions. To address these issues, we propose SAGE, a training-free inference-time framework that structures LLM strategic reasoning around three coordinated operations: anchor, adapt, and recalibrate. SAGE first anchors reasoning to an equilibrium policy that provides a strategically valid prior. It then conditions deviations from this anchor on a soft belief over opponent behavioral tendencies, enabling opponent-specific exploitation. Finally, SAGE distills strategically related interactions into counterfactual hypotheses about previously missing considerations, allowing past experience to recalibrate the model's reasoning. We evaluate SAGE on three repeated imperfect-information games: Leduc Hold'em, Liar's Dice, and Goofspiel, against various opponent types in each game. Compared with reasoning-intensive LLM agents, including Suspicion-Agent, ReTA, Agent-Pro, EMO, and Hypothetical Minds, SAGE achieves up to a 127.6% payoff improvement in Liar's Dice while reducing input and output token usage by up to 80% and 90%, respectively. In direct match-up play, it attains non-negative mean payoff against 5/10, 8/10, and 8/10 evaluated opponents in Leduc Hold'em, Liar's Dice, and Goofspiel, respectively, while using relatively fewer tokens. Code is available at https://github.com/chenzhwsysu57/SAGE.

0.33

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.55
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

SpeedrunBench: Challenging LLM Agents with Video Game Speedrunning

cs.AI ·2026-10-06 ·Yoshinari Fujinuma, Keisuke Kamahori, Ryuto Koike, Abdelrahman Madkour, Varun Prashant Gangal +6 more
benchmark similarity 0.54
Abstract

Frontier LLM agents have been shown to be capable of solving increasingly complex tasks for which humans have measurable solutions. This begs the pertinent question of whether LLM agents can go beyond what humans have already solved. The ability to develop sophisticated strategies to tackle consequential problems becomes paramount as well-trodden, human-developed solutions become insufficient for problems for which we lack context or enough training data. We study agents' capability of such strategy formation through the communal practice of video game speedrunning. In speedrunning, practitioners compete to find the fastest way to complete a video game under certain conditions, and in so doing uncovering interesting unorthodox play styles that require a thorough understanding and mastery of the underlying game mechanics. We introduce SPEEDRUNBENCH, a benchmark that evaluates frontier LLM agents across 9 different games. To perform well in this benchmark, agents must repeatedly improve their strategy, reflect on their performance, exploit their gained knowledge, and reason across a long-horizon of actions to improve on an increasingly difficult problem: being faster than themselves and everyone else. Our experiments show that while frontier agents approach human world records in simple platformer games, they remain behind human performance on longer, more complex games under practical budgets. These results suggest that SPEEDRUNBENCH is a useful testbed for studying agents' strategy formation capabilities as well as being a saturation-resistant evaluation measure, as there is almost always a faster completion time waiting to be discovered.

0.16