2012/02/03 by Urban Larsson, Larsson, Urban, Johan Wästlund +1
Computer Science · Mathematics · #68Q80 #91A46 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO) #cs.CC #cs.LO #math.CO #msc:68Q80 #msc:91A46
paper · pdf · doi:10.48550/arxiv.1202.0664
13 pages, 7 figures
arxiv created 2012/02/03 · arxiv updated 2012/02/06
We study so-called invariant games played with a fixed number d of heaps of matches. A game is described by a finite list M of integer vectors of length d specifying the legal moves. A move consists in changing the current game-state by adding one of the vectors in M, provided all elements of the resulting vector are nonnegative. For instance, in a two-heap game, the vector (1,-2) would mean adding one match to the first heap and removing two matches from the second heap. If (1,-2) ∈ M, such a move would be permitted provided there are at least two matches in the second heap. Two players take turns, and a player unable to make a move loses. We show that these games embrace computational universality, and that therefore a number of basic questions about them are algorithmically undecidable. In particular, we prove that there is no algorithm that takes two games M and M' (with the same number of heaps) as input, and determines whether or not they are equivalent in the sense that every starting-position which is a first player win in one of the games is a first player win in the other.