N by N Checkers is Exptime Complete
Author:
- J. M. RobsonJRJ. M. Robson
- 1 May 1984
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 13 (2) , 252-267
Abstract
The game of Checkers can easily be generalized to be played on an N by N board and the complexity of deciding questions about positions regarded as a function of N. This paper considers mainly the question of whether a particular player can force a win from a given position and also the question of what is the best move in a given position. Each of these problems is shown to be complete in exponential time. This means that any algorithm to solve them must take time which rises exponentially with respect to some power of N and moreover that they are amongst the hardest problems with such a time bound.For instance if there are any problems solvable in exponential time but not in polynomial space, then these two problems are amongst them.Keywords
This publication has 5 references indexed in Scilit:
- Computing a perfect strategy for n × n chess requires time exponential in nJournal of Combinatorial Theory, Series A, 1981
- GO Is Polynomial-Space HardJournal of the ACM, 1980
- Classes of Pebble Games and Complete ProblemsSIAM Journal on Computing, 1979
- Provably Difficult Combinatorial GamesSIAM Journal on Computing, 1979
- The complexity of checkers on an N × N board1978