Safe and Nested Endgame Solving for Imperfect-Information Games

Unlike perfect-information games, imperfect-information games cannot be decomposed into subgames that are solved independently. Thus more computationally intensive equilibrium-finding techniques are used, and abstraction---in which a smaller version of the game is generated and solved---is essential. Endgame solving is the process of computing a (presumably) better strategy for just an endgame than what can be computationally afforded for the full game. Endgame solving has many benefits, such as being able to 1) solve the endgame in a finer information abstraction than what is computationally feasible for the full game, and 2) incorporate into the endgame actions that an opponent took that were not included in the action abstraction used to solve the full game. We introduce an endgame solving technique that outperforms prior methods both in theory and practice. We also show how to adapt it, and past endgame-solving techniques, to respond to opponent actions that are outside the original action abstraction; this significantly outperforms the state-of-the-art approach, action translation. Finally, we show that endgame solving can be repeated as the game progresses down the tree, leading to significantly lower exploitability. All of the techniques are evaluated in terms of exploitability; to our knowledge, this is the first time that exploitability of endgame-solving techniques has been measured in large imperfect-information games.