极小化极大算法解释

Question

我正在查看 Minimax 算法的伪代码：

Function Minimax-Decision(state) returns an action
  ;inputs: state (current game state)
  ;'E' means element of, 'a' is the action
  return a E Actions(state) maximizing Min-Value(Result(a, state))

Function Max-Value(state) returns a utility value
  if Terminal-Test(state) then return Utility(state)
  v <-- -infinity
  for a, s in Successors(state) do v <-- Max(v, Min-Value(s))
  return v

Function Min-Value(state) returns a utility value
  if Terminal-Test(state) then return Utility(state)
  v <-- infinity
  for a, s in Successors(state) do v <-- Min(v, Max-Values(s))
  return v

我认为我知道Minimax算法是如何工作的。你从底部开始填充“分数”值，从效用分数开始向上填充。Max节点处的值为其子节点中的最大值，Min节点处��值为其子节点中的最小值。Max预测Min将始终尝试将Max置于下一轮中最糟糕的位置，并利用这一知识，Max尽可能地做出最佳移动。

因此，对于顺序为Max、Min、Max（来自顶部的图片）：

1）Max希望为自己找到最佳着法（最大效用），因此C1=5，C2=11，C3=8等；

2）Max预测Min会想把Max置于可能的最糟糕的位置（限制Max为最小效用），因此B1=5，B2=2，B3=3；

3）Max希望做出最佳的可能移动，因此A=B1=5。

关于伪代码让我感到困惑的是双重递归以及变量v的目的。有谁能为我解析一下吗？

感谢大家阅读！

- user1846359

Answer 1

我认为你可以通过对深度为d的树进行归纳证明来理解这段代码的作用。

对于深度为1的情况，只有一个节点，Min-Value和Max-Value都会返回该节点的效用值。

对于深度大于1的情况，首先考虑Min-Value。v一开始被赋值为无穷大，在第一次调用Min(v, Max-Value(s))时，由于此时是Max的回合，我们知道通过归纳可得该子节点的效用值是正确的，因此将v设置为该子节点的效用值（这个调用相当于一次赋值，因为v <= 无穷大）。在该程序中后续的Min(v, Max-Value(s))调用将计算传入节点的所有子节点的Max-Value(s)的最小值。因此，Min-Value最终计算出传入节点的所有子节点的效用值的最小值，即当Min轮到移动时，该节点对Min的价值。

Max-Value的论证与Min-Value类似，因此归纳告诉你，对于任何深度的树，Min-Value和Max-Value都会在轮到Max或Min移动并做出与该节点相关的选择时，返回给你传递给它们的节点的值。

你还可以通过归纳证明表明这段代码所做的与你所描述的等价。

因此，双重递归是因为它允许Max和Min在从叶子节点向上遍历树时交替进行，v是一个临时变量，用于计算树的所有子节点的最小或最大值。

- mcdowella