Paper by Martin L. Demaine

Reference:
Jeffrey Bosboom, Spencer Congero, Erik D. Demaine, Martin L. Demaine, and Jayson Lynch, “Losing at Checkers is Hard”, in The Mathematics of Various Entertaining Subjects (MOVES 2017), volume 3, to appear, Princeton University Press.

Abstract:
We prove computational intractability of variants of checkers: (1) deciding whether there is a move that forces the other player to win in one move is NP-complete; (2) checkers where players must always be able to jump on their turn is PSPACE-complete; and (3) cooperative versions of (1) and (2) are NP-complete. We also give cooperative checkers puzzles whose solutions are the letters of the alphabet.

Comments:
This paper is also available as arXiv:1806.05657.

Availability:
Currently unavailable. If you are in a rush for copies, contact me.
[Google Scholar search]

Related webpages:
Checkers Font


See also other papers by Martin Demaine.
These pages are generated automagically from a BibTeX file.
Last updated November 20, 2018 by Martin Demaine.