- 《对弈程序基本技术》专题
-
- 获取主要变例
-
- Bruce Moreland / 文
-
- 要点
-
- 经常有人问，如何在搜索完成后提取主要变例。主要变例是程序认为的对双方来说都是最好的着法线路。它不会由未修改的“Alpha-Beta函数”来获得，所有的Alpha-Beta都只返回数值。
- 我们需要做的是对普通的Alpha-Beta搜索作修改，使得它能获取主要变例。修改的部分用醒目的颜色标出：
-
- typedef struct tagLINE {
- int cmove; //
路线中着法的数量；
- MOVE argmove[moveMAX]; // 路线。
- } LINE;
-
- int AlphaBeta(int depth, int alpha, int beta, LINE *pline) {
- LINE line;
- if (depth == 0) {
- pline->cmove = 0;
- return Evaluate();
- }
- GenerateLegalMoves();
- while (MovesLeft()) {
- MakeNextMove();
- val = -AlphaBeta(depth - 1, -beta, -alpha, &line);
- UnmakeMove();
- if (val >= beta) {
- return beta;
- }
- if (val > alpha) {
- alpha = val;
- pline->argmove[0] =
ThisMove();
- memcpy(pline->argmove +
1, line.argmove, line.cmove * sizeof(MOVE));
- pline->cmove = line.cmove
+ 1;
- }
- }
- return alpha;
- }
-
- 这个函数或许效率很低，因为它用到很多的堆栈空间，但是代码工作起来并不慢。有了这些改动后，如果函数返回Alpha和Beta之间的值，那么它不仅仅返回一个值，还包括能产生这个值的路线(一系列预测的着法)。这对于搜索树的任何结点都是有效的，包括根结点(它是最值得这么做的)。你可以这么来调用Alpha-Beta：
-
- val = AlphaBeta(depth, -INFINITY, INFINITY, &line);
-
- 你得到的是局面的值，以及在“line”这个存储区里保存的预测路线。“line”的数据结构是一个着法数组，以构成一个路线，另有一个整数来告诉你路线中有多少着法。
- 如果你用深度等于零去调用Alpha-Beta，那么这个函数只调用“Evaluate()”并返回它的值。一个着法也没搜索，因此一个着法也没选择，从而和分值一起返回的路线其长度为零。
- 如果你用某个深度调用这个搜索函数，那么你可以找到一个着法其值在Alpha和Beta之间，而你得到的不仅仅是分值，而且包括能产生这个值的一系列着法。为了在Alpha-Beta过程中建立路线，你拿出这个搜索到的着法，把它存入传递的路线存储区中【译注：即函数中的“*pline”】，并把局部的路线存储区【即函数中的“line”】也加到传递的存储区中。
- 你可能会问：“既然有传过来的路线存储区，为什么又要在每次递归的堆栈中新分配一个？”因为你在搜索树中找到一个局部的线路，那么原来的线路被推翻了，但你不能毁坏已经建立好的线路。如果你找到某个返回值在Alpha和Beta之间的结点，你就认为这个结点在搜索树的根结点的路线上，这是不对的。有很多零碎的主要变例是被丢弃的。
- 让你们感到惊讶的是，我在循环内用了“memcpy”这个函数【事实上这也是个循环，因此可能会认为它的效率很低】，它几乎不花时间，因为它很少被执行。
-
- 另一个思想
-
- 另一个一目了然的方法，就是在搜索值返回后，从主置换表中提取主要变例。置换表项中有一个区域存放这局面的最佳着法。由于每个PV结点都有一个值在Alpha和Beta之间，散列项中必定保存着“最佳着法”。
- 从置换表中提取主要变例，可以沿着散列项组成的链来提取，这就像吃馅饼一样简单。
- 我知道很多程序(包括一些专业程序)是这样做的，但是我没有试过。
- 【情况可能会比想象中的复杂，因为置换表中的数据会被覆盖，这样做就必须选择合适的覆盖策略。显然根结点是不会被覆盖的(它总是最后一个写入置换表)，因此至少能提取出一个着法(即程序要走的那步棋)，但是后续着法就很难保证了。深度优先的覆盖策略会比较有利，除此之外，也可以考虑PV结点优先的策略，因为PV结点的数量比Alpha结点和Beta结点少得多，所以这个覆盖策略对置换表不会产生很大的影响。
- 另外，直接从Alpha-Beta函数提取的主要变例，会因为置换表的运用而中断，除非置换表里有一项用来存储主要变例(这不是不可能的，因为PV结点的数量非常少)。如果要得到完整的主要变例，可以考虑不在置换表中写入PV结点(某些程序甚至只在置换表中写入Beta结点)。】
-
- 原文：http://www.seanet.com/~brucemo/topics/pv.htm
- 译者：象棋百科全书网 (webmaster@xqbase.com)
- 类型：全译加译注
上一篇 其他策略——胜利局面
下一篇 其他策略——重复检测
返 回 象棋百科全书——电脑象棋
