  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.
