Timezone: »

 
Poster
Safe and Nested Subgame Solving for Imperfect-Information Games
Noam Brown · Tuomas Sandholm

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #226
in Posters Tue »

In imperfect-information games, the optimal strategy in a subgame may depend on the strategy in other, unreached subgames. Thus a subgame cannot be solved in isolation and must instead consider the strategy for the entire game as a whole, unlike perfect-information games. Nevertheless, it is possible to first approximate a solution for the whole game and then improve it by solving individual subgames. This is referred to as subgame solving. We introduce subgame-solving techniques that outperform prior methods both in theory and practice. We also show how to adapt them, and past subgame-solving techniques, to respond to opponent actions that are outside the original action abstraction; this significantly outperforms the prior state-of-the-art approach, action translation. Finally, we show that subgame solving can be repeated as the game progresses down the game tree, leading to far lower exploitability. These techniques were a key component of Libratus, the first AI to defeat top humans in heads-up no-limit Texas hold'em poker.

Keywords: Game Theory and Computational Economics · Game Playing

Author Information

Noam Brown (Carnegie Mellon University)
Tuomas Sandholm (Carnegie Mellon University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors