A Regularization-Based Approach to Public Belief State Search for Adversarial Games

The public belief state (PBS), which is the posterior over game histories conditioned on public information, is a fundamental abstraction for designing game-theoretically sound search algorithms for imperfect-information games. Existing sound PBS search techniques for adversarial games fall into two categories: gadget-game-based algorithms (including Libratus, DeepStack, Pluribus, Supremus, and Student of Games) and ReBeL-based algorithms. Both these categories possess disadvantages, including a reliance on discontinuous functions, an inability to re-solve subgames, and an implicit representation of policies. In this work, we propose Gravel, a new approach for PBS search---different from these previous two categories---that achieves game-theoretic soundness via regularization. Unlike the aforementioned approaches, Gravel relies on smooth functions, can initiate search at any point in the game, and outputs explicit policies directly. We empirically demonstrate the advantages of Gravel for no-limit Texas hold'em, where we show that it outperforms ReBeL both in head-to-head competitions against Slumbot and in endgame solving. We include our codebase in the submission, making Gravel the first open-source high-performance no-limit Texas hold'em AI.