The complexity of checkers on an N × N board
Authors:
- A. S. FraenkelAFA. S. Fraenkel
- M. R. GareyMGM. R. Garey
- D. S. JohnsonDJD. S. Johnson
- T. SchaeferTST. Schaefer
- Y. YeshaYYY. Yesha
- 1 October 1978
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 55-64
Abstract
We consider the game of Checkers generalized to an N × N board. Although certain properties of positions are efficiently computable (e.g., can Black jump all of White's pieces in a single move?), the general question, given a position, of whether a specified player can force a win against best play by his opponent, is shown to be PSPACE-hard. Under certain reasonable assumptions about the "drawing rule" in force, the problem is itself in PSPACE and hence is PSPACE-complete.Keywords
This publication has 6 references indexed in Scilit:
- GO is pspace hard1978
- On the complexity of some two-person perfect-information gamesJournal of Computer and System Sciences, 1978
- The Planar Hamiltonian Circuit Problem is NP-CompleteSIAM Journal on Computing, 1976
- A Combinatorial Problem Which Is Complete in Polynomial SpaceJournal of the ACM, 1976
- Alternation1976
- Efficient Planarity TestingJournal of the ACM, 1974