2026-07-20T05:35:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8802 2024-03-06T10:42:41Z ddc:004 open_access

Computational Complexity of Generalized Push Fight Bosboom, Jeffrey Demaine, Erik D. Rudoy, Mikhail board games hardness mate-in-one 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeffrey Bosboom and Erik D. Demaine and Mikhail Rudoy 2018 Is Part Of LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2018.11 urn:nbn:de:0030-drops-88029 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.11 eng https://creativecommons.org/licenses/by/3.0/legalcode