您好、欢迎来到现金彩票网!
当前位置:秒速时时彩登录 > 搜索博弈树 >

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

发布时间:2019-06-03 23:52 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  四国军棋的人机博弈搜索算法研究 图 4.8 Best-Certain-Threshold 思想47 图 4.9 Best-Certain-Threshold 伪代码48 图 4.10 随机树节点50 图 4.11 随机树节点PAYOFF 生成50 图 4.12 随机树节点AverageEntropy 生成51 图 4.13 随机树的数据结构51 图 4.14 随机树存储52 图 4.15 Alpha-Beta 与Alpha-Beta-Threshold 访问节点数比较53 图 4.16 Alpha-Beta 与Alpha-Beta-Threshold 内存消耗比较53 图 4.17 Alpha-Beta-Threshold 不同路径熵阈值下访问的节点数54 图 4.18 Alpha-Beta,Alpha-Beta-Threshold,Certain-Threshold 访问的节点数55 图 4.19 Alpha-Beta,Alpha-Beta-Threshold,Certain-Threshold 内存消耗55 图 4.20 四种算法访问的节点数比较56 图 4.21 四种算法内存消耗比较56 图 4.22 Alpha-Beta 与Alpha-Beta-Threshold 访问节点数比较58 图 4.23 Alpha-Beta 与Alpha-Beta-Threshold 内存消耗比较59 图 4.24 Alpha-Beta,Alpha-Beta-threshold,Certain-Threshold 访问的节点数59 图 4.25 Alpha-Beta,Alpha-Beta-Threshold,Certain-Threshold 内存消耗60 图 4.26 四种算法访问的节点数比较61 图 4.27 四种算法内存消耗比较61 表清单 * 表 2.1 SSS 规则库19 表 4.1 棋子的概率分布34 VI 南京航空航天大学硕士学位论文 注释表 PAYOFF 节点支付值 D,d 博弈树深度 live 当前尚未展开的节点 solved 已遍历过了的节点 Alpha 搜索窗口的下限 Beta 搜索窗口的上限 Threshold 策略路径阈值 M 窗口下限第一次增长的参数 N 窗口下限第二次增长的参数 ψ 计算机每秒可搜索的节点数 L 博弈树分支数 S 搜索的状态 T 移动棋子允许考虑的时间 VII 承诺书 本人郑重声明:所呈交的学位论文,是本人在导师指导下,独立进 行研究工作所取得的成果。尽我所知,除文中已经注明引用的内容外, 本学位论文的研究成果不包含任何他人享有著作权的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体,均已在文中以明确方式标 明。 本人授权南京航空航天大学可以有权保留送交论文的复印件,允许 论文被查阅和借阅,可以将学位论文的全部或部分内容编入有关数据库 进行检索,可以采用影印、缩印或其他复制手段保存论文。 (保密的学位论文在解密后适用本承诺书) 作者签名: 日 期: 南京航空航天大学硕士学位论文 第一章 绪论 本章首先简述人机博弈的研究背景和研究现状,介绍四国军棋的游戏规则以及研究的关键 点。然后重点阐述人机博弈搜索算法的研究现状。最后给出本文的主要工作及组织结构。 1.1 四国军棋与人机博弈 1.1.1 人机博弈简介 人机博弈是人工智能的一个重要研究方向。早在上世纪五十年代,就有人设想利用机器来 实现机器与人的对弈。1950,Konrad Zuse ,Claude Shannon,NorBert Wiene 和阿兰图灵就开始 [1] [2] 研究国际象棋(Chess )的程序 。1959 年,A.L.Samuel 从机器学习的角度对西洋跳棋(checker) 进行研究。70 年代初,A.Zorborbrist 在他的博士论文里[3]从模式识别的角度对围棋(Go)博弈 进行研究,编写了第一个完整的围棋程序。20 世纪七八十年代,学者们认识到博弈程序的智能 水平与搜索深度有很大关系,于是开始大量研究各种搜索算法。80 年代末,随着空着剪枝,单 步延伸等高级搜索算法的研究和机器学习方法的发展,机器智能得到了很大提高。1989 年,第 一界计算机奥林匹克大赛在英国伦敦正式开幕,人机博弈在世界上的影响日益广泛。1994 年, 跳棋程序CHINOOK 挑战了跳棋世界冠军。1997 年,IBM “深蓝”打败保持十几年世界棋王头衔 的卡斯帕罗夫轰动了一时。随着人机博弈的发展,一部分棋类的人机博弈程序已对人类棋手造 成一定的威胁。 国际上人机博弈程序主要是研究国际象棋,西洋跳棋,经过专家学者几十年的努力取得很 大的成就。而国内人机博弈起步较晚,主要研究对象是中国象棋和围棋。目前,中国象棋博弈 程序的智能水平已经达到大师级的水平,比较有名的如:棋天大圣,象棋骑兵。而围棋的研究 存在很多难点,其状态空间的复杂度是所有棋牌类游戏中最高的,因此也是极具挑战性的研究 课题。四国军棋是国内三大棋类游戏之一,其研究刚刚起步[4~7] 。四国军棋的研究同样难点重重, 首先它的棋盘 17*17,状态空间和博弈树的复杂度也很高。其次,不同于中国象棋和围棋,它 是一种不完全信息游戏。玩家在下棋过程中只能看到行棋的路线,但不知道对方棋子的具体类 型。同时,四国军棋支持四人游戏,这时会涉及到同盟方合作的问题。这些都给四国军棋的研 究带来大的困难。 2002 年,H.Jaan van den Herik 等[8]纵观人机博弈的发展历史,从状态空间和博弈树的复杂 度角度总结了人机博弈的研究进展,并预测未来十年人机博弈的发展趋势。其文中指出对于状 态空间和博弈树的复杂度很高的博弈来说,采用蛮力搜索和知识库的方法都难以解决。因此, 人机博弈的研究尤其是不完全信息人机博弈的研究需要引入新的理论和方法。 1 四国军棋的人机博弈搜索算法研究 1.1.2 四国游戏规则 1.游戏介绍 四国军棋是我国深受欢迎的棋类游戏之一。四国军棋游戏可以支持两国对拼也可支持四国 大战。当四人游戏时,四人在棋盘上分占四角,分为两方,相对的两家联盟与另外两家对抗, 互相配合战斗;两人游戏时,则分占棋盘的上下两角,相互作战。四国军棋界面如图1.1 所示。 2 .走子规则 行走路线包括公路线和铁路线,显示较细的是公路线,任何棋子在公路线上只能走一步, 显示为粗黑的为铁路线,铁路上没有障碍时,工兵可在铁路线上任意行走,其它棋子在铁路线 上只能直走或经过弧形线,不能转直角弯;棋子落点包括节点、行营、两个司令部,行营是个 安全岛,进入以后,敌方棋子不能吃行营中的棋子,军旗必须放在司令部中,进入任何司令部 的棋子不能再移动。棋子布局的限制:炸弹不能放在第一行,地雷只能放在最后两行,军旗只 能放在司令部。 3 .吃子规则 四国军棋棋子的大小顺序如下:司令军长师长旅长 团长营长连长排长工兵。小棋 遇大棋被吃,地雷小于工兵,大于所有其他棋子;炸弹与任何棋子相遇时,双方都消失。 4 .胜负判决 幸存的一方为胜家,军旗被扛、无棋可走都会被判负; 图 1.1 四国军棋界面 1.1.3 游戏特点 四国军棋是典型的不完全信息游戏,其特点是需要在对手和同盟棋子不确定信息的情况下 2 南京航空航天大学硕士学位论文 做出决策,同时要考虑同盟之间的合作问题。相比起象棋等其他游戏,它有以下四个特点。 1.不完全信息 开局时,玩家不知道对手及同盟方的布局,只能依据经验猜测。随着游戏的进行,也只能 通过棋子的拼杀获得部分棋子信息(通过第三方裁判获知棋子之间“大于”、“小于”或“ 同归于尽” 的关系) 。与牌类游戏相比,玩家获得的信息相对较少,因为牌类游戏中玩家打出的牌是可见的。 2. 玩家布局 在象棋等游戏中玩家的布局是固定的,并且都是相同的;在牌类游戏中玩家手上的牌具有 随机性,并且没有位置的概念;在四国军棋中玩家通过棋子之间位置的交换进行布局,布局有 阵型之分,并且各玩家根据自己的兴趣会选择不同的阵型。一般情况下,在玩家的布局中相邻 棋子之间存在关联关系,也称为相关性,例如,师长周围往往跟着炸弹,小的棋子后边跟着大 的棋子。这种相关性虚虚实实,是陷阱还是真正意图,有待玩家通过试探获知。同时,根据这 种相关性,在下棋过程中高手往往能凭借自己的经验逐渐推测出对手25个棋子中大部分棋子的 类型,在四国军棋中这是非常重要的。 3. 多人零和合作游戏 不完全信息游戏大部分是两人零和游戏,而四国军棋分为两人和四人游戏,分别称为1v1 和2v2模式。在1v1模式下,四国军棋为两人零和游戏;在2v2模式下,则为多人零和游戏。与其 它不完全信息博弈一样,四国军棋需要处理不完全信息下的决策。不同的是,在2v2模式中,玩 家需要在对手和同盟棋子不确定信息的情况下与同盟合作,同盟之间的决策是合作决策,处理 起来非常困难。 4. 博弈树复杂度 四国军棋棋盘的大小是17*17,使得玩家在棋盘上行棋空间大。在1v1模式下,四国军棋博 弈树的平均分支大约为150;在2v2模式下,大约为90 。因此,四国军棋的状态空间复杂度非常 大。并且行棋规则少,使得玩家有大量合理的走法,再加上棋子的信息是不确定的,因此四国 军棋的博弈树复杂度非常大。另外,四国军棋也不是收敛游戏,随着游戏的进行棋子灵活性逐 渐增加,博弈树复杂度并不会降低。 1.1.4 研究关键点 [4] 四国人机博弈系统的主要有5 个基本组成要素 :知识表示、走法产生器、搜索算法和评 价函数,开局库和残局库。在不完全信息人机博弈中,对手信息是不确定的,导致对对手的建 模、局面的评估等都非常困难,因此需要用到概率论、自动推理和机器学习等方法和技术。 四国军棋行走路线包括铁路线和公路线,棋子落点包括节点、行营、两个大本营,棋盘是 17*17的。我们采用17*17个字节的二维数组来表示四国军棋棋盘上的节点类型,数组中每个字 节代表棋盘上的一个点,其值代表这个节点的类型。在系统中我们用9个数字代表节点。其中-1 3 四国军棋的人机博弈搜索算法研究 表示不合法的点,即棋子走到这个点是不合法的;0代表经过点,即不能停留,在九字宫( 中间 九个点)才会出现;1代表大本营,里面的棋子不能动,有2个;2代表行营,里面的棋子是安全 的,有5个;3代表格子里的点,在里面的棋只能走一步,有7个;4代表水平铁路线代表垂直铁路线代表拐角点,可以拐弯,有2个;7代表直角点, 不可以拐弯,有2个。可以看出由1至7这几个值组成了这30个格子的节点类型。 除了棋盘信息还有棋子信息,四国中一共有12 中不同种类棋子,每一方有25 个棋子。在 系统中我们采用一维数组来依次代表一方的棋子,数组的值代表了棋子的种类。 走法产生器是相应的走法生成机制,负责生成一个局面的所有走法,并将其保存到数据结 构中。根据四国军棋的游戏规则,走法产生器可以生成所有合理的走法。在进行走法生成的时 候,往往伴随搜索的进行。当走法生成后,在搜索建树时需要模拟走棋,因此在恢复局面时需 要撤销走棋。模拟走棋时需要把走棋后的局面变化入栈,撤销走棋时还原局面。 如果在博弈树的搜索过程中生成所有的走法,得到的博弈树将十分庞大。由于计算机的处 理能力和存储空间有限,所以博弈树的搜索深度有限。高效的搜索算法能及时剪去没必要扩展 的节点,从而提高搜索的深度,也就能提高博弈程序的智能水平,因此搜索算法是博弈程序的 核心组成要素。 评估函数是四国程序中核心组成要素。四国智能系统的智能水平和评价函数的准确性息息 相关。评价函数的设计依赖于具体博弈的经验知识,对于四国军棋来讲要考虑棋子价值、棋子 位置、棋子灵活度、棋子配合和军旗安全[4]等特征。在实际应用中,评价函数通过调整特征系 数来评估局面。 四国军棋的棋盘为 17*17,行棋规则少,且玩家只能通过拼杀获得部分信息。这些因素决 定了其状态空间和博弈树的复杂度非常大。由于计算机的处理能力和存储空间有限,所以博弈 树的搜索深度有限。高效的搜索算法能产生更多的节点,提高搜索的深度,从而提高博弈算法 的智能水平。因此搜索算法的设计是研究的关键点。 1.2 搜索算法研究现状 1.2.1 搜索算法分类 人机博弈的核心技术是博弈树搜索算法。1950 年 Shannon 首先提出了极大极小算法 [9] ,奠定了人机博弈的理论基础。博弈树搜索算法也随着博弈程序的发 (Minmax Alogorithm ) 展而日益发展。目前国际上常用的搜索算法可分为深度优先算法和最佳优先算法。深度优先典 型算法 Alpha-Beta 算法[10~15]是 20 世纪 50 年代提出的。20 世纪 60 年代很多学者提出了 Alpha-Beta 算法的改进算法,包括Aspiration 算法[16~18] ,PVS 算法[17~20] ,历史启发,置换表[22,23] [24~26] * [27~39] 及迭代深化 等。另一类最佳优先算法,其典型代表为SSS 算法 。这类算法搜索过程中 4 南京航空航天大学硕士学位论文 * 最先展开访问最有希望的节点,而不是向深度优先那样有一个较为固定的搜索方向。SSS 算法 如今很少在棋类博弈程序中看到,但这个算法的思想对当今博弈树搜索技术有着重要影响。20 世纪90 年代,Aske Plaat 等人利用SSS*算法的思想提出了一种新的最佳优先算法——MT-SSS* [44,45] * 算法 。MT-SSS 表现出很高的性能,在很多博弈程序中得到应用。 1.2.2 搜索算法研究历史 1.Minimax 算法[9] 人机博弈的核心技术是博弈树搜索算法,这也是机器博弈研究的热点。棋牌游戏中,玩家 的思维就是根据当前的局势,思索自己有哪些走法。根据这些走法,设想对方会如何走。这样 就形成了一棵博弈树,玩家思考的博弈树深度越深,则技艺越高超,越有可能赢得游戏。机器 [9] 也可以模拟这样的过程。1950 年Shannon 首先提出了极大极小算法(Minmax Alogorithm ) , 奠定了人机博弈的理论基础。对于每一个棋类博弈游戏程序来说,极大极小树都是其中的核心。 该算法是一个零总和算法,即一方要在可选的行动方案中选择将其优势最大化的选择,另一方 则选择令对手优势最小化的方法。这也是很符合人类思维的。玩家总希望自己的走棋是对自己 最有利的,而自己的走棋也总是对对方来说是最不利的。在游戏中,游戏一方可供选择的行动 方案有很多,因此会生成十分庞大的博弈树。搜索的时间耗费会根据搜索层数的增加呈指数增 长。假设游戏双方平均有 40 种走法,建立一棵(双方各走 50 步)搜索树就需生成约 40100 个叶子节点。这远远超出了计算机的处理能力。因此利用完整的博弈树来进行极小极大分析是 不切实际的。可行的办法是只生成一定深度的博弈树,进行极小极大分析,找出当前最好的行 动方案。至于生成博弈树的深度,由于受到计算机存储空间以及游戏时间的限制,只能视实际 情况而定。 1975 年Knuth 和Moore 又提出负极值(Negamax)算法[10] 。Negamax 算法是在Minimax 算 法提出近20 年后做的一个小改进,在程序功能和效率上是没有区别的,唯一不同之处是实现手 法不同。NegaMax 不需要通过一次判断取极大,一次取极小来执行不同的动作。它通过在传递 参数时取负极大值来消除了两方的差别。这样做使人稍难理解,但是使程序更简洁。 2 .Alpha-Beta 算法[10~15] 在Minimax 搜索的过程中,人们发现有些数据是冗余。如果能剔除这些冗余的数据,将减 小搜索的空间。19 世纪50 年代有人在极大极小算法的基础上加入了Alpha-Beta 剪枝技术。Knuth 和Moore[10]记载,John McCarthy 最先产生这个想法,并创造了Alpha-Beta 算法这个名称。Samuel 在20 世纪50 年代末期在他的西洋跳棋程序里使用了这种剪枝算法[12] ,只是他当时认为程序中 有更为重要的部分就没有提及这个方面。19 世纪60 年代末,Slagle and Dixon[13]在西方文献中 正式发表了整个算法。1963 年Brudon 在俄国发表的论文中也描述了一种和Alpha-Beta 相似的 [14] 算法 。 5 四国军棋的人机博弈搜索算法研究 Alpha-Beta 算法相对于极大极小树算法,省略了许多节点的搜索。对于每个被省略的非叶 子节点来说,这意味这不仅节点本身,而且节点下面的子树也被省略了。这导致Alpha-Beta 算 法需要遍历的节点远远少于极大极小算法所遍历的节点。对于同一棵树来说,Alpha-Beta 搜索 所花费的时间远远少于极大极小算法。1975 年Knuth 和Moore 详细分析了Minimax 算法,为 极大极小数剪枝提供了理论基础,并提出了极小树(Minimal tree)的概念[10] 。极小树是Alpha-Beta 算法在最好的情况下访问的博弈树。假设树的深度是D, 而每个节点有L 个分支,则最小树的 D / 2 D / 2     D 叶子节点为L  +L  −1,对于极大极小树的叶子数L 是个很大提高。这意味着通过剪枝, 程序可以搜索原来两倍的深度,这将极大地提高程序的智能。 3 .Alpha-Beta 改进算法 Alpha-Beta 是使用最为广泛的搜索算法。但Alpha-Beta 有其局限性,它对于节点的排列非 常敏感。在节点排列最理想的情形之下,利用Alpha-Beta 搜索所建立的博弈树的节点数的平方 根的2 倍左右。在最差的情况下,Alpha-Beta 搜索所建立的博弈树节点与极大极小搜索一样。 而对于现实游戏中的建立的博弈树来说,节点的排列顺序是杂乱无章的。所以如何调整节点排 列是提高Alpha-Beta 算法性能的关键。另一方面,Alpha-Beta 算法的性能也和开始搜索的初始 窗口有密切关系。如果缩小初始窗口则可以产生更多剪枝,但也存在着重复搜索的风险。 针对Alpha-Beta 搜索的特点,很多学者提出了Alpha-Beta 算法的改进算法。这些改进算法 可以分为两大类:一种是缩小搜索窗口的大小,产生更多的剪枝,从而更快地找到最好的着法。 典型的算法如Aspiration 算法[16~18] ,PVS 算法[17,19,20]等。另一种则是调整节点的排列顺序,提 [21,21] [22,23] [24~26] 高剪枝效率。典型的算法包括历史启发 ,置换表 及迭代深化 等。这些算法已经被 证明为是非常有效的。下面简要介绍几种典型的Alpha-Beta 改进算法。 Aspiration 算法[16~18]从一开始就选取小的窗口取代了Alpha-Beta 的初始窗口(-∞,+ ∞), 从而在搜索初期就进行大量的剪枝。这个初始窗口的选定很重要,如果选择准确,则可以提高 搜索的效率,大大缩短搜索时间。但如果选择的窗口不适合,则需要重新搜索,优势就不明显 了。 PVS 算法[17,19,20] 旨在用极小的窗口建立极小的搜索树,以此达到高效的搜索。算法假设的 是第一步是最佳的移动,后面的节点使用零窗口搜索产生大量剪枝。但如果第一步的移动不好, 后面的节点就要用正常窗口重新搜索,但这时的窗口也缩小了,其搜索效率也比以完整窗口进 行的搜索高。整体来看,极小窗口搜索在效率上是优于Alpha-Beta 的。这也使得PVS 在实际的 应用中得到了广泛的使用。 历史启发[21,22]在搜索的第一层时评估节点,并将节点的评估值降序排列。按照排列后的节 点顺序访问节点,以此提高搜索效率。历史启发和游戏的具体的特性有很大关系。 置换表及迭代深化[22,23]通过建立了一张表记录搜索过的节点。由于不同走法下建立博弈树 6 南京航空航天大学硕士学位论文 可能走到同一个局面,在这种情况下我们可以直接利用已经搜索过的值,而不需要重新搜索。 设计置换表要充分考虑到时间和空间复杂度的问题。搜索的节点如何存储,如何查找是设计的 难点。 迭置换表及迭代深化[24~26] 由于相邻两层的搜索有一定的相似性,把d-1 层的最佳节点作为 d 层搜索的最先搜索的分支,通过这种方式调整访问节点的顺序,提高搜索效率。在实际应用 中,置换表和迭代深化经常一起使用。 4 .SSS*算法[27~ 39] 从50 年代后期人们开始使用Alpha-Beta 算法开始,经过30 多年的研究,Alpha-Beta 的许 多改进算法性能得到很大提高,在人机博弈程序中得到广泛应用。而Alpha-Beta 及其改进算法 都是深度优先的算法。 1979 年Stockman 介绍了一种完全不同于Alpha-Beta 的最佳优先的算法SSS* [27~39] ,它是一 种最佳优先的算法。顾名思义,它不是按照深度优先搜索的,而是最先展开最有希望的节点。 SSS*维护一张全局的状态表,根据状态表的信息在不同的分支展开多条路径,并不断更新这张 信息表。Stockman 最初提出的SSS*存在一些缺陷,在叶子估计值相等的情况下会出现摆动。于 是Campbell 和Marsland 对SSS*算法作了些改进,改变了节点的插入顺序,解决了摆动问题。 * * SSS 是一种复杂的难以理解的算法。另一个重要问题是 SSS 算法需要花费更大的内存空 间。SSS*需要维护一张全局的状态信息表,而这张表的大小和搜索的深度成指数级增长。而且 状态信息表是有序的,所以维护这张表,插入一个数据或者删除一个数据都会花费很多时间, * [39] 导致算法运行缓慢。这也是在实际应用中很少用到SSS 算法的一个重要原因 。但这种最佳优 先的算法思想对于机器博弈技术有着深远的影响。学者已经证明 SSS*访问的节点数要小于 [40~42] Alpha-Beta 算法 。 * * [43] SSS 还有一种对称的算法DUAL 算法 ,它们分别在适用于不同的场合。Aske Plaat 等人 研究,SSS*在搜索深度为偶数的情况下效果较佳,而DUAL*在搜索深度为奇数的情况下效果较 佳。 5 .MT 体系[44,45] 20 世纪90 年代中期,Aaske Plaat 提出了一种新的搜索体系——Memory-enhanced Test(MT) 框架[45] 。MT 体系包含了一系列的算法,通过多次调用零窗口的Alpha-Beta 来实现搜索。通常 Alpha-Beta 搜索是以最宽的窗口开始,以保证结果不会落在窗外。而在 MT 体系中的空窗口搜 索时,结果必会掉在窗口外,返回一个上或者下边界。MT 体系在搜索的过程中逐渐向最终要 找的值逼近。MT 体系把不同的算法统一到一个体系下,让我们更容易看到了不同算法之间的 异同点,有利于我们深层次地理解算法。算法不同的地方在于调用空窗Alpha-Beta 算法时的参 数不同。算法的3个参数(n, first, next) 。其中N 表示根节点,first 是空窗Alpha-Beta 算法开始 7 四国军棋的人机博弈搜索算法研究 搜索的上边界,next 是搜索结束时把结果作为下一个边界。当算法的 3 个参数分别取 n, +∞, * * bound=g 时,也称为MT-SSS 算法。MT-SSS 算法通过多次调用零窗口的Alpha-Beta 算法,来实 * * 现SSS 的搜索。它搜索的叶子节点数和SSS 相等,且花费更少的内存。而且通过调用Alpha-Beta 算法的方式实现最优优先访问,让人更容易理解。当 MT 算法的 3 个参数取 n,- ∞,bound=g+1 * [45] [45] 时,称为MT-DUAL 算法 。当然,MTD 算法由于参数的取值不同,还有很多其他算法 。由于 MT 算法的高性能,它广泛应用于许多博弈程序中。 6 .搜索算法其他方面的改进 一直以来,讨论的Alpha-Beta 及其该进算法搜索的深度都必须是固定的,这也是Alpha-Beta 算法一个很大的问题[46] 。人们希望根据具体情况有些分支搜索得比较深,有些分支搜索得比较 浅。20 世纪80 年代初期Berliner 提出了一种更类似于人类思维的搜索算法B*[46,47] ,实现了好 的走法搜索得比较深,坏的走法走得比较浅。80,90 年代有很多学者研究了B*算法的改进算法 [48~51] [48,52] ,其中有些算法取得了很好的效果 。 1995 年,Korf 和 Chickering 针对不同深度的博弈树搜索提出了一种新的算法,Best-First [53,54] * Minimax Search(BFMMS) 。BFMMS 是一种最佳优先算法,但它搜索的方式和SSS 算法很 不一样。BFMMS 可用于不同深度博弈树的搜索,SSS*则用于固定深度的搜索。 博弈程序中使用搜索算法的效果依赖于评价函数返回的值是否可靠。如果返回的评估值是 不可靠的,则搜索算法所选取的走法不一定是好的着法。但在不完全信息游戏中,很多信息是 不确定的,所以要引进新的理论和解决方法。20 世纪80 年代中后期,Palay 在B*算法中引进了 * [55] [56] 概率分布,创造一种新的算法PB 算法 。1995 年,Junghanns 在搜索算法中运用了模糊理论。 M.L.Ginsberg 引入分区搜索技术和蒙特卡罗随机抽样等方法到桥牌程序GIB[57] 中,使得该程序 所向披靡地赢得了2000 年计算机奥林匹克桥牌比赛的冠军。2002 年,D.Billings 等设计的德克 扑克程序POKI[58]在对手建模上采用统计学习的方法,目前其智能水平达到了职业中级。 1.3 本文主要工作和结构 本文重点研究四国军棋人机博弈的搜索算法,并且通过实验比较各算法的性能。首先我们 针对四国军棋开局中博弈树分支多,模糊度大的特点,提出了基于定时器的期望搜索算法 (Aspiration with Timer:简称 AWT)。AWT 算法利用定时器动态调整窗口来提高搜索效率,快 速找到次优解使游戏进入中局。它以较小的额外内存消耗换取了快速的搜索效率。实验结果表 明AWT 算法能够有效应用到不完全信息四国军棋人机博弈中。 其次,我们针对四国军棋的不完全信息性,使用信息论中信息熵的概念来标示不确定性。 提出Alpha-Beta-Threhold 算法,使用不同分支的路径熵来控制搜索的深度,在确定的分支搜 索深一些,在不确定的分支搜索浅一些。实验比较Alpha-Beta 算法和Alpha-Beta-Threshold 算法的性能。为了改进Alpha-Beta-Threshold 算法性能,又提出了改进算法Certain-Threshold 8 南京航空航天大学硕士学位论文 算法和Best-Certain-Threshold 算法。同时访问不同规模的随机树和四国军棋博弈树,从访问 的节点数和内存的消耗两方面来比较 Alpha-Beta ,Alpha-Beta-Threshold , Certain-Threshold,Best-Certain-Threshold 算法的性能。 本文的组织结构如下: 第一章:主要概述了四国军棋的特点和研究关键点,以及搜索算法的发展历史以及分类, 最后总结了本文的主要工作和结构。 第二章:围绕Alpha-Beta 基准算法和及其改进算法——Aspiration 算法和PVS 算法的思想 展开分析和讨论,并对各算法性能进行比较与分析。介绍完全信息下的搜索算法 SSS*算法和 MT-SSS*算法,详细描述各算法的思想,通过实验来分析和比较这几个算法的性能。 第三章:重点介绍 AWT 算法的思想,论证了算法的高效性和可靠性,并详细叙述了四国 系统中AWT 算法参数选取问题。通过实验比较AWT 算法与Alpha-Beta 算法,Aspiration 算法 在时间效率(访问节点)和内存消耗两方面的性能以及AWT 算法中的缩小参数M 、N 对于算法搜 索到的次优值的影响。 第四章:根据四国军棋的不完全信息的特性,提出了Alpha-Beta-threshold 算法,实现了动 态调整搜索深度的思想,在确定度高的分支搜索深一些,在确定度低的分支搜索浅一些。实验 比较Alpha-Beta 算法和Alpha-Beta-Threshold 算法性能。针对Alpha-Beta-Threshold 算法性能和 节点的排列顺序相关,提出了 Certain-Threshold 算法,并从访问节点数和内存消耗两方面来比 较Alpha-Beta ,Alpha-Beta-Threshold ,Certain-Threshold 三种算法的性能。整合静态估值和路径 熵两个因素,重新定义PAYOFF ,提出了Best-Certain-Threshold 算法。实验比较Alpha-Beta , Alpha-Beta-Threshold 算法,Certain-Threshold 算法,Best-Certain-Threshold 算法性能。 第五章:总结本文的工作,并给出下一步工作的展望。 9 四国军棋的人机博弈搜索算法研究 第二章 经典搜索算法 本章首先概述搜索算法的基础极大极小算法,简介深度优先的Alpha-Beta 算法及其改进算 * * 法、Aspiration 算法、PVS 等算法。然后介绍最佳优先搜索算法,如SSS 算法和MT-SSS 算法 思想。最后本章通过大量实验分析与比较上述算法的性能并作出详细的评价。 2.1 极大极小算法思想 根据人机博弈的过程,我们可以构建一棵博弈树,将所有的走法罗列出来。将机器面临的 局面作为这棵树的根节点,将机器可以走的着法走后而生成的局面作为根节点的子节点。想象 对手针对新生成的局面可以走的每一种可能,作为当前节点的子节点……这样就构建了一颗博 弈树。 MAX WIN MIN LOSS LOSS WIN MAX LOSS WIN LOSS WIN MIN WIN WIN 图 2.1 井字棋 以井字棋为例,图2.1 中的每一个节点代表一个棋盘。假设玩家有两方,一方为MAX ,一 方为MIN ,我们站在MAX 的立场考虑问题。X 代表MAX 要走的棋,O 代表MIN 要走的棋.现 在我们要考虑的是对于现在的棋局Max 走哪一步是对它最有利的.当轮到MAX 要走的棋时, 列出MAX 所有可行的走法;当轮到MIN 要走的棋时,列出MIN 所有可行的走法。分出输赢 的节点作为叶子节点,用WIN ,LOSS 来表示。图2.1 就为井子棋生成的博弈树。 10 南京航空航天大学硕士学位论文 Float Minimax(n) { if(n-Flag==Leaf) g=eval(n); else if(n-Flag==MAX) { g=-∞; child=firstchild(n); while(child≠⊥) { g=max(g,Minimax(child)); child=nextbrother(child); } } else if(n-Flag=MIN) { g=+∞; child=firstchild(n); while(child≠⊥) { g=min(g,Minimax(child)); child=nextbrother(child); } } return g; } 图 2.2 Minimax 伪代码 人机博弈的目的是根据当前局面为机器找到一个好的走法。设MAX 为机器方面临局面, MIN 为对手所面临的局面。为了找到当前的最优行动方案,需要对各个可能的方案所产生的后 果进行比较,就是说要考虑每一方案实施后对方可能采取的所有行动,并计算可能的得分。计 算得分,需要根据估价函数估算当前博弈树端节点的得分。子节点的估值计算出来后,再推算 出父节点的得分,推算的方法是:对MAX 节点,要在可供选择的方案中选一个对自己最有利 的方案,所以选其子节点中一个最大的得分作为自己的得分;对MIN 节点,选其子节点中一个 最小的得分作为父节点的得分。如果一个着法能获得较大的倒推值,则它就是当前最好的行动 方案。这就是极大极小算法的基本思想。图2.2 是极大极小算法的伪代码。 以图2.1 的井字棋为例,将博弈树转化成极大极小树,如图2.3 所示。设评价函数,-1,+1 分别表示MAX 方的输和嬴,根据极大极小原理,从叶子节点推出父节点的值,父节点的值为 +1 。而b 节点的走法就是最好的走法。 11 四国军棋的人机博弈搜索算法研究 图 2.3 井子棋的极大极小搜索 在博弈问题中,每一个格局可供选择的行动方案都有很多,因此会生成十分庞大的博弈树。 搜索的时间耗费会根据搜索层数的增加而急剧增加。试图利用完整的博弈树来进行极小极大分 析是困难的。可行的办法是只生成一定深度的博弈树,然后进行极小极大分析,找出当前最好的 行动方案。 极大极小算法是博弈算法的基础。但极大极小算法的搜索也存在一些冗余。如图2.3 ,当搜 索扩展到b 节点,我们可以看到,b 节点是个叶子节点,它的值为+1 。根据极大极小原理,根 节点 a 的值取孩子节点的最大值;根据井子棋评价函数,只能得到两种结果 [-1 ,+1] ,+1 已经 是a 节点可获得的最大值。搜索可以结束,因为后面的搜索不会对结果产生任何影响。所以, 极大极小搜索中有些搜索是不必要的。 2.2 Alpha-Beta 及其改进算法 2.2.1 Alpha-Beta 算法 Alpha-Beta 算法[10~15] 的基本思想是,边生成博弈树,边评估各节点的倒推值,并且根据评 估出的倒推值范围,及时停止扩展那些没有必要再扩展的子节点,即相当于剪去了博弈树上的 一些分枝,从而节约了机器开销,提高了搜索效率[4] 。具体的剪枝方法如下: (1) 对于一个MIN ,若能估计出其倒推值的上确界Beta ,并且这个Beta 值不大于 MIN 的 父节点(一定是或节点) 的估计倒推值的下确界Alpha ,即Alpha≥Beta ,则就不必再扩展该MIN 节点的其余子节点了。这一过程称为Alpha 剪枝。 (2) 对于一个或节点MAX ,若能估计出其倒推值的下确界Alpha ,并且这个Beta 值不小于 MAX 的父节点(一定是与节点) 的估计倒推值的上确界Beta ,即Alpha≥Beta ,则就不必再扩展该 MAX 节点的其余子节点了。这一过程称为Beta 剪枝。 12 南京航空航天大学硕士学位论文 A B C 18 D E F 16 图 2.4 Alpha 剪枝 图 2.5 Beta 剪枝 例如:图2.4 中,节点 D 的值为 16 ,C 是MIN 节点,取孩子节点的最小值,由此可以判 断节点 C 的值将小于等于 16 ;而节点 B 的值为18,节点A 是MAX 节点,取孩子节点的最 大值,A 的值将大于等于18,这样就不用再考虑C 的其他孩子E 、F ,这种将节点 D 的后继兄 弟节点减去的情况称为 Alpha 剪枝。 图2.5 中,节点 D 的估值为18,C 是MAX 节点,取孩子节点的最大值,由此可以判断节 点 C 的值将大于等于 18 ;节点B 的值为8,而节点 A 为MIN 节点,取孩子节点的最小值, A 的值小于等于 8 。也就是说不再需要考虑节点 C 的其他子节点 E 、F 。这种将节点 D 的后 继兄弟节点减去的情况称为 Beta 剪枝。图2.6 是Alpha-Beta 算法的伪代码。 Alpha-Beta 搜索能够省略许多节点的搜索。对于每一个被省略的非叶子节点来说,这都意 味着不仅节点本身,而且节点下面的子树也被省略掉了。这导致 Alpha-Beta 搜索需要遍历的节 点远远少于极大极小算法所遍历的节点。这也意味着,Alpha-Beta 搜索所花费的时间远远少于 极大极小算法所花费的时间。 Alpha-Beta 搜索由于过程简单、容易理解、且占用空间小等优良特点被广泛应用,成为现 在主流的搜索算法的基础。但是它也有缺点,即它对于节点的排列非常敏感。对于同一层上的 节点,如果排列合适,剪枝效率就很高,可以使实际搜索的博弈树达到最小树。所谓最小树就 是一经向下搜索,第一个节点就是要寻找的走步。但是如果节点的排列顺序恰好是从最差到最 好,就可能使剪枝一直无法进行,从而实际上搜索了整棵的极大极小树。 13 四国军棋的人机博弈搜索算法研究 图 2.6 Alpha-Beta 伪代码 2.2.2 Aspiration 算法 在Alpha-Beta 剪枝过程中,初始的搜索窗口往往是从-∞ (即初始的Alpha 值)到+∞ (初始 的Beta 值),在搜索过程中再不断缩小窗口,加大剪枝效果。 Aspiration 算法[16~18]根据经验猜测一个值,然后在这个值的附近生成一个窗口,用这个窗 口代替(-∞,+∞)搜索。假定我们猜测搜索的结果在 x 附近,那我们可以令Alpha=x-window , Beta=x+window ,调用Value =Alpha-Beta (depth ,x-window ,x+window )来搜索结果。特别是 当window 很小的时候,搜索的效率会比较高,因为有了更多的剪枝。 这样可能得到的结果有三种: 1.返回的值 Value 落在(x-window ,x+window )区间内。在这种情况下,我们知道要找的 值就在猜测的范围之内,可以直接找到最佳的着法。 2.返回的值Value=x+window 。在这种情况下,我们也知道要找的值大于等于x+window , 但是不知道它的精确值是多少。此时需要重新用Alpha-Beta (depth ,value ,+∞)再次搜索。 3.返回的值 Value=x-window 。调用Alpha-Beta (depth ,-∞,value )重新搜索。 14 南京航空航天大学硕士学位论文 图2.7 是Aspiration 算法的伪代码。 Float Aspiration(n,estimate,delta) { Alpha = estimate-delta; Beta = estimate+delta; g = Alpha-Beta(n,Alpha,Beta); if( g=Alpha) g=Alpha-Beta(n,-∞,g); else if ( g=Beta ) g=Alpha-Beta(n,g,+∞); return g; } 图 2.7 Aspiration 算法伪代码 虽然当第一次猜测命中的时候,搜索的时间大大缩短了,但由于会出现 2 种失败的情形, 引发的重新搜索会使搜索时间上的优势丧失。显然,如何准确猜测是渴望搜索提高效率的一个 重要问题。 2.2.3 PVS 算法 PVS 算法[17~20]基于如下假设:假定第 1 步是最佳的移动,其后继则次之,直到另一节点 被证明是最佳的。在一个中间节点,其第一个分枝以一个完整窗口(Alpha ,Beta )搜索之并产 生一个位于该窗中的值 v ,后继的分枝则以一个极小的窗口(v ,v+1 )搜索之。如果猜测不准 确,则返回值落在窗口之外。如果返回值比v+1 大,随后就需以(v+1 ,Beta )为窗口重新搜索; [7] 如果返回值比v+1 小,则说明这个节点不如已有的最佳节点,就不必再搜索了 。 算法假设的是第一步是最佳的移动,后面的节点使用零窗口搜索会产生很多的剪枝。但如 果第一步的移动不好,后面的节点就要用正常窗口重新搜索,但这时的窗口也缩小了,其搜索 效率也比以完整窗口进行的搜索高。图2.8 是PVS 算法的伪代码。 PVS 与深度迭代,置换表一起用,效果会比较好。最常用最简单的深度迭代是指以d-1 层 搜索出的最佳走法作为d 层搜索的最先搜索的分支,这样可以一定程度上保证第一步是好的移 动。 15 四国军棋的人机博弈搜索算法研究 Float PVS(n,Alpha,Beta) { if(n-Flag==Leaf) return eval(n); child = firstchild(n); g = PVS(c,Alpha,Beta); child = nextbrother(child); if(n-Flag==MAX){ g = max(g,Alpha); while(gBeta and child≠⊥){ t=PVS(child,g,g+1); if(tg and tbeta) g = PVS(child,t,Beta); g = max(g,t); child=nextbrother(child); } } else{ g = min(g,Beta); while(gAlpha and child≠⊥){ t=PVS(child,g-1,g); if(tg and tAlpha) g=PVS(child,Alpha,t); g=min(g,t); child=nextbrother(child); } } return g; } 图 2.8 PVS 算法的伪代码 2.2.4 实验分析比较 我们在实验中分别建立6 层6 分支,7 分支,8 分支,9 分支以及7 层7 分支的博弈树。博 弈树节点的估值随机产生。将博弈树存入文件中,然后使用Alpha-Beta ,Aspiration ,PVS 算法 搜索这些树,从访问节点数以及内存消耗两个方面比较它们的性能。算法所访问的叶子节点数 反映了算法时间上的消耗。算法搜索的节点少,则搜索的时间就会比较少,也意味着该算法在 单位时间内能搜索更多的节点。内存消耗比较时,比较算法所用的最大内存。因为每个算法搜 索之前先从文件中读出树节点的信息建立一棵树,建树花去很大的内存,使得各算法花费的内 存差距很难看出。因此在以后的比较中各算法首先减去建树所花的内存再比较。访问节点数以 及内存消耗的比较是评价搜索算法性能的常用方法。 Alpha-Beta, Aspiration, PVS 算法所访问的叶子节点数如图2.9 所示。搜索前两种规模的树, PVS 所访问的节点数高于 Alpha-Beta,Aspiration 两种算法,但在后三种规模的树上都低于 Alpha-Beta,Aspiration 两种算法。随着树的规模增大,PVS 显示出比较好的性能。Aspiration 所 16 南京航空航天大学硕士学位论文 表现的性能和基本的Alpha-Beta 算法相近,可能的原因是:在程序中所用的猜测值是随机产生 的,从前面分析可知,Aspiration 的性能和猜测值是否准确非常有关系。在实际系统中,我们可 以多次实验,通过统计学的相关知识获得一个比较准确的猜测值。 4 x 10 5 4.5 4 3.5 s e d o Alpha-Beta n d 3 Aspiration e t i PVS s i v f o r 2.5 e b m u n 2 1.5 1 0.5 0 1 2 3 4 5 6 7 8 9 number of game tree node x 105 图 2.9 Alpha-Beta, Aspiration, PVS 算法所访问的叶子节点数 5 x 10 4 Alpha-Beta Aspiration PVS 3.5 3 t s o c y r o m e m 2.5 2 1.5 0 1 2 3 4 5 6 7 8 9 number of game tree node x 105 图 2.10 Alpha-Beta, Aspiration, PVS 内存消耗比较 Alpha-Beta, Aspiration, PVS 算法内存消耗如图2.10 所示。随着树的规模的增大,各算法所 花的内存也相应增多。Alpha-Beta ,Aspiration ,PVS 三种算法所花费的内存所差无几。PVS 算 17 四国军棋的人机博弈搜索算法研究 法随着树的规模的增大,增长幅度有所下降。理论上讲,随着树的规模的增大,各算法所访问 的节点应增大。但我们可从图2.9 可看出, PVS 算法在后两棵树时却出现了相反的结果。这是 因为不同规模的树是随机产生的,因此叶子节点的值,以及叶子节点的分布也是随机的。搜索 算法跟所产生的具体的树很有关系。 * 2.3 SSS 及其相关算法 * 2.3.1 SSS 算法 * [27] G.G.Stockman 于1979 年提出了SSS 算法 ,同前面提到的Alpha-Beta 算法以及它的改进 算法完全不同。SSS*算法[28~39]是一种最佳优先搜索算法,把对极大极小树的搜索看成是状态图 的搜索,在不同的分支上展开多条路径,并维护一张关于状态图的全局信息表。相比于 Alpha-Beta 算法,奇特之处在于,SSS*搜索过程中最有希望的节点被最先展开,而不是向深度 [8] 优先或广度优先那样有一个较高固定的搜索方向 。 所谓最佳是相对而言的,如图2.11 所示:对于这样一棵树,x, y 两个节点谁更好呢,d 是 叶子节点,它的值为2 ,b 是MIN 节点,取孩子节点的最小值,所以b 的值小于等于2 ,同样, c 的值小于等于 9 。如果首先访问y 节点,如果y 的值大于等于2,则可不必访问x 节点直接可 以求出a 节点的最大最小值;如果y 的值小于2 ,则需访问x 节点才能求出a 节点的值。如果 首先访问x 节点,那么无论x 的值是什么,都要访问y 节点,才能得出a 的值。这样说来,如 果先访问y 节点就有可能剪掉x 节点,所以y 节点更佳。 a b c d x e y 2 9 图 2.11 更优的节点 在SSS*算法里要引入状态这一概念,定义搜索的状态(state )S = (n ,s,h ),其中 n 表 明当前状态是哪一个节点的;s 是指节点的状态( status )的标记,s 的值是 LIVE 或 SOLVED , LIVE 表明当前节点尚未展开,SOLVED 则表明当前节点已遍历过了,并求出了确切值 h ;h 是 当前节点的值。包含有上述内容的结构S 叫做状态描述符。在算法开始执行前,建立一个堆栈 [8] 来容纳上述状态描述符,这称为OPEN 队列 。 Stockman 的SSS*算法规则库如表2.1 所示: 18 南京航空航天大学硕士学位论文 1.将根节点的状态(root ,LIVE ,+∞)放进 OPEN 队列顶部。 2.将 OPEN 队列顶部的状态 p = (n ,s,h )取出(POP ,即取出的同时从队列中删去)。 3.状态 p 当中,如果 n 是根节点,并且 s 的值为 SOLVED ,则 p 就是搜索的目标状 态,h 就是求出的根节点的值,搜索结束。否则继续。 4.应用状态空间操作的规则集展开 p ,将输出到 OPEN 队列中的状态按 h 从大到小排 列,h 最大的在栈顶。清除 OPEN 队列中多余的状态。状态空间操作的规则集的说明 在下面的表格中。 5.转到2 继续。 * 表 2.1 SSS 规则库 序号 输入状态p 的条件

http://oodlesalootle.com/sousuoboyishu/113.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有