论文摘要
机器博弈目前是人工智能的一个重要研究领域,成为验证了人工智能各项成果的良好平台。非完美信息博弈作为机器博弈中的一个重要分支,相比于对手信息透明的完美信息博弈,更接近现实复杂世界中不确定环境下的决策,具有更深层次的研究价值。军棋是在中国广泛流行的棋盘类游戏,属于典型的非完美信息博弈问题,对其进行研究具有很强的实际意义。本文针对非完美信息博弈和军棋本身特点,对于其中的招法生成、搜索算法、概率推断三个问题进行了研究。同时基于以上研究结果,设计了军棋博弈系统,具有接近人类的智能水平。针对招法生成问题：结合军棋的棋盘特点和行棋规则,本文提出快速招法生成器来代替传统穷举搜索棋盘的办法。提出了基于公路、铁路、工兵三种快速招法生成器,将当前可能出现的棋盘局面进行二进制数编码,之前进行预处理,在招法生成中可以搜索局面想匹配的二进制数,快速给出招法。同时给出实验对比,来验证快速招法器的有效性。针对搜索问题问题：将传统运用在完美信息信息博弈中的UCT算法进行改进,结合其原理和非完美信息博弈的特点提出了确定性融合UCT算法。对于这种算法的概念、流程、数据结构给出介绍,同时将这种搜索算法应用到军棋中,最后对该算法给出了理论与实验的证明。针对概率推断问题：由于军棋这类非完美信息博弈中对手棋子类型的不可见性,如何建立一个好的概率模型准确地推理出对手的状态成为一个重要研究问题。为此提出了非完美信息概率推断模型,将传统用于图像学的马尔科夫网络模型和快速招法预测算法相结合,完成对于当前棋盘局面的推断。同时,将非完美信息概率推断模型应用到军棋中,给出实验验证模型的可行性。最后总结了以上三种针对军棋这类非完美信息博弈问题的改进方法,设计并实现军棋博弈系统。详细介绍了军棋博弈系统中主要构成模块及它们之间的逻辑关系,同时给出了大量的实验结果,证明了改进算法的有效性。
论文目录
摘要Abstract第1章 引言1.1 研究背景1.1.1 课题背景1.1.2 国内外研究现状1.1.3 现状分析1.2 本文贡献1.3 组织结构第2章 机器博弈历史发展与相关算法介绍2.1 机器博弈博简介2.1.1 机器博弈历史背景与发展2.1.2 机器博弈模型2.2 基于对手信息的机器博弈分类2.2.1 完美信息博弈概念及相关搜索2.2.2 非完美信息博弈定义及相关介绍2.3 基于完美信息的机器博弈基本搜索算法2.3.1 极大极小算法2.3.2 Alpha-Beta搜索算法2.3.3 PN search搜索算法2.4 基于非完美信息博弈的搜索算法2.4.1 Double Dummy算法2.4.2 CFR算法2.5 本章小结第3章 数据结构表示及快速招法生成器3.1 快速招法生成器设计与数据结构3.1.1 军棋的棋盘及其数据结构定义3.1.2 公路快速招法生成器设计与实现3.1.3 铁路快速招法生成器设计与实现3.1.4 工兵快速招法生成器设计与实现3.2 快速招法生成器对比验证3.3 本章小结第4章 基于非完美信息博弈的UCT算法改进4.1 UCT算法介绍4.1.1 UCB1算法描述4.1.2 UCT算法描述4.1.3 UCT算法的分析4.2 确定性融合UCT算法设计与应用4.2.1 确定性融合UCT算法4.2.2 确定性融合的UCT算法在军棋中的应用4.2.3 确定性融合UCT算法的收敛性验证4.3 本章小结第5章 基于非完美信息博弈概率模型问题的研究与应用5.1 概率图模型在非完美信息博弈下运用5.1.1 马尔科夫知识推测网络5.1.2 军棋中概率图模型的设计与实现5.1.3 概率模型更新算法在军棋中运用5.2 快速招法预测算法设计与应用5.2.1 置信状态概率更新5.2.2 快速招法预测算法流程5.2.3 军棋系统中快速招法预测算法的设计与实现5.3 非完美信息概率推断模型设计与在军棋中应用5.4 概率模型实验验证5.4.1 统计表实验分析5.4.2 概率图模型误差验证5.4.3 快速招法估值误差计算5.4.4 非完美信息概率推断模型的误差值5.5 本章小结第6章 军棋博弈系统设计与实现6.1 军棋博弈系统的结构设计6.2 军棋系统的数据表示6.2.1 军棋系统的棋盘模块设计6.2.2 军棋外部信息表示模块6.2.3 军棋算法搜索模块6.2.4 军棋概率图模型数据结构设计6.3 军棋博弈系统实战测试6.4 本章小结第7章 总结与展望7.1 总结7.2 展望参考文献致谢攻读硕士学位期间的论文项目情况
相关论文文献
标签：非完美信息博弈论文; 算法论文; 军棋论文; 概率图模型论文;
