动态分配资源提升博弈搜索效率
Dynamic Resource Allocation for Ensemble Determinization MCTS
- 根据搜索过程动态调整确定化树数量
- 非均匀分配模拟次数，优先投入潜力大分支
- 在三款桌游中显著增强算法表现
基于模拟的算法特别适合高不确定性环境，如包含随机性和隐藏信息的对抗性棋类游戏。本文针对集成确定化蒙特卡洛树搜索（Ensemble Determinization MCTS）提出一系列改进，引入两个动态资源分配维度：一是动态确定化数量，根据已有搜索行为增减当前使用的确定化树数量；二是动态模拟分配，将模拟预算非均匀分配给各确定化树，利用模拟间的决策选择潜在知识收益最高的树。在三个流行桌面游戏——Jaipur、Lost Cities 和 Splendor 上进行测试，迭代与时间两种设置下，特定配置均显示出算法强度的统计显著提升。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。