Gobang is PSPACE-complete

DOI10.1007/BF00288536zbMath0401.90112WikidataQ29999401 ScholiaQ29999401MaRDI QIDQ1255445

Stefan Reisch

Publication date: 1980

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

Computational ComplexityGeographyGobangPspace-Completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05)

Related Items

Unnamed Item ⋮ QUIXO is EXPTIME-complete ⋮ Computing a perfect strategy for nxn chess requires time exponential in n ⋮ Theory of annihilation games. I ⋮ On the fairness and complexity of generalized \(k\)-in-a-row games ⋮ An algorithmic analysis of the Honey-Bee game ⋮ Recent results and questions in combinatorial game complexities ⋮ Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete. ⋮ The Othello game on an \(n\times n\) board is PSPACE-complete ⋮ Rikudo is NP-complete

Cites Work

• Unnamed Item
• On the complexity of some two-person perfect-information games

This page was built for publication: Gobang is PSPACE-complete