Not Logged In

Probabilistic State Translation in Extensive Games with Large Action Sets

Full Text: IJCAI09-055.pdf PDF

Equilibrium or near-equilibrium solutions to very large extensive form games are often computed by using abstractions to reduce the game size. A common abstraction technique for games with a large number of available actions is to restrict the number of legal actions in every state. This method has been used to discover equilibrium solutions for the game of no-limit heads-up Texas Hold'em. When using a solution to an abstracted game to play one side in the un-abstracted (real) game, the real opponent actions may not correspond to actions in the abstracted game. The most popular method for handling this situation is to translate opponent actions in the real game to the closest legal actions in the abstracted game. We show that this approach can result in a very exploitable player and propose an alternative solution. We use probabilistic mapping to translate a real action into a probability distribution over actions, whose weights are determined by a similarity metric. We show that this approach significantly reduces the exploitability when using an abstract solution in the real game.

Citation

D. Schnizlein, M. Bowling, D. Szafron. "Probabilistic State Translation in Extensive Games with Large Action Sets". International Joint Conference on Artificial Intelligence (IJCAI), pp 278-284, July 2009.

Keywords: machine learning
Category: In Conference

BibTeX

@incollection{Schnizlein+al:IJCAI09,
  author = {David Schnizlein and Michael Bowling and Duane Szafron},
  title = {Probabilistic State Translation in Extensive Games with Large Action
    Sets},
  Pages = {278-284},
  booktitle = {International Joint Conference on Artificial Intelligence
    (IJCAI)},
  year = 2009,
}

Last Updated: October 14, 2009
Submitted by David Schnizlein

University of Alberta Logo AICML Logo