- 《对弈程序基本技术》专题
-
- 最小-最大和负值最大搜索
-
- David Eppstein */文
- * 加州爱尔文大学(UC Irvine)信息与计算机科学系
-
- 搜索树
-
- 任何棋类游戏都要定义一棵有根的树(即“博弈树”)，一个结点就代表棋类的一个局面，子结点就是这个局面走一步可以到达的一个局面。例如下图是井子棋(Tic-tac-toe)的搜索树：
-
-
-
- (实际上，这个搜索树的根结点应该有9个子结点，但是我去掉了一些对称的情况。如果同样的棋盘是由两个不同的着法顺序形成的，那么我们就建立两个结点，所以这的确是树的结构。稍后我们会在讨论散列技术的时候谈到如何利用重复的结点来提高搜索速度——我们只要搜索第一个，另一个就用第一个搜索结果来代替。另外我们假设棋手是轮流下棋的，没有人一次走多步或跳过不走的，那些复杂的情况可以把它走的一系列着法看作一个着法来处理。【译注：复杂的情况是指一些一次能走很多步的棋类游戏，例如跳棋、西洋跳棋、黑白棋等，按照原作者的方案，可以把一方连续走的几步棋看成一步棋。而译者更愿意把一方连续的几步棋拆成几个回合，只是另一方都别无选择地走了空着。】最后，我们假设搜索树是有限的，这样我们就不会遇到永无止境的棋局或者一步有无限多种着法的棋局。)
- 搜索树中有三种类型的结点：
- (1) 偶数层的中间结点，代表棋手甲要走的局面；
- (2) 奇数层的中间结点，代表棋手乙要走的局面；
- (3) 叶子结点，代表棋局结束的局面，即棋手甲或棋手乙获胜，或者是和局。
-
- 博弈树的评价
-
- 假设某个中间结点的所有子结点都是叶子结点，那么棋局会在一回合内结束。现在我们假设棋手会挑选最好的着法，如果有一个着法能使他赢下棋局，那么他一定会走这步。如果没有可以赢的着法，但是有取得和局的着法，那么他会走这步取得和局的着法。但是，如果所有的着法都使得对手获胜，那么无论如何他都会输。
- 因此在叶子结点的上一层结点，我们就能知道棋局的结果。现在我们知道了这个结点的结果，那么我们可以用同样的方法作推演，知道叶子结点的上两层结点的结果，然后是上三层结点，等等，直到我们达到搜索树的根结点。在每个结点上，棋手只要找到一个子结点能让他获胜，那么他就可以赢下棋局；他只要找到一个形成和局的子结点，棋局就和了；如果获胜与和局的子结点都没有，那么肯定是输的。如果我们有足够多的时间来计算，那么这就给了我们一个可以下棋的完美算法。但是对于任何常规的棋类游戏，我们都不可能有足够的计算时间，因为搜索树实在太大了。
- 另外，“正确”的评价函数只有三个值，赢、输或者和局。在实际的棋类程序中，我们通常使用一个更宽泛的实数来作评价值，就是因为赢、输或者和局是不确定的。如果棋手甲获胜的值用+1表示，和局的值用0表示，棋手乙获胜的值用-1表示，那么博弈树的每个中间结点的值就是子结点的最大值或最小值，这取决于棋手甲还是棋手乙着棋。
-
- 部分的博弈树
-
- 在实战中，我们的搜索算法只能对博弈树展开一部分。我们用一些“中止规则”来决定搜索树展开到哪个结点就停下来，例如我们在8步变化以后听下来。由于棋局没有在叶子结点结束，我们只能用评价函数来猜哪一方获胜。现在我们来假设在我们展开的结点中，棋手甲总是希望棋局到达评价函数大的局面，而棋手乙总是希望棋局到达评价函数小的局面。
- 如果双方都用这种方法来下棋，那么我们可以使用同样的最小-最大过程，来确定到达的叶子结点的评价值，这个过程如下：对每个中间结点，计算子结点的最大值或最小值，这取决于是棋手甲还是棋手乙走棋。到达叶子结点的线路称为“主要变例”(Principal Variation)。最小-最大博弈树的基本原理，就是对博弈树作部分展开，去找主要变例，并走出变例中的第一步。
-
- 广度优先和深度优先搜索，负值最大代码
-
- 正如上面所讲的，计算博弈树的值是一个广度优先的过程(我们要自下而上地，一次一层地计算)。然而实战中，我们使用深度优先(即后序遍历)的递归过程来遍历搜索树，即要得到一个结点的值，就对子结点做递归，然后根据它们的返回值来决定自身的返回值。这样要节省很多空间，因为不需要来存储整个博弈树，而只是存储一条线路(相对来说非常短，例如上面提到的8步中止的规则)。下次我们讨论Alpha-Beta搜索时，会发现深度优先的遍历会有很大的优势，你可以用目前得到的信息来决定某些结点是不需要访问的，这样就节省下很多的时间。
- 只要对搜索树的值作一个很小的改动，就可以用一个求最大值的操作来代替最小值和最大值交替的过程。在搜索树的奇数层(即轮到棋手乙下棋的结点)，就对上面提到的评价值取负数。因此在每个结点上，这些值都可以由子结点的负值求得。我把博弈树搜索的源代码写出来，恐怕就会清楚很多了。
-
- // 将博弈树搜索到一定的深度，返回根结点的评价值
- double negamax(int depth) {
- if (depth <= 0 || 棋局结束)
- return eval(pos);
- else {
- double e = -infty;
- for (当前局面所有可能的着法 m) {
- 执行着法 m;
- e = max(e, -negamax(depth - 1));
- 撤消着法 m;
- }
- return e;
- }
- }
-
- 注意，这个过程只能找到评价值，但是无法得知着法。我们只要在搜索树的根结点找到着法(尽管很多程序都返回整个主要变例)就可以了，要做到这一点，可以对根结点的搜索稍作改动：
-
- // 将博弈树搜索到一定的深度，返回根结点的着法
- move rootsearch(int depth) {
- double e = -infty;
- move mm;
- for (当前局面所有可能的着法 m) {
- 执行着法 m;
- double em = -negamax(depth - 1);
- if (e < em) {
- e = em;
- mm = m;
- }
- 撤消着法 m;
- }
- return mm;
- }
-
- 负值最大的分析：分枝因子和深度
-
- 人们通常简单地根据博弈树的形状来对博弈树算法进行分析。我们假设每个中间结点有同样多的子结点，其数量称为分枝因子(Branching Factor)。我们还假设搜索到固定的深度(就如前面所提到的算法一样)，并且棋局不会很早地结束(在达到搜索深度以前结束)。
- 在这些假设下，很容易写下负值最大程序所花的时间，即正比于展开结点的数量。(看上去需要乘上一个系数，以反映调用负值最大时的那个循环，但是这个循环所花的时间已经被包括在递归函数里了。)【译者也不理解这句话的意思，但译者认为程序中eval()函数所花费的时间最多，而它只是在搜索到叶子结点时才被调用，因此只计算叶子结点的数量就可以了，即bd。】如果分枝因子是b，深度是d，那么这个数就是：
- 1 + b + b2
+ b3 + ... + bd
= bd (1 - 1 / bd)
/ (1 - 1 / b).
- 公式右端括号里的数值接近于1，所以整个运算所花费的时间接近于bd。
- 如果棋类游戏不符合以上假定，我们可以反过来定义一个“有效分枝因子”(Effective Branching Factor)，使得这个b能够符合程序运行所花费的时间。更简单些，可以把“分枝因子”描述为某个棋类游戏中“典型”局面的可能着法数的平均值。
- 这个公式可以告诉我们什么呢？首先它是指数形式的，这就意味着我们不可能搜索太多层，如果电脑的速度翻了番，那么我们只能把d增加很小一点。其次搜索取决于分枝因子b，在分枝因子很小的棋类中(像西洋跳棋，通常每个局面只有3个着法)，我们就可以搜索的比国际象棋(一个局面有30种左右的着法)或围棋(一个局面有几百种着法)深得多，因此我们喜欢让b越小越好。很不幸的是搜索函数更多地决于棋类游戏本身，而不是我们写程序的水平。但是下一次我们要讨论一个算法，称为Alpha-Beta裁剪，它可以很大程度地减少分枝因子，如果运气好的话，它可以减少到没有裁剪的博弈树的平方根那么多，这就意味着我们可以搜索原来深度(即不用Alpha-Beta搜索的深度)的两倍那么深。【b的平方根即b1/2，用一下中学数学学过的公式，(b1/2)d
= bd/2，还记得吗？】
-
- 迭代加深
-
- 负值极大的代码还留给我们一个问题：我们如何来给定搜索深度？简单的棋类程序只把它设成一个固定值，这就可能使得程序走的每步棋时花的时间长短变化非常大。因此你最好根据搜索所需的时间，来决定搜索的深度。幸运的是指数特征的搜索有这样一个好处：通过“迭代加深”(Iterated Deepening)这个手段，可以很容易地对搜索进行控制，刚开始搜索时浅一些，然后增加深度重复搜索直到时间用完为止：
-
- depth = 0
- while (有足够的时间来进行下一层的搜索) {
- depth ++;
- m = rootsearch(depth);
- }
- 执行着法 m;
-
- 这看上去似乎在浪费时间，因为除了最后一次搜索外，前面的搜索都白费了。但是根据前面分析过的结果，白费的时间是很少的：不同层数所花的时间加起来是
1 + b + b2
+ ...，我们已经知道它接近于最后一项bd了。所以，迭代加深所花的代价并不多，而它给我们提供了很好的时间控制的手段。它还有一个很大的作用：在做较深的搜索时，可以用浅一层搜索得到的着法顺序，在Alpha-Beta搜索中，着法顺序是影响搜索的速度的决定性因素。
- 【Iterative
Deepening，字面意思是“重复加深”，就如上文所讲的。但它最主要的作用是改善着法的顺序，它是Alpha-Beta搜索的一种主要的启发方式，浅一层最好的着法在深一层的搜索中首先被尝试，本质上是一种迭代的过程，所以译为“迭代加深”。】
-
- 原文：http://www.ics.uci.edu/~eppstein/180a/970417.html
- 译者：象棋百科全书网 (webmaster@xqbase.com)
- 类型：全译加译注
上一篇 数据结构——Zobrist键值
下一篇 基本搜索方法——简介(二)
返 回 象棋百科全书——电脑象棋
