您好、欢迎来到现金彩票网!
当前位置:秒速时时彩 > 搜索算法 >

中国象棋搜索算法优化

发布时间:2019-06-07 07:00 来源:未知 编辑:admin

  随着信息技术的不断发展和网络技术的不断普及,种 类繁多、迅速便捷的电脑娱乐已然成为人们日常生活中必不 可少的重要组成部分。在众多日常休闲娱乐活动中,电脑休 闲游戏凭借它的快捷性、益智性、互动性、简单性等众多优 点,成为第一选择。

  作为中华文化博大精深的代表之一,中国象棋不仅流 传久远,而且工具简单,操作方便,是一项很好的智力运 动,可丰富文化生活,陶冶情操,培养品格,开发智力,启 迪思维。下中国象棋时,红色方先走,黑色方后走,之后红 黑两方轮流走。当一方的将(帅)被对方的棋子吃掉,又或 者某一步之后将帅互相直接碰面,又或者是被困得已经无棋 可走时,即是对方赢棋。双方下棋时,为了打败对方,必须 仔细谨慎地思考对方的走法,多揣摩双方下面几步,这样棋 局才会更加精彩好看。双方斗智斗勇轮流走棋,称为博弈。

  极大极小算法始终站在博弈一方的立场上给棋局估值, 有利于本方的棋局给予一个较高的价值分数,不利于本方( 有利于对方)的给予一个较低的价值分数,双方优劣不明显 的局面则给予一个中间价值分数。在本方行棋的时候,选择 价值极大的子节点走棋,对方行棋则选择价值极小的子节点 走棋,这就是一个极大极小过程。为表述方便,我们将实行 极大值搜索的一方称为max方,另一方称为min方。Shannon 在1950年首先提出了极大极小算法,从而奠定了计算机博弈的理论基础。

  Alpha-Beta搜索:通过向子结点传递Alpha和Beta值,引 发剪枝,Alpha表示本方最优值,随着搜索不断变大,所以 开始一般取无穷大。Beta表示对方最坏值,随搜索不断变 小,初始时取正无穷大。剪枝的效率直接影响了Alpha-Beta 搜索效率,剪枝越多,效率越快。如果每个结点在搜索第一 个子结点时就产生剪枝,则搜索的结点数达到最小;如果剪 枝发生在每个结点的最后一个子结点上,则等同于没有剪 枝,搜索的结点数达到最大。

  静 态 着 法 启 发 是 指 不 依 赖 于 搜 索 结 果 的 着 法 排 序 方 式,即程序分析了某个局面后,不经过搜索,就大致应该知 道哪些着法应该首先尝试。在4种着法启发中,吃子启发是 静态着法启发,因为吃子着法数量不多,而且往往很多情况 能立刻得到实惠,所以需要首先考虑。而置换表启发、杀手 着法启发和历史表启发,都依赖于以前搜索的结果,因此属 于动态着法启发的范畴。

  3.2 置换表启发和低出(高出)边界的修正在置换表中保存一个着法,一方面可以利用置换表来

  获得主要变例,但最主要的作用是置换表启发。在探测置换 表时,尽管局面命中但深度没达到要求时,至少可以得到一 个着法,这个着法应该首先搜索,几乎所有的象棋程序都是 这么做的。哪些着法应该被保存到置换表中呢?实践证明, PV结点中的最佳着法,以及Beta结点中产生截断的着法,都 应该被保存到置换表中,而Alpha结点尽管也要保存,但不 需保存着法(置换表着法是空的),因为Alpha结点的每个着 法都返回Alpha值,我们不知道哪个着法是最好的。

  显然, 当探测置换表找到P V结点或Beta结点(但深度不够) 时, 就会有需要首先搜索的置换表着法。 那么, 找到Alpha结点时,是否还会有置换表着法呢?中国象棋程序“纵马奔流”采取了一个称为“低出(高出)边界的修正”策

  杀手着法启发(Killer Heuristic)基于这样一个思想,搜索 某个结点时首先尝试着法a1,由a1的后续着法b1产生截断, 回到原来的结点时再搜索a1的兄弟结点a2时,如果b1仍旧是 a2的后续着法,那么b1很有可能也会产生截断。

  采 用 杀 手 着 法 启 发 时 , 需 要 构 造 一 个 称 为 KillerMoves[MaxPly]的全局数组。搜索到深度为Ply的结点 时,首先尝试KillerMoves[Ply]的着法(前提是该着法在当前 局面下是合理的),搜索完这个结点时,把产生截断的着法 (如果有的话)记录到KillerMoves[Ply]。由此产生的效果,就 是当亲兄弟结点没有杀手着法时,会找到堂兄弟结点的杀手 着法。

  应用本文3.1节所提出的静态评价启发,结合置换表启 发和杀手启发,本文提出了一个较好的着法生成顺序,以取 代以往以棋子为主键的排列顺序。 如图1所示。

  使用启发式方法对着法顺序进行优化后,能大大减少 搜索的节点数,实验结果如表1所示,其中优化前的着法顺 序指的是以棋子为主键的排列顺序。从表中可以看出。随着 搜索深度的增加,优化的着法顺序所起的效用越来越大, 这 也验证了剪枝的效率与着法顺序高度相关。

  最初有一个思想,就是一开始只搜索一层,如果搜索的时间比分配的时间少,那么搜索两层,然后再搜索三层, 等等,直到你用完时间为止,这就是迭代的思想。内部迭代 加深优化着法顺序,内部迭代加深是指当对一个节点进行 深度为d(d相对较大)的搜索时,首先对其进行d-2的浅层搜 索,然后进行剪枝,找出一个最优的着法,然后继续进行搜 索,如果时间没有用完同样搜索到d-2层,否则在时间用完 后中断搜索。这会极大地提高搜索深度和效率。

  时间策略在各个象棋程序中差异很大,有的程序根本 没有时间策略,只能设定固定的搜索深度,或者在固定的 时间中止思考,例如中国象棋协议目前就没有时间策略。UCCI协议可以把时限规则告诉引擎,由引擎自动分配时间,时限规则可以是以下两种:

  不 管 处 理 哪 个 规 则 , 都 会 分 配 一 个 合 适 的 时 间

  是否能找到杀棋和搜索深度有关,某一深度下找不到 杀棋,但深一层搜索就可能找到;但和一般局面不同的是, 如果一定深度能找到杀棋,那么更深的深度会得到同样的结 果。因此,如果找到杀棋,那么程序要使用不同的策略。对 于处理杀棋局面,往往用到以下几个策略:

  (1) 置换表的存取策略,前面曾经介绍过,如果置换表中存储的某个局面已被确认找到杀棋,那么探测到这样的局

  (3) 给当前局面赋予一个分值区间(-WIN_VALUE, WIN_ VALUE),如果根结点的所有着法中,除了一个着法可以支 撑(即分值大于-WIN_VALUE)以外,其余着法都会输掉(即 分值都小于-WIN_VALUE),那么应该立即返回这个唯一着 法。另外如果某个根结点已经找到一个着法足够领先对手巨 大优势(即分值大于WIN_VALUE),其他的着法就不必继续搜 索下去,可以直接返回这个着法。

  针对中国象棋中的着法排列,本文将置换表着法、 静 态评价较优的着法和杀手着法排在前面,其余着法按历史得 分依次降序排在后面,从而得到了一个较好的着法生成顺 序,使游戏电脑更加智能,增加了游戏趣味性。

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