人工智能中的极小极大算法

• Mini-max 算法是一种递归或回溯算法，用于决策和博弈论。假设对手也在以最佳方式进行游戏，它为玩家提供了最佳移动。

• Mini-Max 算法使用递归来搜索游戏树。

• Min-Max 算法主要用于 AI 中的游戏。如国际象棋、跳棋、井字棋、围棋和各种拖车游戏。该算法计算当前状态的极小极大决策。

• 在这个算法中，两个玩家玩游戏，一个叫做 MAX，另一个叫做 MIN。

• 双方玩家进行战斗，因为对手玩家获得的收益最小，而他们获得的收益最大。

• 游戏中的两个玩家是彼此的对手，其中 MAX 将选择最大值，MIN 将选择最小值。

• minimax 算法执行深度优先搜索算法来探索完整的博弈树。

• 极小极大算法一直进行到树的终端节点，然后作为递归回溯树。

MinMax算法的伪代码：

function minimax(node, depth, maximizingPlayer) is  
if depth ==0 or node is a terminal node then  
return static evaluation of node  
  
if MaximizingPlayer then       // 用于Maximizer Player  
maxEva= -infinity            
 for each child of node do  
 eva= minimax(child, depth-1, false)  
maxEva= max(maxEva,eva)        //给出值的最大值  
return maxEva  
  
else    // 用于最小化播放器  
 minEva= +infinity   
 for each child of node do  
 eva= minimax(child, depth-1, true)  
 minEva= min(minEva, eva)         //给出最小值  
 return minEva

初始调用：

极小极大（节点，3，真）

Min-Max 算法的工作原理：

• 使用一个例子可以很容易地描述极小极大算法的工作。下面我们举了一个游戏树的例子，它代表了两人游戏。

• 在此示例中，有两个播放器，一个称为 Maximizer，另一个称为 Minimizer。

• Maximizer 将尝试获得最大可能的分数，而 Minimizer 将尝试获得最低可能的分数。

• 这个算法应用了 DFS，所以在这个博弈树中，我们必须一直通过叶子到达终端节点。

• 在终端节点，给出了终端值，因此我们将比较这些值并回溯树，直到出现初始状态。以下是解决两人博弈树的主要步骤：

Step-1：第一步，算法生成整个博弈树并应用效用函数来获取终端状态的效用值。在下面的树图中，我们假设 A 是树的初始状态。假设最大化器进行第一轮，其具有最坏情况的初始值 =-无穷大，而最小化器将进行下一轮，其具有最坏情况的初始值 = +无穷大。

步骤2：现在，首先我们找到Maximizer 的效用值，它的初始值为-∞，因此我们将终端状态的每个值与Maximizer 的初始值进行比较，并确定较高的节点值。它将在所有中找到最大值。

• 对于节点 D max(-1,- -∞) => max(-1,4)= 4

• 对于节点 E max(2, -∞) => max(2, 6)= 6

• 对于节点 F max(-3, -∞) => max(-3,-5) = -3

• 对于节点 G max(0, -∞) = max(0, 7) = 7

步骤3：在接下来的步骤，它是最小化器转一转，所以它会比较+∞的所有节点值，并且将发现3^次层节点的值。

• 对于节点 B= min(4,6) = 4

• 对于节点 C= min (-3, 7) = -3

Step 4：现在轮到Maximizer，它会再次选择所有节点值的最大值，并为根节点找到最大值。在这个游戏树中，只有 4 层，因此我们立即到达根节点，但在实际游戏中，会超过 4 层。

• 对于节点 A max(4, -3)= 4

这就是 minimax 两人游戏的完整工作流程。

Mini-Max 算法的特性：

• Complete -Min-Max 算法完成。它肯定会在有限搜索树中找到解决方案（如果存在）。

• Optimal -Min-Max 算法是最优的，如果两个对手都玩得最好。

• 时间复杂度-由于它对博弈树执行 DFS，所以 Min-Max 算法的时间复杂度为O(b ^m )，其中 b 是博弈树的分支因子，m 是树的最大深度。

• 空间复杂度- Mini-max 算法的空间复杂度也类似于 DFS，为O(bm)。

极大极小算法的局限性：

minimax 算法的主要缺点是对于复杂的游戏，如国际象棋、围棋等，它变得非常慢。这种类型的游戏具有巨大的分支因子，玩家有很多选择来决定。minimax 算法的这种限制可以通过我们在下一个主题中讨论的alpha-beta 剪枝来改进。