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

DOI10.1016/0097-3165(81)90016-9zbMATH Open0467.90100DBLPjournals/jct/FraenkelL81OpenAlexW2091133474WikidataQ29012899 ScholiaQ29012899MaRDI QIDQ1156090FDOQ1156090

Authors: Aviezri S. Fraenkel, David Lichtenstein 

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

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

Cites Work

• Title not available (Why is that?)
• Provably Difficult Combinatorial Games
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• GO Is Polynomial-Space Hard
• Gobang is PSPACE-complete

Cited In (27)

• Playing Savitch and cooking games
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nimber-preserving reduction: game secrets and homomorphic Sprague-Grundy theorem
• Complexity of path-forming games
• Complexity, appeal and challenges of combinatorial games
• Remarks on history and presence of game tree search and research
• Domino-tiling games
• On variants of vertex geography on undirected graphs
• A finite set of functions with an EXPTIME-complete composition problem
• Games, Puzzles and Treewidth
• Title not available (Why is that?)
• Recent results and questions in combinatorial game complexities
• On the complexity of chess
• Chess is hard even for a single player
• On the complexity of computational problems associated with simple stochastic games
• Computer Go: An AI oriented survey
• The Othello game on an \(n\times n\) board is PSPACE-complete
• An algorithmic analysis of the Honey-Bee game
• Theory of annihilation games. I
• Cognitive and computational complexity: considerations from mathematical problem solving
• A short certificate of the number of universal optimal strategies for stopping simple stochastic games
• Complexity of path discovery game problems
• The computational complexity of Angry Birds
• QUIXO is EXPTIME-complete
• Single-suit two-person card play
• Hanabi is NP-hard, even for cheaters who look at their cards

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

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