Theory of annihilation games
Aviezri S. Fraenkel, Yaacov Yesha · Bulletin of the American Mathematical Society · 1976
Put any number of stones on distinct vertices of R. Two players play alternately. Each player at his turn moves one stone from a vertex u to some v G F(ü). If v was occupied, both stones get removed (annihilation). The player making the last move wins. If there is no last move, the game is a tie. Such an annihilation game belongs to a large class of combinatorial games discussed in [1], [3], which are analyzable by the Generalized Sprague-Grundy Function (GSG-function) G: V(R)->ZU {«>} [i], [2], [3] with associated counter function c: V f (R)-+Z9 where V f (R) = {u G V(R): G(u) < <»} [2]. Here R is the game-graph of the game. Our main result is the construction of a complete strategy for the game, which is polynomial in n = I V(R)\\. Let C(R) be the game-graph of the annihilation game on R, also called the contrajunctive compound of R. If V(R) = {ux,..., un}, the vertices of V(C(R)) ( = game positions) constitute the set of all «-tuples û = (pt19..., an) over GF(2), where at = 1 if and only if a stone is on uv Also (w, v) C E(C(R)) if and only if there is a move from u to ü". Thus V(C(R)) is identical with the linear space GF(2) n under the operation ©, Z ' of Nim-sum (below: Generalized Nim-sum [1], [3]).