四国军棋的人机博弈搜索算法研究

论文摘要

人机博弈是人工智能的一个重要研究领域,其中不完全信息的人机博弈能够模拟现实复杂世界中不确定环境下的决策,因此越来越受到关注。四国军棋是一种典型的不完全信息游戏,其特点是不仅需要在对手和同盟棋子信息不确定的情况下做出决策,而且需要考虑与同盟的合作问题。在人机博弈研究中,博弈树的搜索是提高人机博弈系统智能的核心问题之一。四国军棋的博弈树具有分支庞大,支付值模糊等特点,这给四国军棋博弈树搜索的研究带来了困难与挑战。本文围绕四国军棋的人机博弈搜索算法展开深入的研究与分析,主要工作如下:1.针对四国军棋开局中博弈树分支多,模糊度大的特点,提出了基于定时器的期望搜索算法Aspiration with Timer算法,简称为AWT。AWT算法利用定时器动态调整窗口来提高搜索效率,快速找到次优解使游戏进入中局。实验结果表明,它以较小的额外内存消耗换取了快速的搜索效率。2.针对四国军棋不完全信息性,本文提出基于信息论的一种新的搜索算法——Alpha -Beta-Threshold算法。该搜索算法使用门限观念能动态调整搜索深度,其核心思想是在确定度高的分支上搜索的深度比较深,在不确定度高的搜索分支上搜索的深度比较浅。3.由于Alpha-Beta-Threshold算法的性能和着法的排列顺序很相关,本文进一步提出了一种改进算法Certain-Threshold算法。Certain-Threshold在搜索开始的时候,首先按照确定度以及着法的好坏进行排序,首先搜索确定性高的,好的节点的分支,产生更多的剪枝,提高算法性能。为了处理相同支付值情况下不同路径熵的问题,我们进一步改进,提出了Best-Certain -Threshold算法,综合考虑静态估值和路径熵,通过一定规则重新定义了支付值。4.为了更好讨论和分析Alpha-Beta-Threshold,Certain-Threshold,Best-Certain -Threshold算法性能,本文通过人工产生随机博弈树和四国军棋产生的博弈树两种方法进行实验比较与分析。实验结果显示:Alpha-Beta-Threshold算法,Certain-Threshold算法,Best-Certain-Threshold算法所访问的节点同等规模下访问的节点依次减少,而花费的内存依次增多。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 四国军棋与人机博弈
• 1.1.1 人机博弈简介
• 1.1.2 四国游戏规则
• 1.1.3 游戏特点
• 1.1.4 研究关键点
• 1.2 搜索算法研究现状
• 1.2.1 搜索算法分类
• 1.2.2 搜索算法研究历史
• 1.3 本文主要工作和结构
• 第二章 经典搜索算法
• 2.1 极大极小算法思想
• 2.2 Alpha-Beta 及其改进算法
• 2.2.1 Alpha-Beta 算法
• 2.2.2 Aspiration 算法
• 2.2.3 PVS 算法
• 2.2.4 实验分析比较
• 2.3 SSS*及其相关算法
• 2.3.1 SSS*算法
• 2.3.2 MT-SSS*算法
• 2.3.3 实验分析与比较
• 第三章 AWT 算法
• 3.1 动机
• 3.2 AWT 算法思想
• 3.3 AWT 高效性和可靠性分析
• 3.4 参数M，N 选定
• 3.5 实验结果与分析
• 3.5.1 Alpha-Beta，Aspiration 和AWT 算法性能比较
• 3.5.2 不同参数取值下的AWT 算法性能比较
• 3.6 总结
• 第四章 不完全信息搜索算法
• 4.1 动机
• 4.2 基于信息熵的门限思想
• 4.2.1 门限思想
• 4.2.2 阈值的确定
• 4.3 Alpha-Beta-Threshold 算法
• 4.3.1 算法思想
• 4.3.2 伪代码
• 4.3.3 算法正确性
• 4.3.4 存在问题
• 4.4 Certain-Threshold 算法
• 4.4.1 算法思想
• 4.4.2 伪代码
• 4.4.3 存在问题
• 4.5 Best-Certain-Threshold 算法
• 4.5.1 算法思想
• 4.5.2 伪代码
• 4.6 实验分析
• 4.6.1 为什么使用随机博弈树
• 4.6.2 随机博弈树生成
• 4.6.3 随机树下的算法性能分析
• 4.6.4 四国博弈树的生成
• 4.6.5 四国军棋实际博弈树下的算法性能分析
• 第五章 总结与展望
• 参考文献
• 致谢
• 在学期间的研究成果及发表的学术论文