Endgame Solving in Large Imperfect-Information Games
By Sam Ganzfried, Tuomas Sandholm. 2015
45 citations recorded by the source corpus.
The leading approach for computing strong game-theoretic strategies in large imperfect-information games is to first solve an abstracted version of the game offline, then perform a table lookup during game play. We consider a modification to this approach where we solve the portion of the game that we have actually reached in real time to a greater degree of accuracy than in the initial computation. We call this approach endgame solving. Theoretically, we show that endgame solving can produce highly exploitable strategies in some games; however, we show that it can guarantee a low exploitability in certain games where the opponent is given sufficient exploitative power within the endgame. Furthermore, despite the lack of a general worst-case guarantee, we describe many benefits of endgame solving. We present an efficient algorithm for performing endgame solving in large imperfect-information games, and present a new variance-reduction technique for evaluating the performance of an agent that uses endgame solving. Experiments on no-limit Texas Hold'em show that our algorithm leads to significantly stronger performance against the strongest agents from the 2013 AAAI Annual Computer Poker Competition.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Noam Brown
- Johannes Heinrich
- David Silver
- Brandon Amos
- Tuomas Sandholm
- Kaiqing Zhang
- Adam Lerer
- Marc Lanctot
Citations in the corpus
- Smooth UCT Search in Computer Poker (2015, methodology): “Furthermore, solving a subgame of an imperfect-information game, by using online search, can produce exploitable strategies [Burch et al., 2014; Ganzfried and Sandholm, 2015].”
- Safe and Nested Endgame Solving for Imperfect-Information Games (2017, background): “We first review the most intuitive form of endgame solving, which we refer to as unsafe endgame solving (Billings et al. 2003; Gilpin and Sandholm 2006; 2007; Ganzfried and Sandholm 2015).”
- Libratus: The Superhuman AI for No-Limit Poker (2017, methodology): “This leads to better strategies [Brown and Sandholm, 2017b] than prior subgame-solving techniques [Ganzfried and Sandholm, 2015; Burch et al., 2014; Jackson, 2014; Moravcik et al., 2016].”
- Depth-Limited Solving for Imperfect-Information Games (2018, background): “In unsafe solving [13], each player maintains a belief distribution over states.”