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

1981/09/01 by Aviezri S. Fraenkel, Aviezri S Fraenkel, David Lichtenstein · 6 citations
Computer Science · Economics, Econometrics and Finance · #Artificial Intelligence in Games #Constraint Satisfaction and Optimization #Sports Analytics and Performance

paper · doi:10.1016/0097-3165(81)90016-9

crossref issued 1981/09/01 · crossref published 1981/09/01 · crossref published-print 1981/09/01 · openalex publication_date 1981/09/01 · crossref created 2005/02/10 · crossref deposited 2019/01/29 · openalex created_date 2025/10/10 · crossref indexed 2026/06/05 · openalex updated_date 2026/07/23

Cited by

• Complexity of n-Queens Completion
• Fast algorithms for finding randomized strategies in game trees
• The Othello game on an n × n board is PSPACE-complete
• Computer chess [wikipedia]
• EXPTIME [wikipedia]
• P versus NP problem [wikipedia]