On Robot Games of Degree Two
: Vesa Halava, Reino Niskanen, Igor Potapov
: International Conference on Language and Automata Theory and Applications
Publisher: Springer, Cham
: 2015
: Language and Automata Theory and Applications - 9th International Conference, {LATA} 2015, Nice, France, March 2-6, 2015, Proceedings
: Lecture Notes in Computer Science
: 8977
: 224
: 236
: 978-952-12-3014-1
: 0302-9743
DOI: https://doi.org/10.1007/978-3-319-15579-1_17
: http://dx.doi.org/10.1007/978-3-319-15579-1_17
Robot Game is a two player vector addition game played
in integer lattice Zn. In a degree k case both players have k vectors
and in each turn the vector chosen by a player is added to the current
configuration vector of the game. One of the players, called Attacker,
tries to play the game from the initial configuration to the origin while
the other player, Defender, tries to avoid origin. The decision problem is
to decide whether or not Attacker has a winning strategy. We prove that
the problem is decidable in polynomial time for the degree two games in
any dimension n.