|
- 解剖大象的眼睛——中国象棋程序设计探索
-
- 黄晨 * 2005年6月
-
- (五) 克服水平线效应
-
-
- 5.1 裁剪算法概述
-
- 狭义上的裁剪算法属于申朗的B策略,在象棋程序中用得并不多,主要还是90年代提出的空着裁剪。国际象棋程序DarkThought中使用了“AEL裁剪”(AEL Pruning)算法,其中A是改进的空着裁剪,而吸引人的是E和L部分,为此ElephantEye尝试了这两部分的裁剪,虽然并未大幅度提高搜索效率,但笔者体会不少。
- 著名中国象棋软件《象棋世家》的作者郑明政认为,将AEL算法从国际象棋移植到中国象棋的时候必须格外小心,还列举了算法的三个负面作用:
- (1) A——适应性空着裁剪(Adaptive Null-Move Pruning),要小心停着杀和连停着杀,这是由于空着裁剪的不适合无等着局面的本质所致;
- (2) E——延伸的无效路线裁剪(Extended Futility Pruning),要小心死子不急吃的问题,因为不吃子的线路表面上是无效线路,因此裁剪后剩下的深度就不足以看到死子不急吃的局面了。
- (3) L——限制性修剪(Limited Razoring),要小心弃子杀和弃多子杀,因为子力落后的线路作了修剪,从而无法预测到后面存在的杀局。
- 明白了产生这三个负面作用的原因,也就理解了AEL算法的本质,稍后笔者将介绍如何在运用裁剪技术的时候避免产生负面作用,其中一个重要的手段就是选择性延伸。延伸的处理手法正好跟裁剪相反,但起到的作用却与裁剪相同,因此也是本章的主题之一。
-
- 谈到裁剪算法,就不得不提到局面的评价问题,因为很多大多数裁剪方法都是建立在评价局面的基础上的。例如空着裁剪在残局中应该自动禁用,这就涉及到残局界定的问题,又如无效路线裁剪要涉及到无效路线如何界定的问题,限制性修剪需要涉及到界定子力落后的问题,这些问题都和局面评价有关。
- 例如,ElephantEye只会评价子力价值,把一个轻子(马或炮)的价值定为100左右,因此裁剪条件的界定都和这个值有关。当程序重写时,轻子价值改变了,裁剪条件也必须作相应的改变。
-
- 5.2 带检验的适应性空着裁剪
- “适应性空着裁剪”(Adaptive Null-Move Pruning)指的是根据不同情况来调整R值(裁剪深度)的算法,它首先由国际象棋程序DarkThought的作者Ernst Heinz发表在1999年的ICCA杂志上(参阅Heinz EA: Adaptive Null-Move Pruning, ICCA J. 22 (3): 123-132, 1999,可从互联网上找到)。其内容可以概括为:
- (1) 深度小于或等于6时,用R = 2的空着裁剪进行搜索;
- (2) 深度大于8时,用R = 3;
- (3) 深度是7或8时,如果每方棋子都大于或等于3个,则用 R = 3,否则用 R = 2。
- ElephantEye做空着裁剪时,也用了R = 26/83法则,但是ElephantEye并没有判断子数的功能,因此“每方棋子都大于或等于3个”改成了“每方子力价值总和大于3个轻子的价值”,因此确定R的函数是这样的:
-
- const int EndgameMargin = 320;
- int RAdapt(int Depth) {
- if (Depth <= 6) {
- return 2;
- } else if (Depth <= 8) {
- return Evalue[Red] < EndgameMargin || Evalue[Black] < EndgameMargin ? 2 : 3;
- } else {
- return 3;
- }
- }
-
- “带检验的空着裁剪”(Verified Null-Move Pruning)指的是检验空着裁剪是否安全的算法,它首先由Tabibi发表在2002年的ICGA(原ICCA)杂志上(参阅Tabibi OD, Netanyahu NS: Verified Null-Move Pruning, ICGA J. 25 (3): 153-161, 2002,可以从互联网上找到)。其内容可以概括为:
- (1) 用R = 3的空着裁剪进行搜索;
- (2) 如果高出边界,那么做浅一层的搜索(这就意味着一层的搜索是无法做带验证的空着裁剪的);
- (3) 做浅一层的搜索时,子结点用R = 3的不带验证的空着裁剪;
- (4) 如果浅一层的搜索高出边界,那么带验证的空着裁剪是成功的,否则必须重新做完全的搜索。
- 笔者认为这里存在很多问题:
- (1) 用R = 3非常冒进,改用适应性空着裁剪推荐的R = 26/83法则比较合适;
- (2) 检验时做浅一层的搜索太浪费时间,裁剪的层数可以跟空着裁剪一样的R值一样,而且窗口也用以Beta为界的零窗口;
- (3) 做检验时,子结点仍旧应该做带检验的空着裁剪,否则“连停着杀”就检测不出来了。
-
- ElephantEye是否启用空着裁剪,分三种情况讨论:
- (1) 我方子力超过3个轻子的价值,就使用不带检验的适应性空着裁剪;
- (2) 我方子力小于3个轻子的价值,但有进攻子力,则使用带检验的适应性空着裁剪;
- (3) 我方只有仕(士)相(象)等守子,则禁用空着裁剪。
- 因此,ElephantEye的代码中,和空着裁剪有关的部分如下:
-
- int AlphaBeta(int Alpha, int Beta, int Depth, int NullOkay) {
- ……
- if (NullOkay && !InCheck() && HaveAttackPieces()) {
- MakeNullMove();
- Value = -AlphaBeta(-Beta, 1 - Beta, Depth - 1 - RAdapt(Depth), 0);
- UndoMakeMove();
- if (Value >= Beta) {
- if (Evalue[Self] > EndgameMargin) {
- // 我方子力超过3个轻子的价值,空着裁剪不带检验
- return Value; // 如果不是高出边界的,则返回Beta,下同
- } else {
- // 我方子力小于3个轻子的价值,空着裁剪要带检验
- Value = AlphaBeta(Beta - 1, Beta, Depth - RAdapt(Depth), 0);
- if (Value >= Beta) {
- // 如果检验值高出边界,则检验成功,否则检验失败
- return Value;
- }
- }
- }
- }
- ……
- }
-
- 这个技术使得ElephantEye在残局中仍旧能启用空着裁剪,而且不会出现走错的情况,因此ElephantEye在几乎不带知识的情况下,残局的棋力还是非常高的。
-
- 5.3 无效路线裁剪
-
- “无效路线裁剪”(Futility Pruning)是不同于空着裁剪的另一种裁剪方法,它首先由Heinz发表在1998年的ICCA杂志上(参阅:Heinz EA: Extended Futility Pruning, ICCA J. 21(2): 75-83, 1998,可从互联网上找到),包括了AEL算法中的E和L两个部分,它们是基于同一个思想的:当局面相对于主要变例少许落后时,搜索深度可以裁剪一层,相当落后时,可以裁剪两层,大幅度落后时,可以裁剪三层。然而裁剪的这三个层次的手法是不同的,裁剪一层称为“选择性无效路线裁剪”(Selective Futility Pruning),裁剪两层称为“延伸的无效路线裁剪”(Extended Futility Pruning),裁剪三层称为“限制性修剪”(Limited Razoring)。
- 在国际象棋中,裁剪一层、两层和三层的条件分别界定为落后一个轻子、两个轻子和三个轻子,而没有文献为中国象棋给定一个数值。《象棋世家》的作者郑明政经过大量试验,认为落后一相(象)裁剪一层,落后一马裁剪两层,落后一车裁剪三层比较适合。ElephantEye由于没有做试验,因此用得比较保守:
-
- const int SelFutMargin = 80; // 不到一个马
- const int ExtFutMargin = 160; // 不到一个车
- const int RazorMargin = 240; // 超过一个车
-
- 尽管裁剪一层、两层和三层在思路上是一致的,但具体操作和界定上有明显的差别,看下面的代码:
-
- int AlphaBeta(int Alpha, int Beta, int Depth) {
- ……
- FutPrune = 0;
- // a. 在与叶子结点差三层的结点上,采用限制性修剪
- if (Depth == 3 && !Extended && Evaluation() + RazorMargin <= Alpha &&
- Evalue[Opponent] > EndgameMargin) {
- Depth = 2;
- }
- // b. 在与叶子结点差两层的结点上,采用延伸的无效路线裁剪
- if (Depth == 2 && !Extended) {
- Value = Evaluation() + ExtFutMargin;
- if (Value <= Alpha) {
- FutPrune = 1;
- BestValue = Value;
- FutMargin = ExtFutMargin;
- }
- }
- // c. 在与叶子结点差一层的结点上,采用选择性无效路线裁剪
- if (Depth == 1 && !InCheck) {
- Value = Evaluation() + SelFutMargin;
- if (Value <= Alpha) {
- FutPrune = 1;
- BestValue = Value;
- FutMargin = SelFutMargin;
- }
- }
- // 随后逐一检查每个合理着法
- ……
- }
-
- 在操作上可以很明显地看出,裁剪三层和两层的做法是截然不同的,裁剪三层就把即将搜索的深度减去1,它正好和“延伸”(Extension)相反,因此称为“修剪”(Razoring)。对于修剪或裁剪的条件,三层比两层苛刻得多,两层比一层又苛刻得多,这不仅体现在子力上,还有其他因素:裁剪一层只需要当前局面不被将军即可,而裁剪两层需要当前局面没有延伸,这自然包括了不被将军,另外还不能符合兑子或其他延伸条件;另外,裁剪三层要看对方子力有多少,如果处于残局则不适宜做修剪。
- 裁剪两层和一层时,都设置FutPrune这个变量,表明该结点可以实施裁剪。但究竟是否能够裁剪,还需要视该结点的每个着法而定,看随后的代码:
-
- int AlphaBeta(int Alpha, int Beta, int Depth) {
- ……
- // 先判断是否能做修剪或裁剪
- GenMoves();
- while(MovesLeft()) {
- MakeNextMove();
- if (FutPrune && FutMargin - Evaluation() <= Alpha && !InCheck()) {
- UndoMakeMove();
- } else {
- Value = -AlphaBeta(-Beta, -Alpha, Depth - 1);
- UndoMakeMove();
- ……
- }
- }
- ……
- }
-
- 我们注意到,进行裁剪要符合三个条件:(1) 前面已经判断过该结点能做裁剪;(2) 对手走完后,子力仍旧要符合裁剪的条件;(3) 对手的着法不能带将军。值得注意的是,这三个条件对于限制性修剪是无效的,如果符合条件,则可以裁剪三层(因为满足限制性修剪条件的结点也一定设置了FutPrune),否则还需要做两层搜索(即只裁剪了一层),因此有算不到弃子杀的风险。
- 最后要说明的是,无效路线裁剪和限制性修剪在ElephantEye中效果并不好,可能是E和L的条件设得比较保守的缘故。另外,裁剪一层的条件最宽松,尽管它使ElephantEye搜索的结点数减少了,但速度并未提高,因为被裁剪结点的每个着法还是走了(ElephantEye在运行过程中,绝大部分时间花在生成和执行着法上),因此裁剪掉的部分只是叶子结点上静态搜索的部分。
-
- 5.4 其他可以考虑的裁剪方法
-
- 裁剪算法并非只有上面所说的几种,如果程序设计师思路开阔,就可以想出很多裁剪策略。例如根据无效路线裁剪的“裁剪一层、两层和三层”的思路,笔者设计出一套形式上和空着裁剪类似的方案:
-
- int AlphaBeta(int Alpha, int Beta, int Depth) {
- ……
- // 前面是尝试空着裁剪
- // a. 尝试裁剪三层,类似限制性修剪,用RazorMargin
- Value = AlphaBeta(Beta + RazorMargin - 1, Beta + RazorMargin, Depth - 3);
- if (Value >= Beta + RazorMargin) {
- return Value; // 如果不是高出边界的,则返回Beta,下同
- }
- // b. 尝试裁剪两层,类似延伸的无效线路裁剪,用ExtFutMargin
- Value = AlphaBeta(Beta + ExtFutMargin - 1, Beta + ExtFutMargin, Depth - 2);
- if (Value >= Beta + ExtFutMargin) {
- return Value;
- }
- // c. 尝试裁剪一层,类似选择性无效线路裁剪,用SelFutMargin
- Value = AlphaBeta(Beta + SelFutMargin - 1, Beta + SelFutMargin, Depth - 1);
- if (Value >= Beta + SelFutMargin) {
- return Value;
- }
- // 后面是搜索全部着法
- ……
- }
-
- ElephantEye没有使用这套方案。裁剪方案是否有效,除了要通过大量测试来证明外,还要在实战中检测效果。因此任何裁剪方案若要上升到理论的高度,都不是很简单的。
-
- 5.5 静态搜索
-
- 静态搜索尽管实现起来比较简单,但是很多技术细节仍旧是需要考虑的,问题主要有以下几个:
- (1) 如果结点被将军,是否要产生全部着法。绝大多数程序都没有考虑结点被将军的情况,因为将军判断是很花费时间的。而ElephantEye在将军判断上有优势,因此在将军时产生全部的着法。因此有些多步连杀的排局,如果每步将军都吃子,那么ElephantEye只需要搜索1层就可以解出了,因此静态搜索中判断将军对于搜索杀棋是很有好处的。
- (2) 如何使用MVV/LVA启发。MVV/LVA是静态搜索最常用的启发方式,如果棋盘的数据结构精心设计,SEE也是值得尝试的。尽管MVV/LVA很简单,但是究竟根据“被吃子价值-攻击子价值”来排序,还是先排序“被吃子价值”,相同的情况再排序“攻击子价值”呢?这两种策略都很流行,ElephantEye使用后者。另外,MVV/LVA的子力价值越简单越好,ElephantEye已经简化到帅(将)4分,车3分,马炮2分,仕(士)相(象)兵(卒)1分的程度了。
- (3) 是否需要用其他搜索或启发方法。常规搜索中的很多搜索算法都不适合于静态搜索,这就是静态搜索简单的缘故。静态搜索本身就是空着启发的(第一个着法总是空着),但由于没有深度参数,所以不可能使用空着裁剪。另外,几乎所有的程序都不在静态搜索中使用置换表、PVS、杀手启发等算法。
- (4) 是否所有的吃子都需要考虑。如果搜索全部吃子着法,那么程序在叶子结点上花费的时间就非常浪费。ElephantEye在搜索所有吃子着法时,对着法作了过滤——吃不过河的兵和吃仕(士)相(象)的着法都不搜索了,尽管仕(士)和相(象)在ElephantEye的子力评价中分数很高(轻子价值的40%),但静态搜索本身就是对局面的粗略评价。
-
- 5.6 选择性延伸
-
- 常用的选择性延伸有这几种策略:(1) 将军延伸;(2) 单一应着延伸;(3) 杀棋威胁延伸;(4) 兑子延伸;(5) 通路兵挺进延伸。ElephantEye只考虑了将军延伸和兑子延伸,代码很简单:
-
- int AlphaBeta(int Alpha, int Beta, int Depth) {
- ……
- Extended = 0;
- if (InCheck()) {
- Depth ++;
- Extended = 1;
- } // 将军延伸
- if (!Extended && LastMove().IsGoodCap() && LastSecondMove().IsGoodCap()) {
- Depth ++;
- Extended = 1;
- } // 兑子延伸
- ……
- }
-
- 这里的兑子延伸策略是:遇到连续两个吃子着法就延伸一层,连续三个吃子着法就延伸两层,等等。这样,车换马炮的兑子就延伸了两层,而两次连续的简单兑子则延伸了三层,当然,这样做也并非不合理。
- ElephantEye之所以没有做杀棋威胁延伸,是因为在连杀排局中每着都有杀棋威胁,延伸层数太多会导致杀棋的求解速度慢很多。其代码实现起来并不困难,关键是利用空着裁剪:
-
- int AlphaBeta(int Alpha, int Beta, int Depth) {
- ……
- MakeNullMove();
- Value = -AlphaBeta(-Beta, 1 - Beta, Depth - 3);
- UndoMakeMove();
- if (Value >= Beta) {
- ……
- }
- if (!Extended && Value < MaxMoveNum - MaxValue) {
- Depth ++;
- Extended = 1;
- }
- ……
- }
-
- 做空着裁剪时,如果返回一个被杀的分值,则说明面临杀棋威胁,因此需要作延伸。如果程序没有将军判断的功能,只在帅(将)被吃时才返回被杀的分值,那么做空着裁剪就能发现被将军的局面,因此杀棋威胁延伸是包括将军延伸的。
- 为避免裁剪带来的负面作用,选择性延伸是的最有效的手段。在没有延伸的情况下,n回合以后的局面需要2n层搜索才能看到,而采用了将军延伸以后,n回合的连杀就可以在n回合内看到了。同样,如果兑子延伸能识别弃车破仕(士)、一马换双相(象)等手段,那么当这些路线因为子力落后而被裁剪的同时,也会因兑子而延伸,从而抵消了裁剪带来的负面作用。
|
|