Files in this item



application/pdfRichards_Mark.pdf (702kB)
(no description provided)PDF


Title:Reasoning and decisions in partially observable games
Author(s):Richards, Mark
Director of Research:Amir, Eyal
Doctoral Committee Chair(s):Amir, Eyal
Doctoral Committee Member(s):Kale, Laxmikant V.; LaValle, Steven M.; Hinrichs, Timothy
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):General Game Playing
Partially Observable Games
Imperfect Information Games
Information Sets
Belief States
Opponent Modeling
Nash Equilibrium
Extensive Form Games
Game Trees
Monte Carlo Tree Search
Game of Pure Strategy
Game Tree Search
Abstract:The extensive form game is a formalism used to model environments where agents make sequences of decisions, possibly in the face of uncertainty about the state of the world and the decisions made by other agents. Such games can be expressed in the form of a tree. Game-theoretic solutions to two-player extensive form games are intractable in many cases. This thesis presents a complete system for modeling and reasoning about such games in a general way under practical computational restrictions. We address three key challenges related to reasoning about extensive form games: (1) compact representation of the game rules, (2) reasoning about an agent's own knowledge and the knowledge of its opponents; and (3) making decisions in games where it is not possible to generate the full game tree. The utility of any language designed to express games depends on its expressive power, the ability of game designers to naturally and compactly describe game rules, and the reasoning and inferential tools that the language constructs enable. We present a description language that captures the same semantics as extensive form games but allows their expression in more natural and compact constructs. This logical language is an extension to the Planning Domain Description Language (PDDL), which is commonly used for AI planning problems. We demonstrate the utility of our language by showing that it can be used to express the rules of several popular games and that the language constructs can be used by our game-playing system to make effective decisions. A second key challenge for our game-playing system is to model the uncertainty related to opponents' decisions and chance events. We outline a decision-making framework based on the notion of information set generation. Information sets are similar to belief states. Whereas a belief state encodes a probability distribution over possible current worlds, an information set represents the set of all possible game histories that are consistent with a player's observations. By simulating these possible game histories, an agent can reproduce possible past and future decision points for its opponents, including a re-creation of the knowledge state that the opponent would have in making those decisions. We frame information set generation and sampling as a constraint satisfaction problem and show significant gains in efficiency over the existing method on several games. We also show that this operation scales efficiently to massively parallel machines. We achieve speedups of over 500 times in some cases, surpassing current limits of parallelism for fully observable games. The third challenge that we address is making decisions in an environment where observation, deliberation, and action are interleaved. Nash equilibrium solutions are a function of the entire game tree and are predicated on the assumption that agents are computationally unbounded. In practice, agents must make decisions about what to do at the present moment, given a sequence of observations received so far and only limited exploration of the game tree. We present three different decision-making algorithms and show that their optimality depends on whether the game has a dominant, pure, or mixed strategy equilibrium. We describe the circumstances under which an agent can be exploited by an omniscient opponent when using one of these strategies. As a case study, we implement our opponent modeling strategy for the popular board game Scrabble. Our reasoning agent outperforms the de facto world champion system.
Issue Date:2012-09-18
Rights Information:Copyright 2012 Mark Richards
Date Available in IDEALS:2012-09-18
Date Deposited:2012-08

This item appears in the following Collection(s)

Item Statistics