论文部分内容阅读
计算机的人工智能(Artificial Intelligence,简称AI)研究一直是人类一个富于挑战的实践。让计算机具有智能,是科研学者一直为之奋斗的课题。而在计算机AI的研究领域中,让传统的棋类博弈游戏具有智能,一直是人们关注和研究的内容。棋类博弈人工智能,一般包括博弈搜索、局面评估两个方面。顶尖的博弈智能系统还具备自学习的能力,在对局中通过学习不断地提高AI。各种棋类游戏虽然玩法各异,都是基本的博弈算法是通用。其中,作为博弈游戏AI最核心的博弈树搜索算法,是整个博弈AI的基础,同时也是最核心的内容。所以,对博弈树搜索算法的研究和设计,具有重要的现实意义。本论文就是通过对博弈搜索关键技术的分析,设计和实现一个基于改进博弈树搜索算法的黑白棋对弈系统。本论文对基于改进博弈树的黑白棋设计与实现工作,主要体现在以下几个方面:一、对博弈游戏核心的博弈树搜索算法等关键技术进行了较全面的研究和分析。从基本的min-max算法、alpha-beta剪枝、到基于启发式的优化策略、基于期望窗口和有损剪枝的优化策略,到使用多处理器的并行博弈计算等;尽量做到了全面而又系统,为后面的博弈树搜索算法的设计和改进奠定了基础。二、以面向对象的设计思想,设计和实现黑白棋的人工智能对弈系统。在设计上,采用了完全面向对象的方法,把人工智能的各个方面抽象成人类智能对应的推理、分析、记忆和自学习几个方面,然后对这几个部分分别进行设计,改变了以往以算法为核心的形式。三、在黑白棋博弈树搜索算法的实现上,对原来的博弈树搜索算法进行了一定改进。自行设计了一个基于双置换表、浅层探测启发和―杀手‖启发的搜索算法,并且具备动态选择要排序的结点进行排序的能力。这样大大提高了alpha-beta剪枝的效率。同时使用零窗口搜索的MTD(f)方法,一方面提高了效率,另一方面有利于以后的并行计算实现的扩展。四、黑白棋的下棋规则和局面评估方面,使用了位棋盘的数据结构的设计和基于模板匹配的局面评估方法,最大程度地提高了下棋的效率和AI。位棋盘和基于模板匹配的方法是黑白棋程序现阶段先进的设计方法,同时也是其它棋类系统设计的发展趋势。五、在黑白棋对弈系统开局库和自学习方面:开局库并没有使用传统的树型结构,而是使用基于一维线性表的二分查找方法来实现。同时,区别于一般的系统的自学习能力,就是自学习除了可以提高AI之外,还可以不断地提高下棋效率。最后,通过测试,改进的启发式博弈树搜索比原alpha-beta搜索和传统的启发搜索在效率上有了相当的提高。同时经测试,本黑白棋人工智能对弈系统已经具备了较高的智能,具有一定的研究和使用意义。