ERA

Download the full-sized PDF of Simultaneous Move Games in General Game PlayingDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3T323

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Graduate Studies and Research, Faculty of

Collections

This file is in the following collections:

Theses and Dissertations

Simultaneous Move Games in General Game Playing Open Access

Descriptions

Other title
Subject/Keyword
General Game Playing
Simultaneous Move Games
Nash Equilibrium
CFR (CounterFactual Regret)
UCT (UCB applied to Trees)
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Shafiei Khadem, Mohammad
Supervisor and department
Schaeffer, Jonathan (Computing Science)
Sturtevant, Nathan (Computing Science)
Examining committee member and department
Szafron, Duane (Computing Science)
Kolfal, Bora (Accounting and Management Information Systems, School of Business)
Department
Department of Computing Science
Specialization

Date accepted
2010-01-04T19:27:54Z
Graduation date
2010-06
Degree
Master of Science
Degree level
Master's
Abstract
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.
Language
English
DOI
doi:10.7939/R3T323
Rights
License granted by Mohammad Shafiei Khadem (shafieik@ualberta.ca) on 2010-01-04T19:17:39Z (GMT): Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of the above terms. The author reserves all other publication and other rights in association with the copyright in the thesis, and except as herein provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication

File Details

Date Uploaded
Date Modified
2014-04-24T23:47:52.262+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1939808
Last modified: 2015:10:12 19:13:51-06:00
Filename: thesis.pdf
Original checksum: 90236d7169557ec735dd2f182db47555
Well formed: true
Valid: true
File title: thesis.dvi
Page count: 77
Activity of users you follow
User Activity Date