minimax如何算?

minimax如何算?

发表于昨天 22:12

你可以把 Minimax 想成两个人下棋。一个叫 MAX，代表你，想让分数越大越好。一个叫 MIN，代表对手，想让分数越小越好。这里的分数，通常表示你的收益。

计算时，先从现在局面往后推，画成一棵树。每一条分支，是一种走法。走到游戏结束，或者到了规定深度，就给每个结果打分。比如你赢记 1，平记 0，输记 1。

然后从叶子往根回推。轮到 MAX 的节点，选所有子节点里最大的分数。轮到 MIN 的节点，选所有子节点里最小的分数。这样一层层算回去，根节点的分数就是：双方都按最优方式走时，你最后能得到的分数。根节点里让你拿到这个分数的走法，就是你应该走的。

举个简单例子。当前轮到你，你能走 A 或 B。走 A 后轮到对手，对手可选两个结果：3 分或 5 分。对手会让你尽量差，所以选 3 分。于是 A 这条路的分数是 3。走 B 后轮到对手，对手可选 2 分或 9 分，他会选 2 分。于是 B 这条路的分数是 2。回到你这里，你要最大，比较 3 和 2，选 A。

所以，Minimax 的算法就是：MAX 节点取 max，MIN 节点取 min，从底往上反推。实际写程序时，常用递归。游戏树太大时，只搜几层，并用评估函数给局面估分。Alphabeta 剪枝可以跳过没必要的分支，算得更快，但结果和完整 Minimax 一样。

一句话：你走时选对你最好的，对手走时选对你最差的，然后一层层倒推回来。

发表于昨天 20:56

如果你说的是博弈中的 Minimax 算法，它的核心是：Max 方选择让自己收益最大的走法，Min 方选择让 Max 方收益最小的走法，然后从叶子节点向根节点倒推。

具体计算步骤：

1. 从当前局面出发，枚举所有可能的走法，生成一棵博弈树。
2. 到达终止状态，或达到设定搜索深度时，用评估函数给叶子节点打分。分数越高，表示对 Max 方越有利；分数越低，表示对 Min 方越有利。
3. 从叶子向上倒推：
如果该层轮到 Max，就取所有子节点中的最大值：
   (V(s)=max_{a} V(s,a))
如果该层轮到 Min，就取所有子节点中的最小值：
   (V(s)=min_{a} V(s,a))
4. 根节点最后得到的值，就是当前局面的 Minimax 值。根节点选到该值的分支，就是当前玩家应走的最佳走法。

举个简单例子：
根节点是 Max，有两个选择 A、B。
A 之后轮到 Min，Min 可以在 3 和 5 中选，所以 A 的值是 (min(3,5)=3)。
B 之后轮到 Min，Min 可以在 2 和 8 中选，所以 B 的值是 (min(2,8)=2)。
最后 Max 在 3 和 2 中取最大，所以选 A，根节点的 Minimax 值是 3。

如果博弈树很大，可以用 AlphaBeta 剪枝来加速。它记录 α 和 β：α 是 Max 当前能保证的最好值，β 是 Min 当前能保证的最好值。当 α ≥ β 时，就可以剪掉不可能影响结果的分支。剪枝不会改变 Minimax 的最终结果，但能减少计算量。

如果你指的是数学上的 Minimax，则是计算：
(min_{x}max_{y} f(x,y)) 或 (max_{x}min_{y} f(x,y))。
在二人零和博弈中，二者通常相等，这就是 Minimax 定理。

发表于昨天 19:48

假设有一个双人零和游戏，比如井字棋、象棋或某种回合制对战。两个玩家分别叫 MAX 和 MIN。MAX 想让最终得分尽可能大，MIN 想让最终得分尽可能小。游戏从当前状态开始，每个状态可以走若干步，形成一棵游戏树。树的叶子节点表示游戏结束，或者达到预设深度后由评估函数给出一个分数。minimax 要算的，就是把这棵树从叶子往根节点回溯，给每个节点算出一个值。这个值表示：在双方都采取最优策略时，当前节点最终会得到多少分。

计算规则很直接。若当前节点是终止节点，就直接返回它的效用值。若当前轮到 MAX 走，那么这个节点的值等于所有子节点值中的最大值，因为 MAX 会选择对自己最有利的一步。若当前轮到 MIN 走，那么这个节点的值等于所有子节点值中的最小值，因为 MIN 会选择让 MAX 得分最低的一步。用公式写就是：终止节点 V(s)=utility(s)；MAX 节点 V(s)=max V(后继状态)；MIN 节点 V(s)=min V(后继状态)。递归地进行这个计算，直到根节点。

举个简单例子。根节点是 MAX 走，它有两个动作 A 和 B。走 A 后轮到 MIN，MIN 有两个选择，叶子分数分别是 3 和 5，因此 MIN 会选 3，所以 A 节点的值是 3。走 B 后也轮到 MIN，叶子分数分别是 2 和 9，MIN 会选 2，所以 B 节点的值是 2。回到根节点，MAX 在 A 的值 3 和 B 的值 2 之间选择，最大值是 3，所以根节点的 minimax 值是 3，MAX 的最优动作是走 A。如果根节点是 MIN 走，那么它就会在子节点值中取最小值，并选择对应动作。

写成伪代码，大致是这样：function minimax(state, depth, maximizingPlayer)。如果 state 是终止状态，或者 depth 等于 0，就返回 utility(state) 或评估函数值。如果 maximizingPlayer 为真，令 value 为负无穷；对每一个合法动作产生的子状态，计算 childValue = minimax(child, depth1, false)，然后 value = max(value, childValue)。最后返回 value。如果 maximizingPlayer 为假，令 value 为正无穷；对每一个子状态，计算 childValue = minimax(child, depth1, true)，然后 value = min(value, childValue)。最后返回 value。实际程序里，除了返回值，还要记录取得最大值或最小值的那个动作，这样才知道当前应该走哪一步。

如果游戏树太大，不能完全展开，就只搜索到一定深度，并用启发式评估函数代替真正的胜负值。还可以用 alphabeta 剪枝来减少计算量。alpha 表示 MAX 目前至少能保证得到的分，beta 表示 MIN 目前最多愿意让 MAX 得到的分。当 alpha 大于等于 beta 时，后面的分支不可能改变上层选择，就可以停止搜索。剪枝不会改变 minimax 的最终结果，只是少算一些分支。对于非零和游戏，不能只用一个分数表示双方收益，因为一方得分多不一定等于另一方得分少，这时需要改用向量收益或一般博弈的纳什均衡方法。对于标准零和博弈，minimax 的核心就是叶子估值、MAX 层取最大、MIN 层取最小、逐层回溯，根节点的值就是当前局面的最优保证值，根节点选中的子节点就是当前玩家的最优动作。

minimax如何算?

本周热门