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