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). |
Year | DOI | Venue |
---|---|---|
2009 | 10.1007/s00182-008-0142-5 | Int. J. Game Theory |
Keywords | Field | DocType |
reinforcement learning | Graph,Mathematical economics,Positional game,Mathematics,Reinforcement learning,Bounded function | Journal |
Volume | Issue | ISSN |
38 | 2 | 1432-1270 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Thomas Böhme | 1 | 172 | 21.73 |
Frank Göring | 2 | 53 | 9.00 |
Zsolt Tuza | 3 | 1889 | 262.52 |
Herwig Unger | 4 | 259 | 46.76 |