论文部分内容阅读
人机博弈是人工智能的一个重要研究领域,其中不完全信息的人机博弈能够模拟现实复杂世界中不确定环境下的决策,因此越来越受到关注。四国军棋是一种典型的不完全信息游戏,其特点是不仅需要在对手和同盟棋子信息不确定的情况下做出决策,而且需要考虑与同盟的合作问题。在人机博弈研究中,博弈树的搜索是提高人机博弈系统智能的核心问题之一。四国军棋的博弈树具有分支庞大,支付值模糊等特点,这给四国军棋博弈树搜索的研究带来了困难与挑战。本文围绕四国军棋的人机博弈搜索算法展开深入的研究与分析,主要工作如下: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算法所访问的节点同等规模下访问的节点依次减少,而花费的内存依次增多。