The Othello game on an \(n\times n\) board is PSPACE-complete

DOI10.1016/0304-3975(94)90131-7zbMath0801.68080OpenAlexW2088043394WikidataQ29030258 ScholiaQ29030258MaRDI QIDQ1314386

Shigeki Iwata, Takumi Kasai

Publication date: 22 February 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90131-7

zbMATH Keywords

bipartite graphsPSPACE-completeOthellogeneralized geography

Mathematics Subject Classification ID

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

Related Items (12)

Games, Puzzles and Treewidth ⋮ On the complexity of connection games ⋮ Unnamed Item ⋮ Phutball is PSPACE-hard ⋮ QUIXO is EXPTIME-complete ⋮ On the fairness and complexity of generalized \(k\)-in-a-row games ⋮ Automated verification of state sequence invariants in general game playing ⋮ An algorithmic analysis of the Honey-Bee game ⋮ Computational complexity of puzzles and related topics ⋮ The computational complexity of forced capture Hnefatafl ⋮ Cognitive and computational complexity: considerations from mathematical problem solving ⋮ Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.

Cites Work

• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• Computing a perfect strategy for nxn chess requires time exponential in n
• On the complexity of some two-person perfect-information games
• Gobang is PSPACE-complete
• N by N Checkers is Exptime Complete
• GO Is Polynomial-Space Hard
• Alternation
• Planar Formulae and Their Uses
• A Combinatorial Problem Which Is Complete in Polynomial Space

This page was built for publication: The Othello game on an \(n\times n\) board is PSPACE-complete