Wissen, was gut ist. Studieren in Chemnitz.
Böhme, Thomas; Göring, Frank; Tuza, Zsolt; Unger, Herwig : Learning of Winning Strategies for Terminal Games with Linear-Size Memory

Böhme, Thomas ; Göring, Frank ; Tuza, Zsolt ; Unger, Herwig : Learning of Winning Strategies for Terminal Games with Linear-Size Memory

Author(s):
Böhme, Thomas
Göring, Frank
Tuza, Zsolt
Unger, Herwig
Title:
Learning of Winning Strategies for Terminal Games with Linear-Size Memory
Electronic source:
application/pdf
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 25, 2006
Mathematics Subject Classification:
91A26 [ Rationality, learning ]
Abstract:
We prove that if one or more players in a locally finite positional game have winning strategies, then they can find it for themselves, not losing more than a bounded number of plays and not using more than a linear-size memory, independently of the strategies applied by the other players. We design two algorithms for learning how to win. One of them can also be modified to determine a strategy that achieves a draw, provided that no winning strategy exists for the player in question but with properly chosen moves a draw can be ensured from the starting position. If the drawing- or winning strategy exists, then it is learnt after no more than a linear number of plays lost.
Keywords:
strategy learning, terminal game, draw
Language:
English
Publication time:
10 / 2007