Reduced Space and Faster Convergence in Imperfect-Information Games via Regret-Based Pruning
This work addresses efficiency issues for researchers and practitioners in game theory and AI, though it is incremental as it builds on existing Regret-Based Pruning methods.
The paper tackled the problem of high space requirements and slow convergence in solving zero-sum imperfect-information games by introducing Total Regret-Based Pruning, which reduces space usage and speeds up Counterfactual Regret Minimization, achieving an order of magnitude reduction in space with increasing benefits for larger games.
Counterfactual Regret Minimization (CFR) is the most popular iterative algorithm for solving zero-sum imperfect-information games. Regret-Based Pruning (RBP) is an improvement that allows poorly-performing actions to be temporarily pruned, thus speeding up CFR. We introduce Total RBP, a new form of RBP that reduces the space requirements of CFR as actions are pruned. We prove that in zero-sum games it asymptotically prunes any action that is not part of a best response to some Nash equilibrium. This leads to provably faster convergence and lower space requirements. Experiments show that Total RBP results in an order of magnitude reduction in space, and the reduction factor increases with game size.