人工智能的最小最大算法

人工智能中的最小最大算法:

• Mini-max算法是一种递归或回溯算法，用于决策和博弈论。它为玩家提供了一个最佳的动作，假设对手也在玩最佳状态。
• Mini-Max算法使用递归来搜索游戏树。
• Min-Max算法主要用于AI中的游戏。如Chess，Checkers，tic-tac-toe，go和各种拖车玩家游戏。该算法计算当前状态的最小极大决策。
• 在该算法中，两个玩家玩游戏，一个叫做MAX，另一个叫做MIN。
• 当对手玩家获得最大利益时，两个玩家都会对抗它。
• 游戏的两个玩家都是彼此的对手，其中MAX将选择最大化值，MIN将选择最小化值。
• minimax算法执行深度优先搜索算法以探索完整的游戏树。
• minimax算法一直向下到树的终端节点，然后作为递归回溯树。

MiniMax算法的伪代码：

function minimax(node, depth, maximizingPlayer) is  
if depth ==0 or node is a terminal node then  
return static evaluation of node  

if MaximizingPlayer then      // for Maximizer Player  
maxEva= -infinity            
 for each child of node do  
 eva= minimax(child, depth-1, false)  
maxEva= max(maxEva,eva)        //gives Maximum of the values  
return maxEva  

else                         // for Minimizer player  
 minEva= +infinity   
 for each child of node do  
 eva= minimax(child, depth-1, true)  
 minEva= min(minEva, eva)         //gives minimum of the values  
 return minEva

初始调用：

Minimax(node, 3, true)

Min-Max算法的工作

• 使用示例可以容易地描述minimax算法的工作。下面举一个代表双人游戏的游戏树的例子。
• 在这个例子中，有两个玩家，一个叫做Maximizer，另一个叫做Minimizer。
• Maximizer将尝试获得最大可能分数，而Minimizer将尝试获得最低分数。
• 这个算法适用于DFS，因此在这个游戏树中，必须一直通过叶子到达终端节点。
• 在终端节点处，给出终端值，因此将比较这些值并回溯树，直到初始状态发生。以下是解决双人游戏树所涉及的主要步骤：

第1步： 在第一步中，算法生成整个游戏树并应用效用函数来获取终端状态的效用值。在下面的树形图中，下面来看看A是树的初始状态。假设Maximizer采用具有最坏情况初始值 = -无穷大的第一次转弯，并且Minimizer将采用具有最坏情况初始值=+无穷大的下一转弯。

第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步：现在轮到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算法的主要缺点是它对象棋，go等复杂游戏来说非常慢。这种类型的游戏有很大的分支因素，玩家有很多选择可以决定。minimax算法的这种限制可以通过我们在下一个主题中讨论的alpha-beta修剪来改进。