动态资源分配改进Ensemble Determinization MCTS

Dynamic Resource Allocation for Ensemble Determinization MCTS

精选理由

这篇论文给做游戏AI的同行提供了一个很实用的优化思路:不用固定分配计算资源,而是根据搜索情况动态调整,实测对三个桌游都有明显提升。

AI 摘要

该论文针对高不确定性对抗游戏(如Jaipur、Lost Cities、Splendor)中的蒙特卡洛树搜索(MCTS)进行改进,提出两种动态资源分配方法:Dynamic Number of Determinizations根据搜索表现动态调整当前使用的determinization树数量;Dynamic Simulation Allocation根据模拟间决策非均匀分配模拟预算到不同树中。在迭代和时间限制测试下,特定配置相比基线算法在统计上显著提升了强度(p<0.05)。实验基于三个流行桌面游戏,展示了方法在随机和隐藏信息环境中的有效性。

原文 · arXiv cs.AI

Dynamic Resource Allocation for Ensemble Determinization MCTS

Simulation-based algorithms are especially suited for high-uncertainty environments such as adversarial board games with significant elements of randomness and hidden information. In particular, several Monte Carlo Tree Search (MCTS) variants are commonly used in such domains. In this paper, we propose a series of enhancements for Ensemble Determinization MCTS, introducing two axes for dynamic resource allocation. First, Dynamic Number of Determinizations, increases or decreases the number of currently used determinization trees depending on the behavior of so-far search. Second, Dynamic Simulation Allocation, splits the simulation budget nonuniformly across the determinization trees, using simulation-to-simulation decisions to choose the tree with potentially the best knowledge gain. As benchmark domains, we used three popular tabletop games: Jaipur, Lost Cities, and Splendor. Testing our proposed enhancements in iteration- and time-based settings showed that particular configurations yield a statistically significant increase in the algorithm's strength.