University of Illinois Urbana-Champaign

Reasoning and decisions in partially observable games

Richards, Mark

Content Files
Richards_Mark.pdf

Permalink

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

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
Date of Ingest
2012-09-18T21:14:27Z
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

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Siebel School of Computer Science