Finding Optimal Abstract Strategies in Extensive-Form Games

Authors

  • Michael Johanson University of Alberta
  • Nolan Bard University of Alberta
  • Neil Burch University of Alberta
  • Michael Bowling University of Alberta

DOI:

https://doi.org/10.1609/aaai.v26i1.8269

Keywords:

Game Theory, Extensive Form Games

Abstract

Extensive-form games are a powerful model for representing interactions between agents. Nash equilibrium strategies are a common solution concept for extensive-form games and, in two-player zero-sum games, there are efficient algorithms for calculating such strategies. In large games, this computation may require too much memory and time to be tractable. A standard approach in such cases is to apply a lossy state-space abstraction technique to produce a smaller abstract game that can be tractably solved, while hoping that the resulting abstract game equilibrium is close to an equilibrium strategy in the unabstracted game. Recent work has shown that this assumption is unreliable, and an arbitrary Nash equilibrium in the abstract game is unlikely to be even near the least suboptimal strategy that can be represented in that space. In this work, we present for the first time an algorithm which efficiently finds optimal abstract strategies --- strategies with minimal exploitability in the unabstracted game. We use this technique to find the least exploitable strategy ever reported for two-player limit Texas hold'em.

Downloads

Published

2021-09-20

How to Cite

Johanson, M., Bard, N., Burch, N., & Bowling, M. (2021). Finding Optimal Abstract Strategies in Extensive-Form Games. Proceedings of the AAAI Conference on Artificial Intelligence, 26(1), 1371-1379. https://doi.org/10.1609/aaai.v26i1.8269

Issue

Section

AAAI Technical Track: Multiagent Systems