讲解极小极大 (Minimax Explained) [译]

原文链接：Minimax Explained

讲解极小极大

Written by Paulo Pinto .

 

本文讨论如何把搜索应用到带有完整信息的逻辑游戏上。会提及到博弈树，和一个对其进行搜索的算法。给出了伪代码并对变形alpha-beta进行了讲解。

 

 

算法 (The Algorithm)

简介(Introduction)

AI有广泛的应用领域，其中游戏是最有趣的。当今每个主流的操作系统都会附带一些游戏。因此，对于某些算法是专门为游戏设计的，并不需要感到意外。

极小极大算法 (The Min-Max Algorithm)

极小极大算法被应用于二人博弈中，比如井字过三关、西洋棋、国际象棋、围棋等等。所有这些游戏都有一个共通点，都是逻辑游戏。这意味着，可以通过一 组规则和前置条件来定义它们。利用这些（规则和条件），就能够从一个给定的游戏局面得知下一步可能的移动。它们（这些游戏）同时还共同拥有其他一些特性， 都是“拥有完整信息的博弈”。每个玩家都能知道一切关于对手可能的移动方式。

 

图1 ：展示了一个逻辑游戏的搜索树

 

在讲解算法之前，有必要简短地介绍一下搜索树。搜索树是展示搜索的一种途径。方形代表节点，标志了搜索中的决策点。这些节点通过分支连接在一起。搜 索始于根节点，图中最顶上的那个。在每个决策点，可行搜索路径上的节点会被创建，直到再没有更多可能的决策。标志搜索结束的节点是叶节点。

 

这里涉及两个玩家，MAX与MIN。一颗搜索树按深度优先（从当前的游戏位置(进度)开始，直到游戏结束的位置）被生成。最终的选择的位置(走法) 是以MAX的角度来评估的，图1中展示的正是如此。然后，自底向上给树上的节点赋予一个估值。属于MAX玩家的节点获取其子节点中的最大值。MIN玩家的 节点会选择其子节点中的最小值。该算法被描述在清单1中。

MinMax (GamePosition game) {
  return MaxMove (game);
}
 
MaxMove (GamePosition game) {
  if (GameEnded(game)) {
    return EvalGameState(game);
  }
  else {
    best_move < - {};
    moves <- GenerateMoves(game);
    ForEach moves {
       move <- MinMove(ApplyMove(game));
       if (Value(move) > Value(best_move)) {
          best_move < - move;
       }
    }
    return best_move;
  }
}

MinMove (GamePosition game) {
  best_move <- {};
  moves <- GenerateMoves(game);
  ForEach moves {
     move <- MaxMove(ApplyMove(game));
     if (Value(move) > Value(best_move)) {
        best_move < - move;
     }
  }

  return best_move;
}

 

这里发生了什么事？这些数值表明了该步移动有多好。因此，玩家MAX最终会选择最高分数的进行移动。对此玩家MIN也有所行动，将选择对其最有利的移动，即最小化了MAX的得益。

优化 (Optimisations)

优化(Optimisation)

然而，只有非常简单的博弈能够在短时间内生成整棵搜索树。对大多数博弈来说，这是不可能的，到那时可能宇宙都消失了(需要很长的时间)。因此，要对算法进行一些优化。

 

首先需要注意的是，优化是有代价的。我们用与博弈发展有关（几率和捷径）的完整信息来换取算法的最优化。把“通往胜利的完整路径”取代为“通过有机 会获得胜利的路径”来进行决策。如果优化不是最佳选择，或者优化得不好，那么我们能用无用的AI来结束算法。但这也比使用随机选取要好。

 

一个基本的优化是，限制搜索树的深度。为什么这会有所帮助？因为生成完整的树要耗费年月。如果博弈树的分子因子是3，即每个节点都有子树，树中每个层次中节点的数量如下:

Depth	Node Count
0	1
1	3
2	9
3	27
…	..
n	3^n

 

这个序列展示了深度为n的树将有3^n个节点。要获得所有节点的总数，我们需要把每层的节点数加起来。因此，一棵n层的树其节点总数为(0, n, 3^n)。对于多数博弈，像国际象棋就有一个庞大的分支因子，这意味着整棵树可能无法被加载到内存中。即便能行，生成整棵树也将需要很长一段时间。如果分析一个节点需要1秒，那就是说在前面的例子中，每次搜索数都需要耗费(0, 3, 3^n)*1秒。对于一个5层的搜索树，那将是1+3+9+27+81+243 = 364 * 1 = 364秒 = 6分钟! 这对于一个博弈来说太久了。如果电脑的每次移动都要玩家等上6分钟，估计玩家就退出游戏了。

 

第二项优化是，使用一个函数，以某个玩家的角度对当前的棋步进行评估。它将对当前博弈状态给定一个值。例如，统计棋盘上棋子的数量、或离博弈结束还剩余的步数，或是任何我们可以用来衡量棋步的数值。

 

除了评估当前的棋步，该函数可能还计算出当前棋步对结束博弈的帮助有多大。或者换种说法，当前棋步带来的胜数有多大。在这种情况下，该函数被称为“评估函数”。

 

该函数必须把一些启发性考虑进去。启发性即我们对与博弈相关的事物的认知，这有助于创建更好的估值函数。例如，在西洋棋中，在角和边上的棋子是不会 被吃掉的。因此我们可以创建一个估值函数，对在棋盘中这些位置上的棋子给出更高的分值，从而令棋子下到这些位置，使博弈获得更好的结果。

 

估值函数必须能够同时为两个玩家评估棋步，因为你不知道当前（有限的）深度是轮到哪个玩家了。

 

尽管如此，如果博弈是对称的（这是说一个玩家的损失等于另一个玩家的得益，这样的博弈被称为“零和博弈”），则可以不用分别创建两个估值函数。对于这些博弈，一个估值函数就足够了，其中一个玩家只要取反值即可。

 

改进后的算法在清单2中展示：

MinMax (GamePosition game) {
  return MaxMove (game);
}
 
MaxMove (GamePosition game) {
  if (GameEnded(game) || DepthLimitReached()) {
    return EvalGameState(game, MAX);
  }
  else {
    best_move < - {};
    moves <- GenerateMoves(game);
    ForEach moves {
       move <- MinMove(ApplyMove(game));
       if (Value(move) > Value(best_move)) {
          best_move < - move;
       }
    }
    return best_move;
  }
}
 
MinMove (GamePosition game) {
  if (GameEnded(game) || DepthLimitReached()) {
    return EvalGameState(game, MIN);
  }
  else {
    best_move <- {};
    moves <- GenerateMoves(game);
    ForEach moves {
       move <- MaxMove(ApplyMove(game));
       if (Value(move) > Value(best_move)) {
          best_move < - move;
       }
    }
    return best_move;
  }
}

 

即便如此，该算法仍然存在一些缺陷，某些缺陷能通过选择另一个算法来被修复。

 

其中一个缺陷是，如果博弈很复杂，即使有限的深度，答应也会耗费很长一段时间。一个解决方案是限制搜索的时间。如果超时了则返回当前所找到的最好选择。

 

而最大的缺陷是，“有限的视界问题”。一个看似很好的棋步，却可能导致糟糕的结果。这是因为算法没能预见对手将会采取并导致其获利的棋路所导致的。由于算法被有限的深度蒙住了双眼，错失了致命的一步棋。

 

给算法提速(Speeding the algorithm)

仍然有一些东西是可以用来降低搜索时间的。来看一下图2。节点A的值是3，对于起源自节点B的子树，被找到的第一个值是2。因为节点B是在MIN 层，我们是要为节点B选择小于等于2的值。同时我们知道节点A的值是3，并且节点A和B共享同一个在MAX层级的父节点。这意味着起源自节点B的路径不会 被选择，因为对于MAX层的节点来说，3比2更好。因此，不值得继续对节点B的子树进行搜索，我们将安全地忽略掉所有剩余的子节点。

 

图2 ：极小极大搜索树，展示了可以被剪断的分支。

所有的这些都表明，当我们发现对子树的搜索不会带给我们任何有用的结论的时候，搜索可以被跳过。

 

这一优化被称为alpha-beat剪枝，算法描述如下：

   1. 有两个值被传递到每个树的节点：

            值alpha，记录着找到的最好的“大值”（MAX value）；

            值beta，记录着找到的最好的“小值”（MIN value）。

   2. 在MAX层时，在对每个子路径进行估值前，用前一路径的返回值与beta值作比较。如果该值大于beta值，那么跳过对当前节点的搜索；

   3. 在MIN层时，在对每个子路径进行估值前，用前一路径的返回值与alpha值作比较。如果该值小于alpha值，那么跳过对当前节点的搜索。

 

清单3展示了使用了alpha-beta剪枝的MiniMax的完整伪代码：

MinMax (GamePosition game) {
  return MaxMove (game);
}
 
MaxMove (GamePosition game, Integer alpha, Integer beta) {
  if (GameEnded(game) || DepthLimitReached()) {
    return EvalGameState(game, MAX);
  }
  else {
    best_move < - {};
    moves <- GenerateMoves(game);
    ForEach moves {
       move <- MinMove(ApplyMove(game), alpha, beta);
       if (Value(move) > Value(best_move)) {
          best_move < - move;
          alpha <-  Value(move);
       }
 
       // Ignore remaining moves
       if (beta > alpha)
         return best_move;
    }

    return best_move;
  }

}
 
MinMove (GamePosition game) {
  if (GameEnded(game) || DepthLimitReached()) {
    return EvalGameState(game, MIN);
  }
  else {
    best_move < - {};
    moves <- GenerateMoves(game);
    ForEach moves {
       move <- MaxMove(ApplyMove(game), alpha, beta);
       if (Value(move) > Value(best_move)) {
          best_move < - move;
          beta <- Value(move);
       }
 
       // Ignore remaining moves
       if (beta < alpha)
         return best_move;
    }

    return best_move;
  }

}

 

使用了alpha-beta剪枝的MiniMax比默认的MiniMax好多少？这取决于搜索的次序。如果该步棋看起来不会造成影响，那么算法使用 alpha-beta剪枝也不会带来改善。但是，如果是估值函数和产生的棋步所导向的alpha-beta剪枝，会带来更显著的效果。

Alpha-Beta剪枝 (Alpha-Beta Cutoff)

增添Alpha-Beta剪枝 (Adding Alpha-Beta Cutoffs)

大部分人都很想知道这里所讲的“搜索速度”到底是什么。搜索速度在AI中是非常重要的，因为如果一个算法要耗费很长的时间才能给出一个满意的答复，那么该算法是不适合的。

 

例如，一个好的MiniMax算法实现，其估值函数能够给出高质量的评估，或许能够在1秒内探索1000种下法。在象棋比赛中，每个玩家有150秒来决定如何走棋。因此，在这段时间内函数将能够分析150 000种下法。但是，象棋中的每一步都有35种可能的分支！在最后，程序将只能分析出每个棋步的3-4个分支。即便是没有练习过的人也能做得比这好。

 

但是，如果我们把alpha-beta剪枝应用到MiniMax中，加上一个正确的估值函数，结果会更加好。这种情况下，程序就有可能对双倍数量的下法进行分析，从而变成一个更强大的对手。

一个实现的例子 (An example implementation)

例子总是用来说明算法如何实现的一个好途径。回到1999年，我和一个要好的朋友就已经实现了一个西洋棋游戏的Java应用（为了大学的AI课程）。我最近将游戏移植到了C#上。

 

其中的MiniMax算法不是一个最好的实现。其实我要说明的是“最重要的是它能运行”。无论如何，我认为这展示了算法的一种可能实现方式，并且作为例子它已经足够好了。

 

图3 ：每个格子都带有估值的一个棋盘的例子

 

游戏中使用了带有alpha-beta剪枝的MiniMax来为电脑提供移动决策。估值函数为每个被棋子所占据的格子提供一个加权平均数。图3展示 了对每个棋盘上格子的估值。每个格子上的数值被乘以该格子上棋子的类型，在清单5中列出。清单4展示了估值函数的Java实现。它已经被轻微的做了修改， 以符合该主题。

 

                  Piece                                 Value
Normal                                                    5
Normal but close to being promoted       7
King                                                       10

表1 : Piece Values

 

 

// Snippet from Computer.java.
// Contains the evaluation function
/**
* Evaluation function.
*/
private int eval (CheckersBoard board) {
    int colorKing;
    // Finds out who is the current player
    if (color == CheckersBoard.WHITE)
        colorKing = CheckersBoard.WHITE_KING;
    else
        colorKing = CheckersBoard.BLACK_KING;
    int colorForce = 0;
    int enemyForce = 0;
    int piece;
    try {
        // Searchs all board positions for pieces
        // and evaluates each position.
        for (int i = 0; i < 32; i++) {
            piece = board.getPiece (i);
            if (piece != CheckersBoard.EMPTY)
                if (piece == color || piece == colorKing)
                    colorForce += calculateValue (piece, i);
                else
                    enemyForce += calculateValue (piece, i);
        }
    }
    catch (BadCoord bad) {
        bad.printStackTrace ();
        System.exit (-1);
    }
    return colorForce - enemyForce;
}


/**
* Measures the value of a checkers piece, given
* it’s position in the board
*/
private int calculateValue (int piece, int pos) {
    int value;
    if (piece == CheckersBoard.WHITE ) //Simple piece
    if (pos >= 4 && pos <= 7) // White pieces are more
        value = 7; // valuable the closer they get
    else // to the oponent
        value = 5;
    else if (piece != CheckersBoard.BLACK) //Simple piece
        if (pos >= 24 && pos <= 27) // White pieces are more
            value = 7; // valuable the closer they get
        else // to the oponent
            value = 5;
        else // King piece
            value = 10; // King pieces are always the
    // most valuable
    return value * tableWeight[pos];
} 

清单5 : The Java implementation of the evaluation function.

 

注意，代码中使用了一个容器，基于0-31，用来表示棋盘上的位置。

 

游戏代码在这里下载：

• Java version - http://www.progtools.org/games/projects/checkers/checkers.html
• C# version - http://www.progtools.org/games/projects/sharp_checkers/sharp_checkers.html

结论(Conclusion)

对于各种需要模拟人类AI的电脑博弈，MiniMax可能并不是最好的。但是，一个好的实现也能创建出一个强大的对手。我希望这篇文章能在让你了解MiniMax算法并懂的如何将它用到你的游戏中。

 

参考资料(References)

[1] - Russell Stuart J., Norvig Peter. “Artificial Intelligence. A modern approach.”. Prentice Hall, 1995. ISBN 0-13-103805-2.
[2] - Bratko Ivan. “PROLOG. Programming for artificial intelligence” Addison-Wesley, 1990. ISBN 0-201-41606-9
[3] - Rich Elaine, Knight Kevin. “Artificial Intelligence”. McGraw-Hill Inc., 1991. ISBN 0-07-100894-2
[4] - Analytical Reasoning FAQ. Available at http://www.west.net/~stewart/lwfaq.htm

 

Written by Paulo Pinto .