LIPIcs.FUN.2018.11.pdf
- Filesize: 1.35 MB
- 21 pages
Document
Computational Complexity of Generalized Push Fight
Authors
-
Part of:
Volume:
9th International Conference on Fun with Algorithms (FUN 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-04
Cite As Get BibTex
Jeffrey Bosboom, Erik D. Demaine, and Mikhail Rudoy. Computational Complexity of Generalized Push Fight. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FUN.2018.11
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Problems, reductions and completeness
Keywords
- board games
- hardness
- mate-in-one
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Jeffrey Bosboom, Erik D. Demaine, and Mikhail Rudoy. Computational Complexity of Generalized Push Fight. arxiv:1803.03708, 2018. URL: https://arxiv.org/abs/1803.03708.
-
Erik D. Demaine, Martin L. Demaine, and David Eppstein. Phutball endgames are NP-hard. In R. J. Nowakowski, editor, More Games of No Chance, pages 351-360. Cambridge University Press, 2002.
- Aviezri S. Fraenkel, M. R. Garey, David S. Johnson, T. Schaefer, and Yaacov Yesha. The complexity of checkers on an N * N board - preliminary report. In 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978, pages 55-64. IEEE Computer Society, 1978. URL: http://dx.doi.org/10.1109/SFCS.1978.36.
- Aviezri S. Fraenkel and David Lichtenstein. Computing a perfect strategy for n x n chess requires time exponential in n. J. Comb. Theory, Ser. A, 31(2):199-214, 1981. URL: http://dx.doi.org/10.1016/0097-3165(81)90016-9.
- M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics, 32(4):826-834, 1977. URL: http://dx.doi.org/DOI:10.1137/0132071.
-
Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., New York, NY, USA, 1979.
-
Michael Hoffmann. Motion planning amidst movable square blocks: Push-* is NP-hard. In Proceedings of the 12th Canadian Conference on Computational Geometry, pages 205-210, 2000.
- Jerry Holkins. Exposition. https://www.penny-arcade.com/news/post/2015/12/14/exposition, 2015.
- Ben Kuchera. Push Fight is the best board game you’ve never heard of. https://web.archive.org/web/20131211190946/http://penny-arcade.com/report/article/push-fight-is-the-best-board-game-youve-never-heard-of, 2012.
- Brett Picotte. Push Fight game. http://pushfightgame.com/, 2016. Accessed: 2017-06-22.
- J. M. Robson. N by N checkers is exptime complete. SIAM J. Comput., 13(2):252-267, 1984. URL: http://dx.doi.org/10.1137/0213018.
- L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time (preliminary report). In Proceedings of the 5th Annual ACM Symposium on Theory of Computing, pages 1-9, 1973. URL: https://dl.acm.org/citation.cfm?id=804029.