Learning of winning strategies for terminal games with linear-size memory |
| |
Authors: | Thomas Böhme Frank Göring Zsolt Tuza Herwig Unger |
| |
Institution: | 1.Institut für Mathematik,Technische Universit?t Ilmenau,Ilmenau,Germany;2.Fakult?t für Mathematik,Technische Universit?t Chemnitz,Chemnitz,Germany;3.Computer and Automation Institute,Hungarian Academy of Sciences,Budapest,Hungary;4.Department of Computer Science,University of Pannonia,Veszprém,Hungary;5.Fachbereich Informatik,Universit?t Rostock,Rostock,Germany |
| |
Abstract: | We prove that if one or more players in a locally finite positional game have winning strategies, then they can find it by
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 a drawing- or winning strategy
exists, then it is learnt after no more than a linear number of plays lost (linear in the number of edges of the game graph).
Z. Tuza’s research has been supported in part by the grant OTKA T-049613. |
| |
Keywords: | Positional game Reinforcement learning Winning strategy Achieving a draw |
本文献已被 SpringerLink 等数据库收录! |
|