Paper by Erik D. 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, 2019, pages 103–118, 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:

The paper is available in PDF (510k).

See information on file formats.

[Google Scholar search]

Related webpages:

Checkers Font