Spencer Congero

Losing at Checkers is Hard

2018 · arXiv (Cornell University)

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 …