In this article, we prove the completeness of the following game search algorithms: unbounded best-first minimax with completion and descent with completion, i.e. we show that, with enough time, they find the best game strategy. We then generalize these two algorithms in the context of perfect information multiplayer games. We show that these generalizations are also complete: they find one of the equilibrium points.
翻译：在文章中,我们证明了下列游戏搜索算法的完整性:无限制的首个最小型算法,完成和下降,完成,也就是说,我们证明,只要有足够的时间,他们就能找到最佳的游戏策略。然后,我们用完美的信息多玩者游戏来概括这两种算法。我们证明,这些简单化也是完整的:他们找到一个平衡点。
相关内容
《计算机信息》杂志发表高质量的论文，扩大了运筹学和计算的范围，寻求有关理论、方法、实验、系统和应用方面的原创研究论文、新颖的调查和教程论文，以及描述新的和有用的软件工具的论文。官网链接：https://pubsonline.informs.org/journal/ijoc
专知会员服务
113+阅读 · 2019年11月24日
Arxiv
0+阅读 · 2021年11月11日
Arxiv
0+阅读 · 2021年11月11日
Arxiv
0+阅读 · 2021年11月10日
An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
Arxiv
0+阅读 · 2021年11月10日
相关VIP内容
专知会员服务
113+阅读 · 2019年11月24日
相关资讯
相关论文
Arxiv
0+阅读 · 2021年11月11日
Arxiv
0+阅读 · 2021年11月11日
Arxiv
0+阅读 · 2021年11月10日
An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
Arxiv
0+阅读 · 2021年11月10日
微信扫码咨询专知VIP会员