中国象棋搜索算法优化

引言
     随着信息技术的不断发展和网络技术的不断普及，种 类繁多、迅速便捷的电脑娱乐已然成为人们日常生活中必不 可少的重要组成部分。在众多日常休闲娱乐活动中，电脑休 闲游戏凭借它的快捷性、益智性、互动性、简单性等众多优 点，成为第一选择。
作为中华文化博大精深的代表之一，中国象棋不仅流 传久远，而且工具简单，操作方便，是一项很好的智力运 动，可丰富文化生活，陶冶情操，培养品格，开发智力，启 迪思维。下中国象棋时，红色方先走，黑色方后走，之后红 黑两方轮流走。当一方的将（帅）被对方的棋子吃掉，又或 者某一步之后将帅互相直接碰面，又或者是被困得已经无棋 可走时，即是对方赢棋。双方下棋时，为了打败对方，必须 仔细谨慎地思考对方的走法，多揣摩双方下面几步，这样棋 局才会更加精彩好看。双方斗智斗勇轮流走棋，称为博弈。

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

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

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

图1  着法生成顺序
得到实惠”的 着 法 。 因此笔者用 了一个称为M V V (LVA ) 的策略，在 被 吃 子 有 保 护 的 情 况 下 ， 考 虑 M V V ( 被 吃 子 价 值 ) - L V A ( 攻 击 子 价 值 ) 的 值，而在被 吃子没保护 的情况下， 只考虑MVV 的值，然后 对 这 种 策 略 产 生 的M V V (LVA ) 值作排序， 并   选   择M V V (LVA )大于零的着法首先搜索。
3.2 置换表启发和低出(高出)边界的修正在置换表中保存一个着法，一方面可以利用置换表来
获得主要变例，但最主要的作用是置换表启发。在探测置换 表时，尽管局面命中但深度没达到要求时，至少可以得到一 个着法，这个着法应该首先搜索，几乎所有的象棋程序都是 这么做的。哪些着法应该被保存到置换表中呢？实践证明， PV结点中的最佳着法，以及Beta结点中产生截断的着法，都 应该被保存到置换表中，而Alpha结点尽管也要保存，但不 需保存着法(置换表着法是空的)，因为Alpha结点的每个着 法都返回Alpha值，我们不知道哪个着法是最好的。
显然， 当探测置换表找到P V结点或Beta结点(但深度不够) 时， 就会有需要首先搜索的置换表着法。 那么， 找到Alpha结点时，是否还会有置换表着法呢？中国象棋程序“纵马奔流”采取了一个称为“低出(高出)边界的修正”策
略，使得某些Alpha结点也存在置换表着法。
3.3 杀手着法启发
杀手着法启发(Killer Heuristic)基于这样一个思想，搜索 某个结点时首先尝试着法a1，由a1的后续着法b1产生截断， 回到原来的结点时再搜索a1的兄弟结点a2时，如果b1仍旧是 a2的后续着法，那么b1很有可能也会产生截断。
采 用 杀 手 着 法 启 发 时 ， 需 要 构 造 一 个 称 为 KillerMoves[MaxPly]的全局数组。搜索到深度为Ply的结点 时，首先尝试KillerMoves[Ply]的着法(前提是该着法在当前 局面下是合理的)，搜索完这个结点时，把产生截断的着法 (如果有的话)记录到KillerMoves[Ply]。由此产生的效果，就 是当亲兄弟结点没有杀手着法时，会找到堂兄弟结点的杀手 着法。
3.4  着法生成顺序
应用本文3.1节所提出的静态评价启发，结合置换表启 发和杀手启发，本文提出了一个较好的着法生成顺序，以取 代以往以棋子为主键的排列顺序。 如图1所示。
使用启发式方法对着法顺序进行优化后，能大大减少 搜索的节点数，实验结果如表1所示，其中优化前的着法顺 序指的是以棋子为主键的排列顺序。从表中可以看出。随着 搜索深度的增加，优化的着法顺序所起的效用越来越大, 这 也验证了剪枝的效率与着法顺序高度相关。

4 内部迭代加深和优化策略
4.1 迭代思想
最初有一个思想，就是一开始只搜索一层，如果搜索的时间比分配的时间少，那么搜索两层，然后再搜索三层， 等等，直到你用完时间为止，这就是迭代的思想。内部迭代 加深优化着法顺序，内部迭代加深是指当对一个节点进行 深度为d（d相对较大）的搜索时,首先对其进行d-2的浅层搜 索，然后进行剪枝，找出一个最优的着法，然后继续进行搜 索，如果时间没有用完同样搜索到d-2层，否则在时间用完 后中断搜索。这会极大地提高搜索深度和效率。
4.2  时间策略
时间策略在各个象棋程序中差异很大，有的程序根本 没有时间策略，只能设定固定的搜索深度，或者在固定的 时间中止思考，例如中国象棋协议目前就没有时间策略。UCCI协议可以把时限规则告诉引擎，由引擎自动分配时间，时限规则可以是以下两种：
(1) 时段制，即在限定时间内走完规定的步数。
(2) 加时制，即在限定时间内走完整盘棋，但每步会加 上几秒。
不 管 处 理 哪 个 规 则 ， 都 会 分 配 一 个 合 适 的 时 间
(ProperTime)用来走棋，这个时间是这样计算的：
(1) 时段制：分配时间 = 剩余时间 / 要走的步数；
(2) 加时制：分配时间 = 每步增加的时间 + 剩余时间 /
20 (即假设棋局会在20步内结束)；
4.3  杀棋策略
是否能找到杀棋和搜索深度有关，某一深度下找不到 杀棋，但深一层搜索就可能找到；但和一般局面不同的是， 如果一定深度能找到杀棋，那么更深的深度会得到同样的结 果。因此，如果找到杀棋，那么程序要使用不同的策略。对 于处理杀棋局面，往往用到以下几个策略：
(1) 置换表的存取策略，前面曾经介绍过，如果置换表中存储的某个局面已被确认找到杀棋，那么探测到这样的局
面时就不需要考虑深度条件。
(2) 根结点做迭代加深时，找到杀棋后搜索就立即停 止。
(3) 给当前局面赋予一个分值区间(-WIN_VALUE, WIN_ VALUE),如果根结点的所有着法中，除了一个着法可以支 撑(即分值大于-WIN_VALUE)以外，其余着法都会输掉(即 分值都小于-WIN_VALUE)，那么应该立即返回这个唯一着 法。另外如果某个根结点已经找到一个着法足够领先对手巨 大优势(即分值大于WIN_VALUE),其他的着法就不必继续搜 索下去，可以直接返回这个着法。

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