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

摘要

计算机博弈，也称机器博弈，是人工智能领域极具挑战的一个分支。计算机博弈的研究，最早追溯到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届全国比赛，均取得全国冠军。这直接证明了论文研究成果的可行性与有效性。

目录

声明

第1章 绪论

1.1 本课题的研究背景

1.2 计算机博弈的研究现状

1.3 本课题的研究意义

1.4 本文主要工作

第2章 计算机博弈技术解析

2.1 博弈基本原理

2.2 博弈相关技术

2.3 研究对象分析

2.4 本章小结

第3章 爱恩斯坦棋简介及博弈建模

3.1 规则简介

3.2 特征分析

3.3 数学建模

3.4 估值函数的设计

3.4 本章小结

第4章 UCT算法的应用与改进

4.1 经典博弈树搜索算法

4.2 混合优化算法

4.3 UCT算法及其改进

4.4 UCT算法策略性能对比实验

4.5 本章小结

5 爱恩斯坦棋计算机博弈系统

5.1系统结构设计

5.2 系统实现

5.3 系统测试

5.4本章小结

6 总结及展望

6.1 本文的主要贡献与结论

6.2 未来工作与展望

致谢

参考文献

个人简历、在学期间发表的学术论文及取得的研究成果