Reasoning and decisions in partially observable games

Richards, Mark

Permalink

https://hdl.handle.net/2142/34384 Copy

Description

Title

Reasoning and decisions in partially observable games

Author(s)

Richards, Mark

Issue Date

2012-09-18T21:14:27Z

Director of Research (if dissertation) or Advisor (if thesis)

Amir, Eyal

Doctoral Committee Chair(s)

Amir, Eyal

Committee Member(s)

• Kale, Laxmikant V.
• LaValle, Steven M.
• Hinrichs, Timothy

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(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
• Battleship
• Racko
• 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.

Graduation Semester

2012-08

Permalink

http://hdl.handle.net/2142/34384

Copyright and License Information

Copyright 2012 Mark Richards

Owning Collections