Minimax算法解释

我正在寻找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从顶部
enter image description here

1)马克斯想为自己做最好的动作(最大效用),所以C1 = 5,C2 = 11,C3 = 8等

2)Max预测Min将要将Max置于可能的最差位置(限制Max到最小效用),因此B1 = 5,B2 = 2,B3 = 3

3)Max想要做出最好的移动,所以A = B1 = 5

关于伪代码让我感到困惑的是双递归和v的目的 . 有人可以为我打破这个吗?

感谢大家阅读!

回答(1)

2 years ago

我认为你可以通过感应非正式证明来理解这个代码,它适用于深度为d的树 .

对于深度1,您只有一个节点,Min-Value和Max-Value都返回此节点的实用程序 .

对于深度d> 1,首先考虑最小值 . v从无穷远开始,所以在第一次调用Min(v,Max-Value(s))时,v被设置为子节点的效用,由Max计算,因为它在Min之后是Max,我们知道感应是正确的,因为它的深度为d-1 . (此调用相当于赋值,因为v <=无穷大),稍后调用此例程中的Min(v,Max-Value(s))最终计算通过的节点的所有子节点的最大值最小值因此,Min-Value最终计算传入的节点的所有子节点的最小效用,这是该节点在Min移动时的值 .

最大值的参数与最小值非常相似,因此感应告诉您,对于任何深度的树,Min-Value和Max-Value都会返回传递给它们的节点的值,轮到Max或Min移动并做出与该节点相关的选择 .

您还可以通过归纳显示此代码所执行的操作等同于您所描述的内容 .

因此,双重递归的产生是因为它允许Max和Min在从树上向上走树时采取交替转弯,而v是一个临时用于计算树的所有子节点的最小值或最大值 .