论文部分内容阅读
计算机博弈是人工智能研究的重要领域之一,棋类博弈又是计算机博弈中的重要分支,目前其他棋类博弈均得到了较圆满的解决,唯有计算机围棋的最高水平还不及人类的初级棋手。围棋是检验人工智能发展水平的试金石,开发出与职业棋手程度相当的计算机围棋程序有助于对人类认知科学的探索。对当前棋局做出准确高效的静态评估不仅有利于棋手判断当前局势,确定攻防着点,引导下一步棋的走向,而且能够指导信心上界树(Upper Confidence bounds applied to Trees,简称为UCT)算法平衡探索与利用。本文提出了一种棋子影响函数,并在此基础上构建了一个量化模型来解决棋局的静态评估问题;然后将静态评估结果与UCT算法相结合,构造出一种UCT剪枝策略。本文所设计的算法可以提高程序的运行效率,从而提升程序棋力,具有一定的理论研究意义与实际应用价值。本文主要研究成果有:(1)设计了一种棋子的影响函数Influ。过去的影响函数通常没有考虑到对方棋子的阻挡问题,从而造成计算影响值时精度较低。本文采用直线和斜线距离相结合的方式来表征棋子到空点的距离,并利用A*算法进行路径寻优,最终获取单个棋子对空点的影响值;(2)基于Influ棋子影响函数,构造Value全局静态评估量化模型。首先,将单个棋子对空点的影响值线性叠加;然后,进行边角调整、阈值规范和归一化操作等处理步骤,获得棋盘上所有空点受到的总的影响值;最后,使用多级种群竞争消亡法优化模型参数,最终得到Value量化模型。实验表明,Value模型的计算结果与职业棋手的判断非常接近,计算精度适用于棋局的序盘和中盘阶段,为后续的剪枝策略奠定了基础;(3)将Value模型获得的静态评估结果与UCT算法相结合,构造剪枝策略Static。利用静态评估值作为节点的评分标准,以此减少搜索深度,从而在单位时间内增加蒙特卡罗模拟次数,并指导搜索偏向有意义的方向。实验表明,Static剪枝策略可以提高搜索效率,进而提升程序的棋力。