证明了两种游戏搜索算法在改进后能始终找到必胜策略。
Completeness of Unbounded Best-First Minimax and Descent Minimax
- 推广并改进了无界最佳优先极小极大与下降极小极大算法
- 实验表明改进后算法显著提升必胜表现
- 适合研究博弈搜索与强化学习的学者参考
本文研究双人完美信息博弈中的搜索算法，旨在确定最优策略，理想情况下为必胜策略。然而，文献中一些算法即使在无限搜索时间下也无法保证找到必胜策略，例如无界最佳优先极小极大和下降极小极大算法，这两者是当前无知识强化学习的核心算法。随后引入了‘完成技术’对其进行改进，但该技术是否足以确保算法总能确定必胜策略仍是一个开放问题。为此，本文推广了使用完成技术的两类算法，并证明该类任意算法均能计算出最优策略。最后通过实验验证，完成技术显著提升了算法的必胜性能。
原文摘要 · Abstract (English)
In this article, we focus on search algorithms for two-player perfect information games, whose objective is to determine the best possible strategy, and ideally a winning strategy. Unfortunately, some search algorithms for games in the literature are not able to always determine a winning strategy, even with an infinite search time. This is the case, for example, of the following algorithms: Unbounded Best-First Minimax and Descent Minimax, which are core algorithms in state-of-the-art knowledge-free reinforcement learning. They were then improved with the so-called completion technique. However, whether this technique sufficiently improves these algorithms to allow them to always determine a winning strategy remained an open question until now. To answer this question, we generalize the two algorithms (their versions using the completion technique), and we show that any algorithm of this class of algorithms computes the best strategy. Finally, we experimentally show that the completion technique improves winning performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。