Return to search

Simultaneous Move Games in General Game Playing

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.

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:AEU.10048/880
Date06 1900
CreatorsShafiei Khadem, Mohammad
ContributorsSchaeffer, Jonathan (Computing Science), Sturtevant, Nathan (Computing Science), Kolfal, Bora (Accounting and Management Information Systems, School of Business), Szafron, Duane (Computing Science)
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
LanguageEnglish
Detected LanguageEnglish
TypeThesis
Format1939808 bytes, application/pdf
RelationComparing 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