封闭域UCT算法的实现及其性能测试

摘要：

UCT算法在9×9棋盘上的水平，已经接近最优秀的专业棋手，但在19×19棋盘上还不尽人意．一种可能的改进是用多个并行的局部UCT搜索来替代全局UCT搜索，以期用同样的计算资源来达到更深的有效搜索深度．本文力图沿着此研究思路做一些初步的尝试．我们通过改写Fuego的全局UCT搜索算法，本文实现了封闭域UCT搜索算法，并在64个封闭域围棋死活问题上进行了测试．初步结果表明，封闭域UCT算法能够在不使用任何领域知识的情况下，把给定问题的初始分支系数从5～16降低到2．3以下．从正确率和速度两项指标来看，多个并行的局部UCT搜索的研究思路具备可行性．

关键词：搜索算法、计算机围棋、封闭域死活问题、最小迭代次数

分类号：TP181(自动化基础理论)

资助基金：国家自然科学基金项目61163004；云南省应用基础研究面上项目2010CD027．

在线出版日期：2015-01-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：51-56