常会返回正数；如果黑方是赢棋或者很有希望赢，那么返回负数；如果棋局是均势或者是和棋，那么返回在零左右的数值。
2、这个函数的工作原理跟第一个一样，只是如果当前局面要走子的一方优势，那么它返回正数，反之是负数。 5.1.2 最小-最大搜索
最小-最大搜索是一对几乎一样的函数，或者说两个逻辑上重复的函数。纯粹的(不完美的)最小-最大函数，代码如下：
int MinMax(int depth) {
if (SideToMove() == RED) { // 红方是“最大”者 return Max(depth);
} else { // 黑方是“最小”者 return Min(depth); } }
int Max(int depth) { int best = -INFINITY; if (depth <= 0) { return Evaluate(); }
GenerateLegalMoves(); while (MovesLeft()) { MakeNextMove(); val = Min(depth - 1); UnmakeMove(); if (val > best) { best = val; } }
return best; }
int Min(int depth) {
int best = INFINITY; // 注意这里不同于“最大”算法 if (depth <= 0) { return Evaluate(); }
- 29 -
GenerateLegalMoves(); while (MovesLeft()) { MakeNextMove(); val = Max(depth - 1); UnmakeMove();
if (val < best) { // 注意这里不同于“最大”算法 best = val; } }
return best; }
上面的代码可以这样调用： val = MinMax(5);
这样可以返回当前局面的评价，它是向前看5步的结果。
这里的“评价”函数用的是我上面所说第一种定义，它总是返回对于红方来说的局面。
我简要描述一下这个函数是如何运作的。假设根局面(棋盘上当前局面)是红方走，那么调用的是“Max”函数，它产生红方所有合理着法。在每个后续局面中，调用的是“Min”函数，它对局面作出评价并返回。由于现在是白走，因此白方需要让评价尽可能地大，能得到最大值的那个着法被认为是最好的，因此返回这个着法的评价。
“Min”函数正好相反，当黑方走时调用“Min”函数，而黑方需要尽可能地小，因此选择能得到最小值的那个着法。
这两个函数是互相递归的，即它们互相调用，直到达到所需要的深度为止。当函数到达最底层时，它们就返回“Evaluate”函数的值。
如果在深度为1时调用“MinMax”函数，那么“Evaluate”函数在走完每个合理着法之后就调用，选择一个能达到最佳值的那个着法导致的局面。如果层数大于1，那么另一方有权选择局面，并找一个最好的。 5.1.3、负值最大函数
负值最大只是对最小-最大的优化，“评价”函数返回我所说的第二种定义，对于当前结点上要走的一方，占优的情况返回正值，其他结点也是对于要走的一方而言的。这个值返回后要加上负号，因为返回以后就是对另一方而言了。代码如下：
int NegaMax(int depth) { int best = -INFINITY; if (depth <= 0) { return Evaluate();
- 30 -
}
GenerateLegalMoves(); while (MovesLeft()) { MakeNextMove();
val = -NegaMax(depth - 1); // 注意这里有个负号。 UnmakeMove(); if (val > best) { best = val; } }
return best; }
在这个函数里，当走子一方改变时就要对返回值取负值，以反映当前局面评价的更改。就根结点是红先走的情况，如果没有剩下的层数，那么“评价”返回的值是就红方而言的，如果有剩下的层数，就产生后续局面，函数对这些局面逐一做递归，每个次递归都得到就黑方而言的评价，黑方走得越好值就越大。当评价值返回时，它们被取负数，变成就白方而言的评价。
该函数在遍历时结点的顺序同“最小-最大”搜索的函数是一样的，产生的返回值也一样。它的代码更短，同时减少了移植代码时出错的可能，代码维护起来也比较方便。
5.2 Alpha-Beta搜索
5.2.1 最小-最大搜索算法的问题
Alpha-Beta 同“最小-最大”非常相似，事实上只多了一条额外的语句。“最小-最大”运行时要检查整个博弈树，然后尽可能选择最好的线路。这是非常好理解的，但效率非常低。每次搜索更深一层时，树的大小就呈指数式增长。
通常一个中国象棋局面平均都有45个左右的合理着法（有效分支因子），所以用最小-最大搜索来搜索一层深度，就有45个局面要检查，如果用这个函数来搜索两层，就有452个局面要搜索，搜索局面的数量一指数级增长，非常迅速。要想通过检查搜索树的前面几层，并且在叶子结点上用启发式的评价，那么做尽可能深的搜索是很重要的。最小-最大搜索无法做到很深的搜索，因为有效的分枝因子实在太大了。 5.2.2 Alpha-Beta修剪
Alpha-Beta修剪算法可以有效地减少分支因子，它是建立在这样一个思想之上：如果你已经有一个不太坏的选择了，那么当你要作别的选择并知道它不会更好时，你没有
- 31 -
必要确切地知道它有多坏。有了最好的选择，任何不比它更好的选择就是足够坏的，因此你可以撇开它而不需要完全了解它。只要你能证明它不比最好的选择更好，你就可以完全抛弃它。Alpha-Beta对搜索树有两种修剪
1、浅的修剪
假设用最小-最大搜索(前面讲到的)来搜索下面的树：
当搜索到F，发现子结点的评价分别是11、12、7和9，在这层是棋手甲走，我们希望他选择最好的值，即12。所以，F的最小-最大值是12。
现在开始搜索G，并且第一个子结点就返回15。一旦如此，就知道G的值至少是15，可能更高(如果另一个子结点比G更好)。这就意味着我们不指望棋手乙走G这步了，因为就棋手乙看来，F的评价12要比G的15(或更高)好，因此我们知道G不在主要变例上。我们可以裁剪(Prune)结点G下面的其他子结点，而不要对它们作出评价，并且立即从G返回，因为对G作更好的评价只是浪费时间。一般来说，像G一样只要有一个子结点返回比G的兄弟结点更好的值(对于结点G要走棋的一方而言)，就可以进行裁剪。
2、深的裁剪
我们来讨论更复杂的可能裁剪的情况。例如在同一棵搜索树中，我们评价的G、H和I都比12好，因此12就是结点B的评价。现在我们来搜索结点C，在下面两层我们找到了评价为10的结点N：
- 32 -
相关推荐：
loading