2015 | OriginalPaper | Buchkapitel
On Robot Games of Degree Two
verfasst von : Vesa Halava, Reino Niskanen, Igor Potapov
Erschienen in: Language and Automata Theory and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Robot Game is a two player vector addition game played in integer lattice
$$\mathbb {Z}^n$$
. 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$$
.