Theory of annihilation games—I

Place tokens on distinct vertices of an arbitrary finite digraph with n vertices which may contain cycles or loops. Each of two players alternately selects a token and moves it from its present position u to a neighboring vertex v along a directed edge which may be a loop. If v is occupied, and u ≠ v, both tokens get annihilated and phase out of the game. The player first unable to move is the loser, the other the winner. If there is no last move, the outcome is declared a draw. An O(n⁶) algorithm for computing the previous-player-winning, next-player-winning and draw positions of the game is given. Furthermore, an algorithm is given for computing a best strategy in O(n⁶) steps and winning—starting from a next-player-winning position—in O(n⁵) moves.