一种无需深度强化学习的高效博弈搜索算法，适用于计算资源有限场景。
Monte Carlo Permutation Search
- 基于全路径回放统计优化探索，避免使用有偏超参数
- 在五类游戏中表现普遍优于GRAVE算法，提升明显
- 适合资源受限的通用游戏玩法系统，如嵌入式博弈引擎
我们提出蒙特卡洛排列搜索（MCPS），一种通用的蒙特卡洛树搜索算法，改进了GRAVE算法。当深度强化学习不可行或赛前计算资源有限时（如通用游戏对弈），该方法尤为适用。MCPS的核心思想是将从根节点到当前节点路径上所有动作的全部回放统计纳入节点探索项中。我们在多种游戏上进行了测试：六角棋（Hex）、围棋（Go）、AtariGo、NoGo以及一款战棋游戏（Wargame）。实验结果表明，MCPS几乎在所有情况下均优于GRAVE算法。此外，我们还提供了用于加权三种统计来源的公式数学推导，新公式不再依赖GRAVE中的偏差超参数，实现更优性能。
原文摘要 · Abstract (English)
We propose Monte Carlo Permutation Search (MCPS), a general-purpose Monte Carlo Tree Search (MCTS) algorithm that improves upon the GRAVE algorithm. MCPS is relevant when deep reinforcement learning is not an option or when the computing power available before play is not substantial, such as in General Game Playing. The principle of MCPS is to include in the exploration term of a node the statistics on all the playouts that contain all the moves on the path from the root to the node. We test MCPS on a variety of games: Hex, Go, AtariGo, NoGo and a Wargame. MCPS almost always outperforms GRAVE. We also provide a mathematical derivation of the formulas used for weighting the three sources of statistics. These formulas are an improvement on the GRAVE formula since they no longer use the bias hyperparameter of GRAVE.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。