Automated Action Abstraction of Imperfect Information Extensive-Form Games

Authors

  • John Hawkin University of Alberta
  • Robert Holte University of Alberta
  • Duane Szafron University of Alberta

Abstract

Multi-agent decision problems can often be formulated as extensive-form games. We focus on imperfect information extensive-form games in which one or more actions at many decision points have an associated continuous or many-valued parameter. A stock trading agent, in addition to deciding whether to buy or not, must decide how much to buy. In no-limit poker, in addition to selecting a probability for each action, the agent must decide how much to bet for each betting action. Selecting values for these parameters makes these games extremely large. Two-player no-limit Texas Hold'em poker with stacks of 500 big blinds has approximately 1071 states, which is more than 1050 times more states than two-player limit Texas Hold'em. The main contribution of this paper is a technique that abstracts a game's action space by selecting one, or a small number, of the many values for each parameter. We show that strategies computed using this new algorithm for no-limit Leduc poker exhibit significant utility gains over epsilon-Nash equilibrium strategies computed with standard, hand-crafted parameter value abstractions.

Downloads

Published

2011-08-04

How to Cite

Hawkin, J., Holte, R., & Szafron, D. (2011). Automated Action Abstraction of Imperfect Information Extensive-Form Games. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 681-687. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7880

Issue

Section

AAAI Technical Track: Multiagent Systems