GameShrink

Lossless abstraction of imperfect information games. Finding an equilibrium of an extensive form game of imperfect information is a fundamental problem in computational game theory, but current techniques do not scale to large games. To address this, we introduce the ordered game isomorphism and the related ordered game isomorphic abstraction transformation. For a multi-player sequential game of imperfect information with observable actions and an ordered signal space, we prove that any Nash equilibrium in an abstracted smaller game, obtained by one or more applications of the transformation, can be easily converted into a Nash equilibrium in the original game. We present an algorithm, GameShrink, for abstracting the game using our isomorphism exhaustively. Its complexity is o ˜(n 2 ), where n is the number of nodes in a structure we call the signal tree. It is no larger than the game tree, and on nontrivial games it is drastically smaller, so GameShrink has time and space complexity sublinear in the size of the game tree. Using GameShrink, we find an equilibrium to a poker game with 3.1 billion nodes – over four orders of magnitude more than in the largest poker game solved previously. To address even larger games, we introduce approximation methods that do not preserve equilibrium, but nevertheless yield (ex post) provably close-to-optimal strategies.


References in zbMATH (referenced in 11 articles , 1 standard article )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Čermák, Jiří; Lisý, Viliam; Bošanský, Branislav: Automated construction of bounded-loss imperfect-recall abstractions in extensive-form games (2020)
  2. Kroer, Christian; Waugh, Kevin; Kılınç-Karzan, Fatma; Sandholm, Tuomas: Faster algorithms for extensive-form game solving via improved smoothing functions (2020)
  3. Avni, Guy; Guha, Shibashis; Kupferman, Orna: An abstraction-refinement methodology for reasoning about network games (2018)
  4. Čermák, Jiří; Bošanský, Branislav; Horák, Karel; Lisý, Viliam; Pěchouček, Michal: Approximating maxmin strategies in imperfect recall games using A-loss recall property (2018)
  5. Basilico, Nicola; Gatti, Nicola; Amigoni, Francesco: Patrolling security games: definition and algorithms for solving large instances with single patroller and single intruder (2012)
  6. Rubin, Jonathan; Watson, Ian: Computer poker: a review (2011) ioport
  7. Yu, Xiaohan; Xu, Zeshui; Chen, Qi: A game model based on multi-attribute aggregation (2011)
  8. Hoda, Samid; Gilpin, Andrew; Peña, Javier; Sandholm, Tuomas: Smoothing techniques for computing Nash equilibria of sequential games (2010)
  9. Southey, Finnegan; Hoehn, Bret; Holte, Robert C.: Effective short-term opponent exploitation in simplified poker (2009)
  10. Conitzer, Vincent; Sandholm, Tuomas: New complexity results about Nash equilibria (2008)
  11. Gilpin, Andrew; Sandholm, Tuomas: Lossless abstraction of imperfect information games. (2007)