Endgame Solving in Large Imperfect-Information Games

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.