Paper by Erik D. Demaine

Reference:

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.

BibTeX

@InProceedings{PushFight_FUN2018,
  AUTHOR        = {Jeffrey Bosboom and Erik D. Demaine and Mikhail Rudoy},
  TITLE         = {Computational Complexity of Generalized {Push} {Fight}},
  BOOKTITLE     = {Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018)},
  MONTH         = {June 13--15},
  YEAR          = 2018,
  ADDRESS       = {La Maddalena, Italy},
  PAGES         = {11:1--11:21},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.4230/LIPIcs.FUN.2018.11},
  dblp          = {https://dblp.org/rec/conf/fun/BosboomDR18},
  comments      = {The full version of this paper is available as
                   <A HREF="https://arXiv.org/abs/1803.03708">arXiv:1803.03708</A>, and from <A HREF="https://doi.org/10.4230/LIPIcs.FUN.2018.11">LIPIcs</A>.},
}

Abstract:

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.

Comments:

The full version of this paper is available as arXiv:1803.03708, and from LIPIcs.

Availability:

The paper is available in PDF (1383k).

See information on file formats.

[Google Scholar search]