Paper by Erik D. Demaine
- Jeffrey Bosboom, Erik D. Demaine, and Mikhail Rudoy, “Computational Complexity of Generalized Push Fight”, in Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), La Maddalena, Italy, June 13–15, 2018, 11:1–11:21.
We analyze the computational complexity of optimally playing the two-player
board game Push Fight, generalized to an arbitrary board and number of pieces.
We prove that the game is PSPACE-hard to decide who will win from a given
position, even for simple (almost rectangular) hole-free boards. We also
analyze the mate-in-1 problem: can the player win in a single turn?
One turn in Push Fight consists of up to two “moves” followed by a
mandatory “push”. With these rules, or generalizing the number of
allowed moves to any constant, we show mate-in-1 can be solved in polynomial
time. If, however, the number of moves per turn is part of the input, the
problem becomes NP-complete. On the other hand, without any limit on the
number of moves per turn, the problem becomes polynomially solvable again.
- The full version of this paper is available as arXiv:1803.03708.
- The paper is available in PDF (1383k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 14, 2019 by