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

Application of Improved UCT Algorithm in EinStein Würfelt Nicht!Computer Game

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

UCT(Upper Confidence Bound Apply to Tree)algorithm,as the extension of Monte Carlo search algorithm,is widely concerned and applied to computer game system because of its strong robustness.EinStein würfelt nicht!game is a new kind of game introduced in the domestic game competition in recent years,and the randomness and entertainment of throwing the dice in the competition attracts the participation of the majority of scholars.From the perspective of global optimization method,UCT algorithm was introduced to apply in EinStein würfelt nicht!game system.Firstly,the UCT algorithm is further optimized by using the parallel computing method based on the current state of multi-core computer.Secondly,the current winning factor(WINK)and the optimal node selection factor(UCTK)are introduced to optimize the optimal relationship between the decision winning percentage and the move.Finally,a complete EinStein würfelt nicht!game system is constructed.The winning percentage is improved by 25%by computer-computer game with the game system based on the Minimax algorithm,α-βalgorithm and Monte Carlo algorithm,and it has won the champion in the National Computer Game Contest,which further validates the effectiveness of the algorithm.