什么是极大极小博弈树？

极大极小博弈树(Minimax Game Tree,简写为MGT)用于编写电脑之间的游戏程序，这类程序由两个游戏者轮流，每次执行一个步骤。当然，所有可能的步骤构成了一个树的结构。例如下面的图就是一个MGT，它表示了Tic-Tac-Toe游戏的前两步所有可能的步骤。Tic-Tac-Toe是一种简单的九宫格游戏，玩法是使用3*3的9个方格子，每人下一次看谁先连成一行3个，以下称ttt游戏。

我们注意到这棵树不同于其他的树结构，比如二叉树，2 3树以及堆树，根据游戏规则，一个MGT节点上可能有很多个子节点。

图中的树有三级，不过在编码中，极大极小树的级通常被称作层（级：level,层：ply）。在每一层中，“转换”开关指向另一个游戏者。

对一棵完整的极大极小树来说，计算机能够向前遍历每一步，直到找到最佳步骤为止。当然，正如你在例图中看到的那样，仅仅几个步骤也会令这棵树变得异常庞大，对于一台普通的计算机来说，预测五个步骤就足以令其迅速崩溃。因此，对于像国际象棋和围棋这样的大型博弈游戏来说，计算机程序不可能遍历所有结果，而是仅仅通过最上层的几个步骤来判断胜负。此外，程序员们也提出了很多算法和技巧来减少节点数目，比如阿尔法 贝塔剪枝算法（Alpha-Beta pruning），Negascout搜索算法以及MTD（全称是：Memory enhanced Test Driver，即记忆增强测试驱动）方法。

MGT当然不能预测所有计算机游戏的可能步骤。比如扑克游戏，计算机在判断对手动向的时候将会非常吃力，因为因为计算机不能看到对方手中的牌。因此，仅仅对于两个游戏者都能看到全部博弈形式的游戏来说，MGT才是最好的选择。这些游戏包括国际跳棋、五子棋、国际象棋和围棋，这些游戏被称作完全信息博弈（games of perfect information）。

极大极小博弈树是因描绘这种结构的一种简单算法而得名。我们来对ttt游戏的结果分配一下分值。如果叉（X）获胜，则分值为1。如果圈（O）获胜，则分值为-1。现在，叉将试图获得最大化的分值，而圈将试图最小化分值。于是，第一位研究此问题的研究者决定把游戏者叉命名为max，并且把游戏者圈命名为min。因此，这个完整的数据结构就被命名为极大（Max）极小（Min）博弈树。

极大极小逻辑也被用于其它博弈，比如国际象棋中。然而，在这些更复杂的博弈中，程序仅仅能搜索极大极小树中的一部分；由于树太过庞大，程序往往不能搜索到博弈最终的结局。计算机一般是搜索某几个节点之后就停止了。然后程序在某个节点上评估博弈的胜负，这些评估结果被换算成博弈形势的分值。如果计算机是max一方，程序会试图使博弈形势的分值最大化，同时为获胜结局（将死）赋最大值（比如说这个值是一百万）。如果计算机是min一方，显然程序将试图最小化分值，并为获胜结局赋最小分值（例如负一百万）。游戏双方将在两个最大值之间博弈，数值越接近哪一方则哪一方获利。

极大极小算法背后的策略假定参与博弈的游戏者都尽自己最大的努力获得好结果。因此，无论对方选择有利或有害的步骤，计算机都将会根据对手的着法选择最于己有利的步骤。

这个简单浅显的概念就是极大极小树的最大奥妙。比如，对max的程序来说，无论min怎么做，最佳的步骤或步骤序列一定会得到最高分值的结果。而min显然将选择那些让它获得最低分值的结果。

从某种意义上说，叶子节点（the?bottom?nodes，最下层节点）是唯一需要评估位置分值的节点，因为它们代表最终的结局。比如在max的博弈变化中，叶子节点始终处在同一位置。程序将假定min将从可能的步骤中选择最低分值的步骤行动，那么任何max节点的最大最小值都会等同于min节点的最低分值子节点。

最后，像人类的棋类游戏一样，程序的能力高低取决于计算机对所处形势的评估能力，以及程序搜索的深度。一位国际象棋大师对形势的估计误差要大大小于余位业余选手，而且象棋大师对于棋局的预测也远比一般人更远。计算机同样也可以对棋局做出很长远的预测，并且它着棋不会失误，因为它会看到对手由于失误而做出的回应。

有很多算法可以帮助极大极小算法提高搜索效率。其中一种被称作阿尔法贝塔剪枝算法。在使用这种算法进行的搜索中，计算机所要搜索的节点数大约只是不使用这种技术所需搜索节点数的平方根那么多。也就是说，如果程序原来需要搜索四百个节点，使用新的算法后它只需要搜索二十个。

其它的一些工具包括置换表（Transposition?table），记载搜索结果的纪录被放在一张可以快速存取的很小的表中。通常来说，不同的步骤序列可能达到相同的位置（结果）。这两个位置（结果）就可以互换。该表可以帮助计算机认识目前棋局的形势，因为它已经付出了内存存取时间的代价对其进行了审查。

同时，这些技术也允许计算机搜索更多的节点，并模拟策略思考。尽管其它的技术也开始崭露头角（比如神经网络），但极大极小树仍然是该类程序的最佳心脏。

极大极小博弈树(Minimax Game Tree)用于编写电脑之间的游戏程序，这类程序由两个游戏者轮流，每次执行一个步骤。当然，所有可能的步骤构成了一个树的结构。例如下面的图就是一个MGT，它表示了Tic-Tac-Toe游戏的前两步所有可能的步骤。

在每一层中的节点通常代表不同游戏者的选择，这两个游戏者通常被称作马克思（MAX）和米恩（Min）。

例如如果第二层是Max turn，则第三层就是Min turn，第二层的每个节点就是Max的choice，它们之间是或的关系，第三层的每个节点就是Min的choice，它们之间是与的关系。根据这个树，Max要做出的选择就让下次Min做出的任意选择都最小，即Minimax这个词的含义，极小化对手的最大收益。所以它不同于Maximin最大化自己的收益。

因为往往一局要下到最后才能分出胜负，而Game Tree上nodes的增长是以指数方式的，比如深蓝（Deep Blue）可以搜索12步，假设各方每步都有10种选择，那么一次的搜索量也有1万亿次，所以对于普通的电脑能够搜索到4步也有1万次了，所以就需要一个评分系统，对局面进行打分，考虑到是双人对战，则评分从负无穷到正无穷。所以马克思就是要找到一个最大的分数，而米恩就是要找到一个最小的分数。

下面用一个例子来说明，Tic-Tac-Toe游戏。

其中'o'代表PC，'x'代表玩家。其中有三个主要的函数：

int minSearch( char _board[9] )
int maxSearch( char _board[9] )
int gameState(char _board[9])

分别扮演max和min的角色，寻找最大和最小值，以及一个评分函数。

下面重点说说这个游戏的核心部分，gameState评分函数：

连三          100分
双连二       50分
平局          0分
不分胜负     1

其中如果评分时不分胜负则还会继续搜索，直到找到其他三种状态。

最后附上源码：

int gameState(char _board[9])
{
	int state;
	static int table[][3] = 
	{
		{0, 1, 2},
 		{3, 4, 5},
  		{6, 7, 8},
 		{0, 3, 6},
  		{1, 4, 7},
  		{2, 5, 8},
  		{0, 4, 8},
  		{2, 4, 6},
  	};
	char chess = _board[0];
 	for (char i = 1; i < 9; ++i)
  	{
 		chess &= _board[i];
 	}
  	bool isFull = 0 != chess;
 	bool isFind = false;
	for (int i = 0; i < sizeof(table) / sizeof(int[3]); ++i)
	{
		chess = _board[table[i][0]];
  		int j;
		for (j = 1; j < 3; ++j)
			if (_board[table[i][j]] != chess)
				break;
			if (chess != empty && j == 3)
			{
				isFind = true;        
				break;
			}
		}
		if (isFind)
			//got win or lose
			state = chess == o ? WIN : LOSE;
		else
		{
			if (isFull)
				//all position has been set without win or lose
				return DRAW;
			else
			{
				//finds[0] -> 'o', finds[1] -> 'x'
				int finds[2] = {0, };
				for (int i = 0; i < sizeof(table) / sizeof(int[3]); ++i)
				{
					bool findEmpty = false;
					chess = 0xff;
					int j;
					for (j = 0; j < 3; ++j)
						if (_board[table[i][j]] == empty && !findEmpty)
							findEmpty = true;
						else
                         chess &= _board[table[i][j]];
                if ((chess == o || chess == x) && findEmpty)
                {
                    isFind = true;        
                    if (o == chess)
                         ++finds[0];
                     else
                        ++finds[1];
                 }
            }
             if (finds[0] > 1 && finds[1] < 1)
                 //2 'o' has been founded twice in row, column or diagonal direction
                 state = -(INFINITY / 2) * finds[0];
             else if (finds[1] > 1 && finds[0] < 1)
                 //2 'x' has been founded twice in row, column or diagonal direction
                 state = INFINITY / 2 * finds[1];
             else
                 //need to search more.
                 state = INPROGRESS;
         }
    }
     return state;
 }

本文地址：http://www.nowamagic.net/librarys/veda/detail/948，欢迎访问原出处。