博弈树搜索算法在中国象棋中的应用

Posted by naxq  at 三月 1st, 2013

本文转载自：《计算机系统应用》2009年第9期

Application of Game Tree Search Algorithm in Computer Chinese Chess
岳金朋 冯 速 (北京师范大学 信息科学与技术学院 北京 100875)
摘 要： 针对中国象棋博弈中较为高效的α-β剪枝算法进行研究，以提升其效率。依据α-β剪枝算法的效率
与子节点扩展的排列顺序高度相关的事实及中国象棋自身的特点，从优化着法的排列顺序入手，设计
出启发能力较强的着法排列方案，并进一步提出扩大窗口的内部迭代加深算法对上述着法排列方案进
行修正，从而使着法顺序得到进一步的优化。实验数据表明，提出的方法可以明显提升α-β剪枝的
效率。
关键词： 中国象棋 α-β剪枝 着法顺序 内部迭代加深 扩大窗口
机器博弈是人工智能研究的重要分支，人类对机
器博弈的研究衍生了大量的研究成果。α-β剪枝是机
器博弈搜索中最为重要的算法之一。本文在研制中国
象棋博弈程序的过程中，设计了一个较为优化的着法
生成顺序，对于同一层数可以花费更少的搜索时间，
因此棋力更高。在此基础上，提出了一种扩大窗口的
内部迭代加深算法，对着法生成顺序做了进一步的优
化，从而使α-β剪枝的效率有了更大幅度的提高。在
着法生成顺序中，本文还提出了静态评价启发技术。
本文所使用的α-β剪枝的概念及相关的博弈树搜索
算法在文献[1]中有较详尽的介绍。
1 着法排列顺序的优化
α-β剪枝对着法顺序非常敏感[2]，所以采用启发
式方法对其进行优化是提高算法效率的关键所在。本
节参考国际象棋中已有的启发式方法，结合中国象棋
的实际情况，提出一个较好的着法排列方案，并通过
实验进行验证。在该方案中，我们使用置换表启发、
静态评价启发及动态启发等技术。
1.1 置换表启发
在搜索中，经常会在不同的路径上遇到相同的棋
局，这样的子树没有必要重复搜索，把最优着法、分
值、深度和节点类型等信息保存在一个称为置换表
① 基金项目:国家自然科学基金(60273015)
收稿时间:2009-01-09
(transposition table)[3,4]的数据结构中，再次遇到时
直接运用即可。
假设对某局面进行d 层搜索，窗口是[α,β]，而发
现该局面在置换表中已存在，其评价值为ν，类型为t，
深度为d’。当d’≥d 时，如果t 为精确型，便可直接返
回ν而代替搜索；如果t 为高出边界型且ν≥β，便可
进行剪枝。否则进行重新搜索以保证所取得数据的准
确，此时置换表中保存的最佳着法给了我们一定的启
发，它为搜索提供一个较优着法，该着法应排在前面优
先搜索，这使总体着法顺序得到一定程度的优化，置换
表的一个主要作用是它对着法顺序的启发[5,6]。
1.2 静态评价启发
静态评价启发(static evaluation heuristic)主要用
来优化吃子着法的顺序。对吃子着法进行静态评价启发，
就是要找出表面上占有较大优势的吃子着法。中国象棋
的主要攻击手段就是吃子，首先通过检测吃子来寻找最
优着法往往会产生较好的效果。如果我们用V 表示攻击
子的价值，用W 表示被吃子的价值(各个棋子的价值如
表1 所示)，那么某个吃子着法的价值U 可表示为：
(1)
V W
U
W



（被吃子有保护）
（被吃子无保护）
2009 年 第 9 期 计 算 机 系 统 应 用
Applied Technique 应用技术 141
表1 棋子的交换价值
帅(将) 车 马 炮 仕(士) 相(象) 兵(卒)
5 4 3 3 1 1 2
当吃子着法的值U＞0 时为表面上能得到获得很
大利益的着法，这样的着法往往是好的着法；U＝0 可
能是等价值的换子，这样的着法也值得一试；而U＜0
的着法往往是吃亏的。因此我们可将吃子着法依据U
进行排序，并对U≥0 的着法优先进行搜索。
1.3 动态启发
相对来说，对于中国象棋中的某一局面，U≥0 的吃
子着法是很少的，大多数着法都是U＜0 的吃子着法和
非吃子的着法。对于这些着法仅用1.2 节所述的静态评
价启发是不够的， 还要进行动态启发(dynamic
heuristic)。树搜索的过程，实际也是信息积累的过程。
对这些信息进行挖掘，可以得到我们所需要的启发信息。
国际象棋的经验表明，历史启发(history heuristic)[
7]和杀手启发(killer heuristic)[8]都是很好的动态
启发方法。历史启发的思想是：搜索树中某个节点上
的好着法，对于其他节点可能也是好的。所谓好着法
是指可以引发剪枝的着法，或者是其兄弟节点中最好
的着法[7]。一经遇到这样的着法，算法就给其历史得
分一个相应的增量，使其具有更高的优先搜索权，这
个增量通常为d2(d 为当前节点需要搜索的深度)或
2d。具体地说，就是设立一个90×90 的数组，红方
和黑方的着法都记录在这个数组中，前一个指标代表
起始格，后一个指标代表目标格；或者设立一个14
×90 的数组，红方着法和黑方着法分别记录，前一个
指标代表兵种，后一个指标代表目标格。历史启发是
从全局信息中获取优先准则的一种方法。对非吃子着
法和表面上不能立刻得到实惠的吃子着法根据其历史
得分进行排序，就能获得较佳的着法顺序。由于着法
的历史得分随搜索而改变，对节点的排列也会随之动
态改变。
杀手启发实际上是历史启发的特例。它是把同一
层中，引发剪枝最多的着法称为杀手，当下次搜索时，
搜索到同一层次，如果杀手是合法走步的话，就优先
搜索杀手。根据国际象棋的经验，杀手产生剪枝的可
能性很大，中国象棋也可以吸取这个经验。
1.4 着法生成顺序
应用1.2 节提出的方法，本节给出一个较好的着
法生成顺序，以取代以往以棋子为主键的排列顺序。
如图1 所示：
图1 着法生成顺序
使用启发式方法对着法顺序进行优化可以大大减
少搜索的节点数，实验结果如表2 所示(测试数据选自
文献[9]中有代表性的20 个中局盘面)，其中优化前的
着法顺序指的是以棋子为主键的排列顺序。从表中可
以看出，随着搜索深度的增加，优化的着法顺序所起
的效用越来越大，这也验证了剪枝的效率与着法顺序
是高度相关的。
表2 不同着法顺序搜索访问的平均节点数对比
搜索访问的平均节点数
搜索
深度 优化前的
着法顺序
优化后的
着法顺序
降低程度
（%）
1 40 40 0
2 670 450 -33
3 5198 2766 -47
4 31408 10882 -65
5 263397 65516 -75
6 1422290 240260 -83
7 11400735 1257174 -88
计 算 机 系 统 应 用 2009 年 第 9 期
142 应用技术 Applied Technique
值得指出的是，本文对杀手的位置进行了大量实
验，发现将杀手放在静态评价≥0 的吃子着法之后将
获得更高的剪枝效率。表3 对比了将杀手排在吃子着
法之前与之后搜索时访问的平均节点数(测试数据为
上述的20 个中局盘面)。从表中可以看出，杀手位置
的调整对于搜索效率的提升是较为明显的。
表3 杀手排在吃子着法之前与之后搜索访问的平均
节点数对比
搜索访问的平均节点数
搜索
深度 杀手排在吃子
着法之前
杀手排在吃子
着法之后
降低程度(%)
1 40 40 0
2 502 450 -10
3 3400 2766 -18
4 14115 10882 -23
5 87275 65516 -25
6 332417 240260 -28
7 1798713 1257174 -30
2 内部迭代加深
在1.1 节曾经指出，置换表可为搜索提供一个较
优的着法，从而优化总体着法顺序。然而，如果查找
置换表没有命中，我们如何一开始就能得到一个较优
的着法呢？这时可以利用内部迭代加深(internal
iterative deepening)[10,11]的办法。
2.1 内部迭代加深优化着法顺序
内部迭代加深是指当对一个节点进行深度为d 的
搜索时，先对该节点做一次深度为d－r 的搜索，一般
来说，d＞3，r＝2。利用d－r 的浅层搜索可以得到
一个较优的着法，这个着法将在深层搜索中放在第一
个位置优先尝试，同时，由于浅层搜索将在置换表、
历史表和杀手表中保存下有价值的信息，这将使深度
为d 的深层搜索获得更高的剪枝效率。
Knuth 和 Moore 的实验[2]表明利用α-β剪枝
搜索d 层所需时间大约是d－1 层所需时间的B1/2
倍，其中B 为平均分支因子数。如果中国象棋取B＝
40，每多搜一层就会花上原先的6 倍时间。所以，内
部迭代加深中深度为d－r的搜索大约是深度为d时的
1/6r，如果r＝2，则浅层搜索所花的时间仅为深层搜
索的1/36，其代价较小，但能够对深层搜索的着法顺
序产生重要指导。
2.2 扩大窗口的内部迭代加深
通过实践，本文发现内部迭代加深算法可能会产
生一个问题：那就是深度为d－r 的浅层搜索的返回值
并未落在窗口[α，β]的范围之内，而且也没有因为高
于窗口上界β而发生剪枝，而是低于窗口的下界α，
这种低出边界的搜索将导致浅层的启发信息不准确。
本文针对这一问题进行改进，将节点的窗口范围扩大
为[－∞，β]，进行低出边界的修正，形成了扩大窗口
的内部迭代加深(internal iterative deepening with
enlarged window，简称IIDEW)算法。如下所示：
1) 入口参数为(α，β，d)，[α，β]是初始窗口，
d 是搜索深度，函数名为AlphaBeta;
2) 若d＝0，则取静态估计值返回;
3) HashMove＝0;
4) ProbeHash(α，β，d，HashMove); // 查
找置换表
5) 若HashMove≠0，转10);
6) Score＝AlphaBeta (α，β，d－2);
7) 若Score＞α，转9);
8) Score＝AlphaBeta (－∞，β，d－2);
9) ProbeHash(α，β，d，HashMove); // 查
找置换表
10) 产生所有合理着法mi，1≤i≤n，并将
HashMove 排在第一个位置;
11) Best=－∞，HashFlag=“fail low”;
12) i＝1;
13) 执行着法mi;
14) Score＝－AlphaBeta (－β，－α，d－1);
15) 撤销着法mi
16) 若Score＞Best，则Best＝Score，否则，
转19);
17) 若Best＞α，则α＝Best，HashFlag=
“exact”;
18) 若Best≥β，则HashFlag=“fail high”，
转21);
19) i＝i＋1;
20) 若i≤n，则转13);
21) RecordHash(HashFlag，Best，d，mi); //
存入置换表
22) 取Best 值返回;
加入扩大窗口的内部迭代加深修正后，着法生成
2009 年 第 9 期 计 算 机 系 统 应 用
Applied Technique 应用技术 143
顺序如图2 所示：
图2 经扩大窗口的内部迭代加深调整后
的着法生成顺序
表4 对比了普通的和扩大窗口的内部迭代加深搜
索访问的平均节点数(测试数据同上述20 个中局盘
面)，从表中可以看出，扩大窗口的内部迭代加深在第
9 层时将搜索效率提高10%左右，并且随深度增加而
逐渐提高。
3 结论
针对中国象棋中的着法排列问题，本文将置换表
着法、静态评价较优的着法和杀手着法排在前面，其
余着法按历史得分依次降序排在后面，从而得到了一
个较好的着法生成顺序。实验数据表明上述优化在同
样的时间内使搜索时访问的平均节点数降低了一个数
量级。然后，通过内部迭代加深算法及其扩大窗口的
改进形式，对着法生成顺序做了进一步的优化。实验
数据表明扩大窗口的内部迭代加深算法能使剪枝效率
有10%左右的提升。因此，本文使用的着法生成顺序
对提高中国象棋博弈程序的效率有一定的作用。
表4 普通与扩大窗口内部迭代加深搜索
访问的平均节点数对比
搜索访问的平均节点数
搜索
深度 内部迭代加深+
α-β 剪枝
扩大窗口的内部迭代
加深+α-β 剪枝
降低程度
(%)
1 40 40 0
2 450 450 0
3 1734 1734 0
4 6405 6534 2
5 43822 42945 -2
6 151590 144010 -5
7 765856 712246 -7
8 2472578 2250045 -9
9 15662623 14096360 -10
参考文献
1 岳金朋,冯速.博弈树搜索算法概述.计算机系统应用,
2009,18(9):203－207.
2 Knuth DE, Moore RW. An analysis of Alpha-Beta
pruning. Artificial Intelligence, 1975,6(4):293－326.
3 Zobrist A. A new hashing method with application for
game playing. ICCA Journal, 1990,13(2):69－73.
4 Moreland B.Transposition table.2004/3. https://chessprogramming.
wikispaces.com/Transposition+Table.
5 Breuker DM, Uiterwijk JWHM, van den. Herik HJ.
Replacement schemes for transposition tables. ICCA
Journal, 1994,17(4):183－193.
6 Breuker DM, Uiterwijk JWHM, Herik HJ van den.
Replacement schemes and two-level tables. ICCA
Journal, 1994,19(3):175－180.
7 Schaeffer J. The history heuristic and Alpha-Beta
search enhancements in practice. IEEE Transactions on
Pattern Analysis and Machine Intelligence, 1989,11:
1203－1212.
8 Akl SG, Newborn MM. The principal continuation and
the killer heuristic. ACM Proceedings of ACM
National Conference. Seattle: ACM, 1977:466－473.
9 黄少龙.象棋中局精妙战法.北京:金盾出版社, 2005:
78－150.
10 Frayn C. Computer chess programming theory. 2006.
http://www.frayn.net/beowulf/theory.html
11 Moreland B. Interative deepening. 2004,3.
12 http://www.seanet.com/~brucemo/topics/iterative.htm.

0

0