Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning
Reduced Space and Faster Convergence in Imperfect-Information Games via Pruning
复制标题
DOI：
--
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
Noam Brown;T. Sandholm
中科院分区：
文献类型：
--
作者：
Noam Brown;T. Sandholm
反事实遗憾最小化（CFR）等迭代算法是解决大型零和不完美信息游戏的最流行方法。在本文中，我们介绍了最佳响应修剪（BRP），这是对CFR等迭代算法的改进，允许暂时修剪表现不佳的动作。我们证明，在零和游戏中使用CFR时，添加BRP将渐近地修剪任何对某些NASH平衡最佳响应的动作。事实证明，这导致了更快的收敛性和较低的空间要求。实验表明，BRP导致空间减少7倍，而还原因子随游戏尺寸而增加。
Iterative algorithms such as Counterfactual Regret Minimization (CFR) are the most popular way to solve large zero-sum imperfect-information games. In this paper we introduce Best-Response Pruning (BRP), an improvement to iterative algorithms such as CFR that allows poorly-performing actions to be temporarily pruned. We prove that when using CFR in zero-sum games, adding BRP will asymptotically prune 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 BRP results in a factor of 7 reduction in space, and the reduction factor increases with game size.