GO Is Polynomial-Space Hard

Cited in

(65)

PSPACE-Hardness of some combinatorial games
Single-suit two-person card play
Storage allocation is NP-hard
Computing a perfect strategy for nxn chess requires time exponential in n
Playing disjunctive sums is polynomial space complete
Theory of annihilation games. I
Undirected edge geography
Geography
Complexity of path-forming games
The Othello game on an \(n\times n\) board is PSPACE-complete
A short certificate of the number of universal optimal strategies for stopping simple stochastic games
The Go polynomials of a graph.
Recent results and questions in combinatorial game complexities
Applying adversarial planning techniques to Go
Decision algorithms for multiplayer noncooperative games of incomplete information
On variants of vertex geography on undirected graphs
TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable
Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.
Complexity, appeal and challenges of combinatorial games
Rikudo is NP-complete
On the computational complexities of various geography variants
\(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\)
On the number of go positions on lattice graphs
The shortest connection game
On the fairness and complexity of generalized \(k\)-in-a-row games
\textsc{Havannah} and \textsc{TwixT} are PSPACE-complete
Single-player and two-player buttons \& scissors games (extended abstract)
On the complexity of connection games
On the PSPACE-completeness of Peg Duotaire and other peg-jumping games
\textsc{Transverse wave}: an impartial color-propagation game inspired by social influence and quantum NIM
UNO is hard, even for a single player
Deciding the winner in \(k\) rounds for DISJOINT ARROWS, a new combinatorial partizan game
Phutball is PSPACE-hard
Remarks on history and presence of game tree search and research
The frontier of decidability in partially observable recursive games
Hanabi is NP-hard, even for cheaters who look at their cards
Lower bounds for multiplayer noncooperative games of incomplete information
Computer Go
Computer Go: An AI oriented survey
Feedback game on Eulerian graphs
Bichromatic coloring game on triangulations
On the complexity of computational problems associated with simple stochastic games
Feedback game on 3-chromatic Eulerian triangulations of surfaces
Nimber-preserving reduction: game secrets and homomorphic Sprague-Grundy theorem
Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies
Geography, Kotzig's Nim, and variants
Hackenforb the chameleon: a game capable of mimicking (practically) any misère game
Solving Maker-Breaker games on 5-uniform hypergraphs is PSPACE-complete
Trail trap: a variant of partizan edge geography
Epistemic skills: logical dynamics of knowing and forgetting
\textsf{PSPACE}-completeness of \(k\)-\textsc{Atropos}
Computational complexity of \textsc{Turning Tiles}
The one-round Voronoi game replayed
An algorithmic analysis of the Honey-Bee game
Epistemic skills: reasoning about knowledge and oblivion
Between burning and cooling: liminal burning on graphs
On the shortest path game
The King chasing problem in Chinese Chess is NP-hard
Turing machines with access to history
The complexity of two-player games of incomplete information
Learning to score final positions in the game of Go
The game chromatic number and the game colouring number of cactuses
New complexity results about Nash equilibria
A finite set of functions with an EXPTIME-complete composition problem
PSPACE-completeness of an escape problem

This page was built for publication: GO Is Polynomial-Space Hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3873542)