非完美信息博弈算法研究与军棋博弈系统设计与实现

摘要

机器博弈目前是人工智能的一个重要研究领域，成为验证了人工智能各项成果的良好平台。非完美信息博弈作为机器博弈中的一个重要分支，相比于对手信息透明的完美信息博弈，更接近现实复杂世界中不确定环境下的决策，具有更深层次的研究价值。军棋是在中国广泛流行的棋盘类游戏，属于典型的非完美信息博弈问题，对其进行研究具有很强的实际意义。本文针对非完美信息博弈和军棋本身特点，对于其中的招法生成、搜索算法、概率推断三个问题进行了研究。同时基于以上研究结果，设计了军棋博弈系统，具有接近人类的智能水平。
　　针对招法生成问题:结合军棋的棋盘特点和行棋规则，本文提出快速招法生成器来代替传统穷举搜索棋盘的办法。提出了基于公路、铁路、工兵三种快速招法生成器，将当前可能出现的棋盘局面进行二进制数编码，之前进行预处理，在招法生成中可以搜索局面想匹配的二进制数，快速给出招法。同时给出实验对比，来验证快速招法器的有效性。
　　针对搜索问题问题:将传统运用在完美信息信息博弈中的UCT算法进行改进，结合其原理和非完美信息博弈的特点提出了确定性融合UCT算法。对于这种算法的概念、流程、数据结构给出介绍，同时将这种搜索算法应用到军棋中，最后对该算法给出了理论与实验的证明。
　　针对概率推断问题:由于军棋这类非完美信息博弈中对手棋子类型的不可见性，如何建立一个好的概率模型准确地推理出对手的状态成为一个重要研究问题。为此提出了非完美信息概率推断模型，将传统用于图像学的马尔科夫网络模型和快速招法预测算法相结合，完成对于当前棋盘局面的推断。同时，将非完美信息概率推断模型应用到军棋中，给出实验验证模型的可行性。
　　最后总结了以上三种针对军棋这类非完美信息博弈问题的改进方法，设计并实现军棋博弈系统。详细介绍了军棋博弈系统中主要构成模块及它们之间的逻辑关系，同时给出了大量的实验结果，证明了改进算法的有效性。

目录

声明

摘要

第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 展望

参考文献

致谢

攻读硕士学位期间的论文项目情况