Gobang is PSPACE-complete

DOI10.1007/BF00288536MaRDI QIDQ1255445zbMATH OpenWikidataFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• On the complexity of some two-person perfect-information games

Cited in

(11)

• Computing a perfect strategy for nxn chess requires time exponential in n
• Recent results and questions in combinatorial game complexities
• Rikudo is NP-complete
• Theory of annihilation games. I
• Quantified Boolean Solving for Achievement Games
• QUIXO is EXPTIME-complete
• The Othello game on an \(n\times n\) board is PSPACE-complete
• Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.
• An algorithmic analysis of the Honey-Bee game
• scientific article; zbMATH DE number 7232976 (Why is no real title available?)
• On the fairness and complexity of generalized \(k\)-in-a-row games

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

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