解剖大象的眼睛——中国象棋程序设计探索(五)：消除水平线效应

auntyellow 发表于 2005-6-14 22:59:00

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

页: [1]

华工象棋论坛's Archiver

解剖大象的眼睛——中国象棋程序设计探索(五)：消除水平线效应