Playing Imperfect-Information Games in General Game Playing by Maintaining Information Set Samples

Download files
Access & Terms of Use
open access
Copyright: Schofield, Michael
Altmetric
Abstract
General Game Playing is a field of research where artificially intelligent systems (agents) are designed to understand the rules of any game and to play that game efficiently and effectively. The agent is expected to read and interpret a declaration of rules consistent with extensive form games, learn how to play, then play to win, all within a time budget. Games with imperfect-information have recently been added as a new challenge for existing General Game Playing systems. These imperfect-information games limit the information being received by the agent such that there are a number of indistinguishable game-play histories forming an information set. This research introduces techniques for playing imperfect-information games and reports on their limitations, efficiency, and effectiveness. Firstly, a bolt-on solution is presented that converts a perfect-information game player to an imperfect-information game player. HyperPlay maintains a collection of models of the true game as a foundation for reasoning, and move selection. The design choices for the technique are examined, its soundness and completeness are proved, experimental results are used to demonstrate the use of the technique in a variety of imperfect-information games, revealing its strengths, weaknesses, and its limitations. The Strategy Fusion Error is identified as an important limitation. Secondly, a nested player is presented using imperfect-information simulations to overcome the Strategy Fusion Error. The improved technique, HyperPlay-II, correctly values information based on the expected cost and reward and thus correctly values information-gathering moves. Again, experimental results are presented that demonstrate the use of the new technique revealing its strengths, weaknesses, and its limitations. Its poor scalability is identified as an important limitation. Finally, the efficiency and effectiveness of the techniques is examined through a series of experiments on games selected to expose the worst aspect of the techniques. Results show that: HyperPlay produces biased samples which are easily corrected, HyperPlay is far more efficient than random sampling, and HyperPlay-II correctly values information but scales as O(n^2).
Persistent link to this record
Link to Publisher Version
Link to Open Access Version
Additional Link
Author(s)
Schofield, Michael
Supervisor(s)
Pagnucco, Maurice
Thielscher, Michael
Creator(s)
Editor(s)
Translator(s)
Curator(s)
Designer(s)
Arranger(s)
Composer(s)
Recordist(s)
Conference Proceedings Editor(s)
Other Contributor(s)
Corporate/Industry Contributor(s)
Publication Year
2017
Resource Type
Thesis
Degree Type
PhD Doctorate
UNSW Faculty
Files
download public version.pdf 2 MB Adobe Portable Document Format
Related dataset(s)