爱恩斯坦棋计算机博弈算法的研究与实施

发布时间：2020-09-23 06:21

　　计算机博弈,也称机器博弈,是人工智能领域极具挑战的一个分支。计算机博弈的研究,最早追溯到20世纪50年代阿兰图灵所设计的第一个纸上象棋程序。经过近七十年的研究,全球计算机博弈领域的专家、学者们为计算机博弈贡献比较丰富的理论、实战案例分析,包括相关的技术、方法与策略,特别是国际象棋、围棋等棋类计算机博弈,取得了令人惊讶的成果。比如,1997年国际象棋棋王卡斯帕罗夫对战IBM深蓝、2016年世界围棋九段李世石对战谷歌AlphaGo,均以人类棋手失败而告终,藉此人们对计算机博弈有了崭新认识,真正认识到计算机博弈领域,人工智能的强大。相比国外的精彩,国内计算机博弈的研究起步较晚,但也发展迅速,比如,从2006年首届全国性计算机博弈竞标赛开始,迄今已经成功举办11届比赛,近年来每年参加决赛的师生有300多支队伍、400余名师生,角逐17个项目,参加高校近40所,这些活动极大推动了我国计算机博弈活动的发展。本论文选择了不完全信息博弈、并非大家喜闻常见的爱恩斯坦计算机博弈为研究对象,爱恩斯坦棋具有多变的初始对局状态和在行棋过程中需要通过掷骰子决定具体走子范围的特点,这既提高了博弈过程的趣味性,也增加了博弈决策的研究难度。论文引入计算机博弈领域的著名UCT(Upper Confidence Bound Apply to Tree)算法,提出改进思想及其实施方法,在此基础上构建新的博弈策略系统,以提升棋力。为此,全文首先阐述了计算机博弈基本原理以及相关技术;其次,介绍了爱恩斯坦棋规则并建立了数学模型;然后,比较深入分析了UCT算法,构建应用策略;最后,开发了爱恩斯坦棋博弈系统,参加全国比赛,验证成果。论文在以下方面开展细小的创新工作:(1)确立攻守平衡基本策略。比较详细分析了爱恩斯坦棋特征并建立数学模型,从攻守结合和削减掷骰子所带来决策影响力角度,与调节进攻因子、防守因子和保护因子为手段,优化了估值方法,构建了二次估值函数,极大提高了爱恩斯坦棋计算机博弈中的估值准确性。(2)建立混合优化算法。提出了基于随机模拟的蒙特卡洛算法和基于预测的期望搜索算法相结合的混合优化算法(Hybrid Optimization Algorithm),并将二次估值函数应用到混合优化算法之中,提高了机器学习方法蒙特卡洛的模拟搜索过程与运行效率。(3)提出提速与全局优化着法方法。基于现在PC机强大的多核计算能力,引入并行计算方法,提高了UCT算法运行速度;引入当前估值因子(WINK)和次优节点平衡因子(UCTK),以决策估值方法部分克服了博弈着法优选难题,促使博弈全局性最优着法的产生。论文作者携带上述研究成果武装的KnighTeam-AN2程序跟随计算机博弈团队参加了2016年在沈阳航天航空大学和2017年在重庆互联网学院、重庆理工大学举办的2届全国比赛,均取得全国冠军。这直接证明了论文研究成果的可行性与有效性。
【学位单位】：重庆理工大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP18

【参考文献】