Scalable sub-game solving for imperfect-information games

摘要

Counterfactual regret minimization (CFR) is a popular and effective method for solving a game with imperfect information. The effect of CFR is limited by the size of the game state space. With the increase in the number of game participants, the game state space will increase rapidly. Although the vanilla CFR is suitable for two-player imperfect-information games, it does not work well in imperfect-information games with three or more players. In this paper, we design a framework for imperfect-information games, which can not only deal with two-player imperfect-information games but also can efficiently solve three-player imperfect-information games. Compared with traditional solving methods, in this framework we propose real-time hand abstraction (RTHA), which can reduce the error caused by the abstraction. We also propose a warm-start online solution of sub-game (WSOS-SG) method, which can improve the accuracy of the action estimation and solve the sub-game in real time. Experimental results show that the agent based on our method achieve better performances than traditional methods. The agent based on our method took part in the 2018 AAAI-ACPC poker competition and won third place in heads-up no-limit Texas hold'em. (C) 2021 Elsevier B.V. All rights reserved.