Solving General Game Playing with Incomplete Information Problem using Iterative Tree Search and Language Learning

General Game Playing with Incomplete Information (GGP-II) is about developing a system capable of successfully playing incomplete information games without human intervention by just receiving their rules at runtime. Different algorithms (players) have been provided to play games in GGP-II. This research is concerned with three main limitations of algorithms in the literature: valuing-information, generating mixed strategy and cooperating in games which require implicit communication. In this thesis, I theoretically and experimentally show why past GGP-II players suffer from these problems and introduce four algorithms to overcome these problems and discuss the advantages and limitations of each algorithm. Firstly, I introduce the Iterative Tree Search (ITS) algorithm. ITS learns the best strategy by simulating different plays with itself. I show theoretically and experimentally how ITS correctly values information and models opponents by generating mixed strategies in different games. However, ITS fails to play large games and also the cooperative games which require implicit communication. Secondly, I present the Monte Carlo Iterative Tree Search (MCITS). This algorithm uses Monte Carlo Tree Search technique to focus the search on a more promising part of the game. I experimentally show the success of this algorithm on different games from the literature. MCITS fails to generate mixed strategies and to correctly play games which require implicit communication. Thirdly, I introduce a communication language learning technique called General Language (GL). GL is capable of generating an implicit communication language for cooperative players to share their information. The GL technique sees a communication language as an additional game rule. It can be used on top of any existing GGP-II player. This feature makes it a general algorithm. The main limitation of GL is its inability to solve large problems. Finally, I present the General Language Tree Search algorithm (GLTS). This algorithm extends the GL technique to be applicable to large games. It prioritises the communication languages according to their closeness to the most successful one. To validate my claim, I perform an experiment using GLTS by providing it with a Multi-Agent Path Finding with Destination Uncertainty problem. The GLTS algorithm successfully discovers the desired strategies by utilising the implicit communication among agents.

Grantor dc:publisher

UNSW, Sydney

Year dc:date

2020

Author dc:creator

• Chitizadeh, Armin

• GGP
• General Game Playing
• Incomplete Information
• Language Learning
• Multi-agent
• Monte Carlo
• GGP-II
• Implicit communication
• Multi-Agent Path Finding

Statement dc:rights

• open access
• CC BY-NC-ND 3.0
• free_to_read

Licence

• https://purl.org/coar/access_right/c_abf2
• https://creativecommons.org/licenses/by-nc-nd/3.0/au/

Language dc:language

EN

Identifier

https://doi.org/10.26190/unsworks/21886

OAI identifier oai:identifier

oai:unsworks.library.unsw.edu.au:1959.4/67169