A4 Refereed article in a conference publication
On Robot Games of Degree Two
Authors: Vesa Halava, Reino Niskanen, Igor Potapov
Conference name: International Conference on Language and Automata Theory and Applications
Publisher: Springer, Cham
Publication year: 2015
Book title : Language and Automata Theory and Applications - 9th International Conference, {LATA} 2015, Nice, France, March 2-6, 2015, Proceedings
Series title: Lecture Notes in Computer Science
Volume: 8977
First page : 224
Last page: 236
ISBN: 978-952-12-3014-1
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-319-15579-1_17
Web address : 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.