The State of Solving Large Incomplete-Information Games, and Application to Poker

By Tuomas Sandholm. 2010

128 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

In Game & Decision Theory

Citations in the corpus

OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “It has revolutionized Poker AI research [58, 60], leading to the largest variants of poker being solved and competitive polices that have beat top human professionals [10, 45, 13, 15].”
DeepStack: Expert-level artificial intelligence in heads-up no-limit poker (2017, neutral): “Abstraction and offline computation of complete strategies has been the dominant approach for almost 20 years (33, 40, 41).”
Evaluating state-space abstractions in extensive-form games (2013, background): “] have made remarkable progress [15] [11], the size of most real-world settings is beyond the capability of current solvers.”
Fictitious Self-Play in Extensive-Form Games (2015, background): “XFP and many other current methods of computational game theory (Sandholm, 2010) are full-width approaches and therefore require reasoning about every state in the game at each iteration.”
An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information (2014, background): “Another notable example is the algorithmic progress that has led to game-theoretic Poker agents that are competitive with highly skilled human opponents (e.g., see Zinkevich, Bowling, & Burch, 2007; Sandholm, 2010).”
Arena: A General Evaluation Platform and Building Toolkit for Multi-Agent Intelligence (2019, background): “Competitive multi-agent intelligence originally comes from computational game theory [9, 11, 60, 79].”
Opponent Modeling by Expectation–Maximization and Sequence Prediction in Simplified Poker (2017, unknown): “For more information we refer the reader to the review by Sandholm on the state of solving incomplete-information games [22], and the review by Rubin and Watson on algorithms, approaches , and agents in computer poker [23].”
Self-play Monte-Carlo tree search in computer poker (2014, background): “Computer poker provides a diversity of stochastic imperfect information games of different sizes and has proved to be a fruitful research domain for game theory and artificial intelligence (Sandholm 2010; Rubin and Watson 2011).”
Finding Optimal Abstract Strategies in Extensive-Form Games (2012, background): “This improvement, as larger and larger abstract games are solved, has appeared to drive much of the advancement in the Annual Computer Poker Competitions (Sandholm 2010).”
Computing Approximate Nash Equilibria and Robust Best-Responses Using Sampling (2011, unknown): “(2010) and Sandholm (2010) is to use the Excessive Gap Technique applied to a relaxed optimization problem from which the linear program described above is derived.”