Phutball Endgames are Hard
<|reference_start|>Phutball Endgames are Hard: We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game. In contrast, the similar problems of determining whether there is an immediately winning move in checkers, or a move that kings a man, are both solvable in polynomial time.<|reference_end|>
@article{demaine2000phutball,
    title={Phutball Endgames are Hard},
    author={Erik D. Demaine, Martin L. Demaine, and David Eppstein},
    journal={More Games of No Chance, MSRI Publications 42, 2002, pp. 351-360},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0008025},
    primaryClass={cs.CC cs.GT}
}