理解极小极大算法 (Understanding The Minimax Algorithm) [译]

原文链接：Understanding The Minimax Algorithm

理解极小极大算法

曾经喜爱编写二人的零和游戏？这里包含了在你对代码进行编译前所需要要懂得的所有东西。

 

计算机科学中最有趣的事情之一就是编写一个人机博弈的程序。有大量的例子，最出名的是编写一个国际象棋的博弈机器。但不管是什么游戏，程序趋向于遵循一个被称为极小极大的算法，伴随着各种各样的子算法在一块。

 

首先，一个定义：一个二人的零和博弈是一个两个玩家间轮流进行的比赛，整个博弈同时对于两个玩家都是可见的，并且有一个赢家和一个输家（或者打平）。零和是因为如果博弈是赌钱的，输家支付给赢家，总的来说金钱是没有损失的。（有点像能量反应：没有能量被创建或销毁）

 

Super-exploding Noughts and Crosses in Space, anyone? The rules are a little complex for this article, so we'll stick to the standard variety.

 

最简单的二人零和游戏之一是井字棋，玩家们轮流将X和O放置到一个3x3的网格中，赢家是第一个将自己的3个棋子放到在一行、一列或对角线上的那 位。你也许和我一样在小时候玩过这游戏，通过这游戏，你学会了如何促使每次都能获胜或和局。事实上，一旦两个玩家都领悟了窍门，每盘游戏的结果必定是和 局。获胜的唯一途径只有找个新手来玩了。

算法 (The algorithm)

用极小极大算法来分析井字棋，在博弈论中是相当常见的。因此我将谈论一个不一样的游戏，叫做Nim(取物游戏)，用来说明极小极大及其一些变形。因 为取物游戏容易理解、非常陌生和建模简单，它是有趣的。另外，在取物游戏中没有和局，因此整个输赢情况更加简单：总会有人胜出。但那是谁呢？

 

在取物游戏中，玩家面对3堆石子，每堆里分别有5个石子。每个玩家每轮只能在其中一个堆中取走任意数量的石子或整堆。输家是被迫取走最后一个石子的那个，这时3堆石子都被取空了。（换个角度看就是，赢家是第一个面对3堆石子被清空的玩家）

 

举个例子，假设我们的两个玩家的名字是Max和Minnie。Max先下（他总是这样，没有绅士风度）并决定取走第一堆的所有石子。然后 Minnie从第二堆取走一些石子，只留下两个。Max思考了一会儿，然后从第三堆中取走一些石子，留下了2个。然后Minnie弃权了，因为无论她怎么 做，Max都会胜出。（如果她从任一堆取走一个石子，Max取走另一堆的所有石子，留给Minnie的是最后一个石子。如果Minnie取走任一堆的所有 石子，Max取走另一堆中的一个石子，留给Minnie的还是最后一个石子。）

遍历节点 (Traversing nodes)

用博弈树对像Nim（取物游戏）这样的游戏进行建模。将博弈的初始状态看做一个节点，作为树的根。从这个节点开始，每种可能的走法都被建模为另一个关联的节点，代表博弈的另一种状态或走法。

 

图1: The first few levels in the noughts and crosses game tree.

 

因此，作为一个例子，在井字棋中，根节点是一个空的网格。习惯上X先下，有3种可能的走法：正中、角上和靠边的中间（其他的走法等同于这三个中的一 个）。因此，初始的根节点有3个关联的博弈状态。对于O，这些新节点每个都有不同可能的走法，如上面图1总所示。你可以作进一步猜想并绘出更多的层级。

 

Nim的博弈树更复杂。初始状态就有15种可能性，对应于3个堆中分别取走1，2，3，4或5个石子。这15种可能的博弈状态的每一个都连接着14种可能的状态（对于第二个玩家来说），如此类推。你可以想象到博弈状态（即博弈树中的节点）的数量在爆炸式地增长。

 

如果你碰巧有一张足够大的纸，它将能够绘制出我所描述的Nim的整个博弈树。对于树的叶节点（即没有下线连接的节点），你将能够通过到达特定叶节点 的路径（贯穿整棵树）来辨别出博弈的输家。下面的图2展示了一个特别愚蠢的路径（贯穿博弈树），玩家在每个回合中分别取走整堆石子（这绝不是明智的选择， 但这是允许的）。Max是输家，因为他在第三步中取走了第三堆的所有石子。

 

图2: An allowable but idiotic game play for Nim, resulting in Max losing.

 

我们可以赋予每一个叶节点一个值来指出谁胜出（或输了）。为了确保不造成困惑，我们以第一个玩家Max的视角并分配一个货币值。我们设定该路径中胜 出的一方获得£1，输了的一方需要支付同等数量的货币给对方——因此，如果赢家是Max，节点的值将是£1，如果赢家是Minnie则值是-£1（因为 Max需要支持同等数额给她）。

第一个玩家 (Player one)

让我们想象一下，我们站在Max（先下的玩家）的角度构来建整颗博弈树。每种走法表现为树中的一个节点，你能想象到，每一整层就代表了一个玩家的所 有可能走法。因此，树的根节点是Max在一开始所面对的情况：3个堆中分别有5个石子，对Minnie来说有15种可能的走法。在这种情况下Max应该选 择哪一个呢？他应该做的是自底向上分析所有的可能走法，并给每个节点分配一个值，以他最有可能胜出的节点不断往上选择。

 

图3: A simple choice in a game tree, to calculate the minimax value of the root node.

 

让我们来看一下上面图3中展示的一个捏造的例子。所显示的根节点是Max所需要下棋的位置。有两种可能的选择：走左边，已经知道会获胜；走右边，已 知道会输掉（记住，所有支出都是站在Max的立场来看的）。我不知道你会怎样选择，但我会选择第一个，这意味着当前博弈位置的值也为£1。对于每个轮到 Max下的博弈位置，Max都会选择最大化其利益的选项。Minnie和Max一样，将会选择对其最有利的选项。因此，她始终是最大化自己的获益，在 Max看来就是最小化他的利益。

 

如果你拥有整棵博弈树，你就能够自底向上地给每个节点算出一个值。如果是属于Max的节点（即轮到Max走棋），它的值将会是其子节点中的最大值。 如果它是属于Minnie的节点，它的值会是其子节点中的最小值。实质上，这就是极小极大算法：构造博弈树，交替地使用最小/最大约束来算出每个节点的 值。对先下的玩家（这里是Max）来说，根节点的值就是整个博弈的值。

递归函数 (The recursive method)

相对于构造并分析整棵博弈树，最好的途径是递归遍历博弈树（实际上是一个后缀遍历）并在你需要时计算出所需的数值（同时在你完成时销毁你不需要的杂 项）。实质上，由于博弈树被以递归的方式来遍历，所以通过计算各个子树的极小极大的最大（或最小）值来算出极小极大值。记住相邻层级是最大化和最小化相互 交替的（或许你会以Minnie的视角来进行观察，而非Max）。

 

下面的图4展示了一个简化了的取物游戏（只有一堆的5个石子，每次你可以取走1，2或3个石子）的完整博弈树。每个节点中的数值是走棋后石堆中剩下的石子数，每个节点旁的字母是对于Max的极小极大值（W=win, L=lose）。注意，这里博弈值（根节点的值）是L —— 即Max始终会输掉（如果你愿意，这个简化版的取物游戏的赢家始终是第二个下的那位）。

 

图4: The complete game tree for a simplified Nim game.

 

尽管极小极大算法始终确保为Max找到最好的走法，但存在一个大问题。博弈树可能很庞大——惊人的庞大。例如国际象棋，一个二人零和博弈的经典原 型。每个博弈位置都有30种可能的走法。由于每盘博弈都大约要走80步（40个回合），这意味着树的最底层会有将近10118个节点。（注意，在比赛中很 少有被将军的情况——失利的一方会提前放弃。）作为对照，在宏观宇宙中有将近10^8种原子，这意味着，实质上计算机是不可能构造出整个象棋的博弈树的。 那我们能做些什么呢？

 

第一项优化是在极小极大算法中限制我们对博弈树估算的深度。这么做的话我们可能没有真正地遍历到叶节点，因此我们使用一个逼近函数——启发式的—— 的近似值作为节点或博弈位置的值。不可避免的，该数值是不精确的，但它能让我们在使用极小极大算法时不必对底层的所有节点进行的估值。启发性能越好，越能 发现制胜的棋步，也更接近精确的极小极大值。

限制深度 (Limiting depth)

对于极小极大的递归算法，我们需要限制递归的深度而不是让他一直递归到叶节点。最简单的实现方法是将一个深度参数传递给递归的极小极大函数并在每次递归中减少它的值。在最底层的递归，我们使用启发式函数计算出当前博弈位置的极小极大值。

 

现在得到的博弈树的根节点的极小极大值仅仅是一个近似值。极小极大算法探索得越深，该值将越精确（因为我们更有机会遍历到叶节点），但会耗费更长的时间。我们计算极小极大值（指导如何走棋）时需要权衡精确度和耗时。

 

每当再次轮到我们下棋，对于新的博弈位置，我们需要重新计算它的极小极大值。每步移动都是根据基于当前博弈状态计算出的极小极大值做出的决定。

 

在很多运行在标准PC硬件的国际象棋程序中，极小极大搜索的深度被限制在6层左右——包含了十亿个可能的博弈位置。超过这个层数会导致的分析博弈位置的耗时更长，这是不现实的。例如，以1百万/s的比率分析博弈位置，6层的深度需要耗费约一刻钟。

Alpha-beta剪枝 (Alpha-beta pruning)

alpha-beta剪枝是由John McCarthy在1956年的一次会议中首先被提出（尽管该命名是后来的事了）。alpha-beta剪枝是一个用来裁剪掉博弈树某个完整分支的方法， 因此这些分支不需要被极小极大进行评估。实质上，算法在极小极大的递归中维护两个额外的值：alpha和beta。alpha是Max的最小值（对Max 来说，是其最大损失），beta是Minnie的最大值（对Max来说，是其最大得益）。一开始，alpha的取值为负无穷，beta的取值为正无穷。在 极小极大递归的过程中，当极小极大值比alpha更大时，alpha被替换为该值（beta也是一样的，当算出的值比其更小时）。如果它们在某个时刻相交 了（即alpha>=beta），那么当前查找的分支对于所有玩家都不会带来得益，因此可以被忽略掉，或裁剪掉。这表明算法不会错误地裁剪掉对任何 一方玩家有利的分支，因此alpha-beta剪枝被广泛地应用于极小极大的实现中。

 

 

By Julian M Bucknall

评论

3 楼 liufengyuan07 2012-12-05  

这就去下，谢谢，！~

2 楼 univasity 2012-12-03  

liufengyuan07 写道

你好，这篇文章的图片打不开，很着急，可以发一份给我吗，[e-mail]   谢谢！

好的，我将之前的网页备份传到网盘了，有需要的朋友请到这里下载：
http://pan.baidu.com/share/link?shareid=156112&uk=973378439

1 楼 liufengyuan07 2012-11-27  

你好，这篇文章的图片打不开，很着急，可以发一份给我吗，[e-mail]   谢谢！