Computing a perfect strategy for nxn chess requires time exponential in n
From MaRDI portal
Publication:1156090
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
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
This page was built for publication: Computing a perfect strategy for nxn chess requires time exponential in n
