GO Is Polynomial-Space Hard

Cited in

(63)

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

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)