首页 文章

Minimax算法解释

提问于
浏览 次
4

我正在寻找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的目的 . 有人可以为我打破这个吗？

感谢大家阅读！

algorithm search tree minimax

1 回答

  • 3

    我认为你可以通过感应非正式证明来理解这个代码，它适用于深度为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是一个临时用于计算树的所有子节点的最小值或最大值 .

    回复于

相关问题