General Game Playing (GGP) deals with the design of players that are able to play any discrete, deterministic, complete information games. For many games like chess, designers develop a player using a specially designed algorithm and tune all the features of the algorithm to play the game as good as possible. However, a general game player knows nothing about the game that is about to be played. When the game begins, game description is given to the players and they should analyze it and decide on the best way to play the game.
In this thesis, we focus on two-player constant-sum simultaneous move games in GGP and how this class of games can be handled. Rock-paper-scissors can be considered as a typical example of a simultaneous move game. We introduce the CFR algorithm to the GGP community for the first time and show its effectiveness in playing simultaneous move games. This is the first implementation of CFR outside the poker world. We also improve the UCT algorithm, which is the state of the art in GGP, to be more robust in simultaneous move games.
In addition, we analyze how UCT performs in simultaneous move games and argue that it does not converge to a Nash equilibrium. We also compare the usage of UCT and CFR in this class of games. Finally, we discuss about the importance of opponent modeling and how a model of the opponent can be exploited by using CFR.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:AEU.10048/880 |
| Date | 06 1900 |
| Creators | Shafiei Khadem, Mohammad |
| Contributors | Schaeffer, Jonathan (Computing Science), Sturtevant, Nathan (Computing Science), Kolfal, Bora (Accounting and Management Information Systems, School of Business), Szafron, Duane (Computing Science) |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 1939808 bytes, application/pdf |
| Relation | Comparing UCT versus CFR in Simultaneous Games, Mohammad Shafiei, Nathan Sturtevant and Jonathan Schaeffer, GIGA (IJCAI Workshop on General Game Playing) (peer reviewed), 2009. |
Page generated in 0.002 seconds