改进UCT算法在爱恩斯坦棋中的应用

摘要：

UCT(Upper Confidence Bound Apply to Tree)算法是蒙特卡罗搜索算法的延展,因其鲁棒性强而受到广泛关注,且被应用于计算机博弈系统.爱恩斯坦棋是近年国内博弈大赛引进的新棋种,在竞赛中投骰子所引发的随机性和娱乐性吸引了广大学者的目光.从全局优化着法角度出发,在爱恩斯坦棋博弈系统中引入 UCT算法.首先,针对当前计算机多核现状,利用并行计算方法进一步优化 UCT 算法;其次,针对 UCT算法的最优着法需求,引入当前估值因子(WINK)和次优节点平衡因子(UCTK) ,以此辅助增加估值的精确度,决策胜率与着法的优先关系,提高算法的收敛效率;最后,构造了爱恩斯坦棋博弈系统,通过与基于极大极小算法、α-β算法以及蒙特卡罗算法的爱恩斯坦棋博弈系统进行机-机对弈,其胜率提高了25%,并在全国计算机博弈大赛中获冠军,这进一步验证了改进算法的有效性.

关键词：UCT算法、爱恩斯坦棋、并行计算、平衡优化

所属期刊栏目：45

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金－青年科学基金项目61502065;重庆市基础科学与前沿技术研究计划项目cstc2015jcyjA40041;重庆市重庆理工大学研究生创新基金YCX2016238

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

页数：共5页

页码：196-200