改进蒙特卡洛树搜索，用证明数更高效地找到必胜路径。
Generalized Proof-Number Monte-Carlo Tree Search
- 为每方维护证明数，简化代码并支持多玩家游戏
- 新策略使搜索更快，11个棋类中8个提升至80%成功率
- 可同时利用分数上下界，适用于复杂评分游戏
本文提出广义证明数蒙特卡洛树搜索：一种将证明数搜索（PNS）与蒙特卡洛树搜索（MCTS）结合的新方法。通过三个核心改进：首先，为每方追踪证明数，无需反证数，降低实现复杂度，并拓展至多玩家游戏；其次，提出多种基于证明数的选点策略，实验显示简单高效；第三，与分数有界MCTS融合，能同时利用分数上下界，而不仅限于胜负判断。在11个棋类游戏中测试，8个达到约80%的性能提升，显著优于现有方法。
原文摘要 · Abstract (English)
This paper presents Generalized Proof-Number Monte-Carlo Tree Search: a generalization of recently proposed combinations of Proof-Number Search (PNS) with Monte-Carlo Tree Search (MCTS), which use (dis)proof numbers to bias UCB1-based Selection strategies towards parts of the search that are expected to be easily (dis)proven. We propose three core modifications of prior combinations of PNS with MCTS. First, we track proof numbers per player. This reduces code complexity in the sense that we no longer need disproof numbers, and generalizes the technique to be applicable to games with more than two players. Second, we propose and extensively evaluate different methods of using proof numbers to bias the selection strategy, achieving strong performance with strategies that are simpler to implement and compute. Third, we merge our technique with Score Bounded MCTS, enabling the algorithm to prove and leverage upper and lower bounds on scores - as opposed to only proving wins or not-wins. Experiments demonstrate substantial performance increases, reaching the range of 80% for 8 out of the 11 tested board games.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。