Computing a perfect strategy for nxn chess requires time exponential in n

DOI10.1016/0097-3165(81)90016-9zbMath0467.90100OpenAlexW2091133474WikidataQ29012899 ScholiaQ29012899MaRDI QIDQ1156090

David Lichtenstein, Aviezri S. Fraenkel

Publication date: 1981

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(81)90016-9

zbMATH Keywords

chessparticular gamecomplete in exponential timecomputing a perfect strategynxn board

Mathematics Subject Classification ID

Game theory (91A99) 2-person games (91A05)

Related Items (24)

Games, Puzzles and Treewidth ⋮ Complexity, appeal and challenges of combinatorial games ⋮ On variants of vertex geography on undirected graphs ⋮ Single-suit two-person card play ⋮ Unnamed Item ⋮ A short certificate of the number of universal optimal strategies for stopping simple stochastic games ⋮ On the complexity of computational problems associated with simple stochastic games ⋮ QUIXO is EXPTIME-complete ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Theory of annihilation games. I ⋮ A finite set of functions with an EXPTIME-complete composition problem ⋮ Remarks on History and Presence of Game Tree Search and Research ⋮ Hanabi is NP-hard, even for cheaters who look at their cards ⋮ Complexity of path-forming games ⋮ Playing Savitch and Cooking Games ⋮ An algorithmic analysis of the Honey-Bee game ⋮ Computer Go: An AI oriented survey ⋮ The computational complexity of Angry Birds ⋮ Domino-tiling games ⋮ Complexity of path discovery game problems ⋮ Recent results and questions in combinatorial game complexities ⋮ On the complexity of chess ⋮ The Othello game on an \(n\times n\) board is PSPACE-complete

Cites Work

• Unnamed Item
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• Gobang is PSPACE-complete
• Provably Difficult Combinatorial Games
• GO Is Polynomial-Space Hard

This page was built for publication: Computing a perfect strategy for nxn chess requires time exponential in n