GameShrink
swMATH ID:  12511 
Software Authors:  Gilpin, Andrew; Sandholm, Tuomas 
Description:  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 multiplayer 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 closetooptimal strategies. 
Homepage:  http://www.cs.cmu.edu/~sandholm/extensive.jacm07.pdf 
Related Software:  DeepStack; Libratus; NetworkX; Radish; AMPL; LPbook 
Referenced in:  10 Publications 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

Lossless abstraction of imperfect information games. Zbl 1314.91025 Gilpin, Andrew; Sandholm, Tuomas 
2007

all
top 5
Referenced by 24 Authors
all
top 5
Referenced in 9 Serials
Referenced in 4 Fields
10  Game theory, economics, finance, and other social and behavioral sciences (91XX) 
3  Computer science (68XX) 
3  Operations research, mathematical programming (90XX) 
1  Combinatorics (05XX) 