Potential-Aware Imperfect-Recall Abstraction with Earth Mover's Distance in Imperfect-Information Games
Potential-Aware Imperfect-Recall Abstraction with Earth Mover's Distance in Imperfect-Information Games
复制标题
DOI：
10.1609/aaai.v28i1.8816
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Sam Ganzfried;T. Sandholm
中科院分区：
文献类型：
--
作者：
Sam Ganzfried;T. Sandholm
我们希望解决的游戏规模与最佳算法可解决的最大实例规模之间往往存在很大差距;例如，扑克的一个流行变体在其游戏树中有大约10 ^{165}$个节点，而目前最佳的近似均衡查找算法可扩展到大约10 ^{12}$个节点的游戏。为了近似这些博弈中的均衡策略，主要的方法是创建一个足够小的完整博弈的策略近似，称为抽象，并解决较小的博弈。领先的抽象算法为不完全信息游戏生成的抽象，有不完美的召回和分布意识，使用$k$-means与地球移动的距离度量聚类相似的状态在一起。分布感知的抽象在给定的回合中将状态分组在一起，如果它们在未来强度上的完全分布是相似的（例如，与之相对的是，仅仅是它们的强度的期望）。领先的算法考虑在游戏的最后一轮的未来强度的分布。然而，考虑未来所有回合（而不仅仅是最后一轮）中强度分布的轨迹可能会受益。考虑所有未来轮次的抽象算法称为潜在感知。我们提出了第一个算法计算潜在的意识到的回忆抽象使用推土机的距离。无限制德州扑克的实验表明，我们的算法提高了性能比以前最好的方法。
There is often a large disparity between the size of a game we wish to solve and the size of the largest instances solvable by the best algorithms; for example, a popular variant of poker has about $10^{165}$ nodes in its game tree, while the currently best approximate equilibrium-finding algorithms scale to games with around $10^{12}$ nodes. In order to approximate equilibrium strategies in these games, the leading approach is to create a sufficiently small strategic approximation of the full game, called an abstraction, and to solve that smaller game instead. The leading abstraction algorithm for imperfect-information games generates abstractions that have imperfect recall and are distribution aware, using $k$-means with the earth mover's distance metric to cluster similar states together. A distribution-aware abstraction groups states together at a given round if their full distributions over future strength are similar (as opposed to, for example, just the expectation of their strength). The leading algorithm considers distributions over future strength at the final round of the game. However, one might benefit by considering the trajectory of distributions over strength in all future rounds, not just the final round. An abstraction algorithm that takes all future rounds into account is called potential aware. We present the first algorithm for computing potential-aware imperfect-recall abstractions using earth mover's distance. Experiments on no-limit Texas Hold'em show that our algorithm improves performance over the previously best approach.