Automated Abstraction of Large Action Spaces in Imperfect Information Extensive-Form Games

Abstract

An agent in an adversarial, imperfect information environment must sometimes decide whether or not to take an action and, if they take the action, must choose a parameter value associated with that action. Examples include choosing to buy or sell some amount of resources or choosing whether or not to move combined with a distance for that movement. This problem can be expanded to allow for mixing between multiple actions each with distinct associated parameter values and can be expressed as an imperfect information extensive form game. This dissertation describes a new automated method of abstracting the action space of such decision problems. It presents new algorithms for implementing the method, provides some theory about how the method relates to Nash equilibria in a small poker game and assesses the method using several poker games. One of these algorithms was used in the creation of an agent that won one of the divisions of the 2012 Annual Computer Poker Competition. An improvement upon this algorithm produced an action abstraction of two-player no-limit Texas hold'em poker that out-performs a state-of-the-art action abstraction while requiring less than 40% of the memory. The resulting agent had the best overall results in a round robin tournament of six top two-player no-limit Texas hold'em agents.