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

摘要

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