人工智能的最小最大算法
人工智能中的最小最大算法:
- 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修剪来改进。