我们能用更为复杂的路线来作裁剪。我们知道N会返回10或更小(轮到棋手乙走棋，需要挑最小的)。我们不知道J能否返回10或更小，也不知道J的哪个子结点会更好。如果从J返回到C的是10或者更小的值，那么我们可以在结点C上作裁剪，因为它比兄弟结点B要好。因此在这种情况下，继续找N的子结点就毫无意义。考虑其他情况，J的其他子结点返回比10更好的值，此时搜索N也是毫无意义的。所以我们只要看到10，就可以放心地从N返回。 5.2.3 Alpha-Beta修剪算法的实现
Alpha-Beta修剪算法在搜索中传递两个值，第一个值是Alpha，即搜索到的最好值，任何比它更小的值就没用了，因为策略就是知道Alpha的值，任何小于或等于Alpha的值都不会有所提高。
第二个值是Beta，即对于对手来说最坏的值。这是对手所能承受的最坏的结果，因为我们知道在对手看来，他总是会找到一个对策不比Beta更坏的。如果搜索过程中返回Beta或比Beta更好的值，那就够好的了，走棋的一方就没有机会使用这种策略了。
在搜索着法时，每个搜索过的着法都返回跟Alpha和Beta有关的值，它们之间的关系非常重要，或许意味着搜索可以停止并返回。
如果某个着法的结果小于或等于Alpha，那么它就是很差的着法，因此可以抛弃。因为我前面说过，在这个策略中，局面对走棋的一方来说是以Alpha为评价的。
如果某个着法的结果大于或等于Beta，那么整个结点就作废了，因为对手不希望走到这个局面，而它有别的着法可以避免到达这个局面。因此如果我们找到的评价大于或等于Beta，就证明了这个结点是不会发生的，因此剩下的合理着法没有必要再搜索。
如果某个着法的结果大于Alpha但小于Beta，那么这个着法就是走棋一方可以考虑走的，除非以后有所变化。因此Alpha会不断增加以反映新的情况。有时候可能一个合
- 33 -
理着法也不超过Alpha，这在实战中是经常发生的，此时这种局面是不予考虑的，因此为了避免这样的局面，我们必须在博弈树的上一个层局面选择另外一个着法。算法代码如下，醒目斜体部分是在最小-最大算法上改过的：
int AlphaBeta(int depth, int alpha, int beta) { if (depth == 0) {
return Evaluate(); }
GenerateLegalMoves(); while (MovesLeft()) { MakeNextMove();
val = -AlphaBeta(depth - 1, -beta, -alpha); UnmakeMove();
if (val >= beta) { return beta; } if (val > alpha) { alpha = val; } }
return alpha; }
把醒目的部分去掉，剩下的就是最小-最大函数。可以看出现在的算法没有太多的改变。
这个函数需要传递的参数有：需要搜索的深度，负无穷大即Alpha，以及正无穷大即Beta：
val = AlphaBeta(5, -INFINITY, INFINITY);
这样就完成了5层的搜索。最终出现的情况是，在搜索树的很多地方，Beta是很容易超过的，因此很多工作都免去了。 5.2.4 可能的弱点
这个算法严重依赖于着法的寻找顺序。如果你总是先去搜索最坏的着法，那么Beta截断就不会发生，因此该算法就如同最小-最大一样，效率非常低。该算法最终会找遍整个博弈树，就像最小-最大算法一样。
如果程序总是能挑最好的着法来首先搜索，那么数学上有效分枝因子就接近于实际分枝因子的平方根。这是Alpha-Beta算法可能达到的最好的情况。
- 34 -
由于中国象棋的分枝因子在45左右，这就意味着Alpha-Beta算法能使国际象棋搜索树的分枝因子变成7左右。
这是很大的改进，在搜索结点数一样的情况下，可以使你的搜索深度达到原来的两倍。这就是为什么使用Alpha-Beta搜索时，着法顺序至关重要的原因。 5.3迭代加深
如果准备开始搜索一个中国象棋的局面，那么要搜索多深？事先预测搜索将进行多少时间，这有些困难，因为完成D层搜索所需要的时间取决于很多不确定的因素。在复杂的中局局面里，你可能不会搜索得很深，而在残局中你可能会搜索得非常深。
有一个思想，就是一开始只搜索一层，如果搜索的时间比分配的时间少，那么搜索两层，然后再搜索三层，等等，直到你用完时间为止。
这足以保证很好地运用时间了。如果你可以很快搜索到一个深度，那么你在接下来的时间可以搜索得更深，或许你可以完成。如果局面比你想象的复杂，那么你不必搜索得太深，但是至少有合理的着法可以走了，因为你不太可能连1层搜索也完不成。
这个思想称为“迭代加深”(Iterative Deepening)，因为使用迭代搜索，每次都比一次前一次加深1层(多1层没有什么奥妙的，当然你可以试试多两层，但是1层比较好)。
代码如下：
for (depth = 1; ; depth ++) {
val = AlphaBeta(depth, -INFINITY, INFINITY); if (TimedOut()) { break; } }
这是一个非常有效的搜索方法。如果能增强Alpha-Beta使得它返回一条“主要变例”，那么便可以用主要变例中的着法来做下一次迭代搜索。这样做之所以有好的效果，是因为第一次搜索的线路通常是好的，而Alpha-Beta对着法的顺序特别敏感。如果着法顺序很坏，那么在中国象棋中“分枝因子”将接近45。如果着法很好，那么分枝因子将接近于7。前一次迭代的搜索函数得到的主要变例通常是非常好的着法。
迭代加深的思想给了你一个简单的方法，它可以在时间用完时中断搜索，并且会提高你的搜索效率。 5.4 置换表
中国象棋的搜索树可以用图来表示，而置换结点可以引向以前搜索过的子树上。置换表可以用来检测这种情况，从而避免重复劳动。置换表还有另一个更为重要的作用：每个散列项里都有局面中最好的着法，在“迭代加深”中，首先搜索好的着法可以大幅
- 35 -
度提高搜索效率。因此如果在散列项里找到最好的着法，那么首先搜索这个着法，这样会改进着法顺序，减少分枝因子。 5.4.1 置换表的实现
主置换表是一个散列数组，每个散列项如下：
class HashRecord { };
private static final int BookUnique = 1;//指示结点类型，就是下面Flag的值。 private static final int BookMulti = 2; private static final int HashAlpha = 4; private static final int HashBeta = 8; private static final int HashPv = 16; public HashRecord(){ Flag=0; Depth=0; Value=0; ZobristLock = 0; BestMove = new MoveStruct(); }
long ZobristLock; int Flag, Depth; int Value;
MoveStruct BestMove;
这个散列数组是以―Zobrist键值‖为指标的。当求得局面的键值，除以散列表的项数得到余数，这个散列项就代表该局面。由于很多局面都有可能跟散列表中同一项作用，因此散列项需要包含一个校验值，它可以用来确认该项就是要找的。通常校验值是一个64位的数，也就是上面的ZobristLock。
从搜索中得到结果后，要保存到散列表中。用散列表来避免重复工作，最重要的是记住搜索有多深。如果在一个结点上搜索了3层，后来又打算做10层搜索，就不能认为散列项里的信息是准确的。因此子树的搜索深度也要记录。
在Alpha-Beta搜索中，很少能得到搜索结点的准确值。Alpha和Beta的存在有助于裁剪掉没有用的子树，但是用Alpha-Beta有个小的缺点，就是通常不会知道一个结点到底有多坏或者有多好，只是知道它足够坏或足够好，从而不需要浪费更多的时间。
当然，这就引发了一个问题，散列项里到底要保存什么值，并且当你要获取它时怎样来做。答案是储存一个值，另加一个标志来说明这个值是什么含义。在我上面的例子中，比方说你在评价域中保存了16，并且在标志域保存了―HashPV‖，这就意味着该结点的评价是准确值16；如果你在标志域中保存了―HashAlpha‖，那么结点的值最多是16；如果保存了―HashBeta‖，这个值就至少是16。
- 36 -
相关推荐：
loading