minimax算法初探以及若干例子

字数统计: 2.3k字 | 阅读时长: 9分

2020-09-13

lc题目汇总64, leetcode428, 动态规划129, 博弈9, 搜索62

摘要: minimax 算法简介

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们来聊一下博弈问题。此前我们通过动态规划解决过不少博弈问题，参考文章博弈DP，也解决过非常困难的问题：【搜索难题】力扣913-猫和老鼠。

这些问题的解决过程都是基于一个称为 minimax 算法的框架，再配合其它算法（搜索、动态规划等）解决的。minimax 是二人有限零和博弈中的核心结论，最早由 1928 年冯诺依曼的相关论文提出并形成一门理论，后来经过多年发展，相关的概念和定理已经很完善，

本文我们看一下 minimax 算法，以及一些题目。算法背后的理论，包括问题的形式化描述，概念，定理和证明，涉及到一些分析、代数和优化方面的数学知识，以后我们再展开。

我们首先大致阐述一下 minimax 算法，并简要提一下其后续优化，即 $\alpha - \beta$ 剪枝。然后我们解决 843. 猜猜这个单词、之后再给出一些题目清单，均为 minimax + 搜索/动态规划/数学推导，可以集中刷题。

minimax 算法

Minimax算法是一种找出失败的最大可能性中的最小值的算法。

该算法是一个零总和算法：一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的方法，开始时总和为 0。

使用 minimax 算法解决博弈问题时，注意以下几点：

该算法的字面意思：让最大的情况最小。这里的最大一般是指，博弈中最不利的情况
该算法需要满足零和博弈：其中一方得到利益那么另一方就会失去利益，游戏利益的总和为0
该算法是一个树形结构的递归算法，每个节点的孩子和父节点都是对方玩家，所有的节点被分为极大值（我方）节点和极小值（对方）节点。

算法流程

int minimax(node, depth)
    if node is a terminal node or depth = 0
        return the heuristic value of node
    if the adversary is to play at node
        let alpha := +inf
        foreach child of node
            alpha := min(alpha, minimax(child, depth - 1))
    else // we are to play at node
        let alpha := -inf
        foreach child of node
            alpha := max(alpha, minimax(child, depth - 1))
    return alpha

minimax 算法的优化：$\alpha-\beta$ 剪枝

在上述的极大极小算法中，MIN 和 MAX 过程将遍历搜索树的所有的可能性，然后再从端点的估计值倒推计算，这样的效率非常低下。

而 $\alpha-\beta$ 算法的引入可以提高运算效率，对一些非必要的估计值进行舍弃。其策略是进行深度优先搜索，当生成结点到达规定深度时，立即进行静态估计，一旦某一个非端点的节点可以确定倒推值的时候立即赋值，节省下其他分支拓展到节点的开销。

剪枝规则：

（1）$\alpha$ 剪枝，任一极小层节点的 $\beta$ 值不大于他任一前驱极大值层节点的 $\alpha$ 值，即 $\alpha$（前驱层）≥ $\beta$（后继层），则可以终止该极小层中这个MIN节点以下的搜索过程。这个MIN节点的倒推值确定为这个 $\beta$ 值。

（2）$\beta$ 剪枝，任一极大层节点的 $\alpha$ 值不小于它任一前驱极小值层节点的 $\beta$ 值，即 $\beta$（前驱层）≤ $\alpha$（后继层），则可以终止该极大值层中这个MAX节点以下的搜索过程。这个MAX节点的倒推值确定为这个 $\alpha$ 值。

题目：843. 猜猜这个单词

给你一个由不同字符串组成的单词列表 words ，其中 words[i] 长度均为 6 。words 中的一个单词将被选作秘密单词 secret 。

另给你一个辅助对象 Master ，你可以调用 Master.guess(word) 来猜单词，其中参数 word 长度为 6 且必须是 words 中的字符串。

Master.guess(word) 将会返回如下结果：

如果 word 不是 words 中的字符串，返回 -1 ，或者
一个整数，表示你所猜测的单词 word 与秘密单词 secret 的准确匹配（值和位置同时匹配）的数目。

每组测试用例都会包含一个参数 allowedGuesses ，其中 allowedGuesses 是你可以调用 Master.guess(word) 的最大次数。

对于每组测试用例，在不超过允许猜测的次数的前提下，你应该调用 Master.guess 来猜出秘密单词。最终，你将会得到以下结果：

如果你调用 Master.guess 的次数大于 allowedGuesses 所限定的次数或者你没有用 Master.guess 猜到秘密单词，则得到 “Either you took too many guesses, or you did not find the secret word.” 。
如果你调用 Master.guess 猜到秘密单词，且调用 Master.guess 的次数小于或等于 allowedGuesses ，则得到 “You guessed the secret word correctly.” 。

生成的测试用例保证你可以利用某种合理的策略（而不是暴力）猜到秘密单词。

提示：

1 <= words.length <= 100
words[i].length == 6
words[i] 仅由小写英文字母组成
words 中所有字符串 互不相同
secret 存在于 words 中
10 <= allowedGuesses <= 30

示例 1：
输入：secret = “acckzz”, words = [“acckzz”,”ccbazz”,”eiowzz”,”abcczz”], allowedGuesses = 10
输出：You guessed the secret word correctly.
解释：
master.guess(“aaaaaa”) 返回 -1 ，因为 “aaaaaa” 不在 words 中。
master.guess(“acckzz”) 返回 6 ，因为 “acckzz” 是秘密单词 secret ，共有 6 个字母匹配。
master.guess(“ccbazz”) 返回 3 ，因为 “ccbazz” 共有 3 个字母匹配。
master.guess(“eiowzz”) 返回 2 ，因为 “eiowzz” 共有 2 个字母匹配。
master.guess(“abcczz”) 返回 4 ，因为 “abcczz” 共有 4 个字母匹配。
一共调用 5 次 master.guess ，其中一个为秘密单词，所以通过测试用例。

示例 2：
输入：secret = “hamada”, words = [“hamada”,”khaled”], allowedGuesses = 10
输出：You guessed the secret word correctly.
解释：共有 2 个单词，且其中一个为秘密单词，可以通过测试用例。

算法：minimax

这是一个交互式问题，流程大致如下。

step1: 选择一个词 word 猜：

1	int i = findNext(sim, candidates);

step2: 相似性为 state (0~6)，即 word 与 target 有 state 个字符一样，6-state 个字符不一样：

1	int s = master.guess(wordlist[i]);

step3: 下一个词 nxt，nxt 与 state 不匹配的数目必须为 6 - state，将不满足的标记删除：

for (int j = 0; j < N; ++j) {
    if (candidates[j] && sim[j][i] != s) {
        candidates[j] = false;
    }
}

step4: 选择 nxt，尽量保证后续的可行集最小。具体做法如下：

对每个未排除的词，记录一个 cnt 数组，cnt[i] := 其它未排除的词中与该词相似性为 i 的单词个数。

这里 minimax 算法体现在：从未排除的词中选择使得 cnt 数组的最大值最小的那个单词。选择过程的代码如下：

int findNext(const vector<vector<int> >& sim, const vector<bool>& candidates) {
    int N = candidates.size();
    int mn = INT_MAX;
    int mn_ind = -1;
    for (int i = 0; i < N; ++i) {
        if (!candidates[i]) continue;
        vector<int> counts(6, 0);
        for (int j = 0; j < N; ++j) {
            if (j == i || !candidates[j]) continue;
            ++counts[sim[i][j]];
        }
        int mx = *max_element(counts.begin(), counts.end());
        if (mx < mn) {
            mn = mx;
            mn_ind = i;
        }
    }
    return mn_ind;
}

代码 (C++)

class Solution {
public:
    void findSecretWord(vector<string>& wordlist, Master& master) {
        int N = wordlist.size();
        vector<vector<int> > sim(N, vector<int>(N, 0)); // sim[i][j] 是两个词之间匹配的字母数
        for (int i = 0; i < N; ++i) {
            sim[i][i] = 6;
            for (int j = i + 1; j < N; ++j) {
                sim[i][j] = sim[j][i] = _calSim(wordlist[i], wordlist[j]);
            }
        }
        vector<bool> candidates(N, true);
        while (true) {
            int i = findNext(sim, candidates);
            int s = master.guess(wordlist[i]);
            if (s == 6) return;
            for (int j = 0; j < N; ++j) {
                if (candidates[j] && sim[j][i] != s) {
                    candidates[j] = false;
                }
            }
        }
    }

private:
    int _calSim(const string& s1, const string& s2) {
        int res = 0;
        for (int i = 0; i < 6; ++i) {
            res += s1[i] == s2[i];
        }
        return res;
    }

    int findNext(const vector<vector<int> >& sim, const vector<bool>& candidates) {
        int N = candidates.size();
        int mn = INT_MAX;
        int mn_ind = -1;
        for (int i = 0; i < N; ++i) {
            if (!candidates[i]) continue;
            vector<int> counts(6, 0);
            for (int j = 0; j < N; ++j) {
                if (j == i || !candidates[j]) continue;
                ++counts[sim[i][j]];
            }
            int mx = *max_element(counts.begin(), counts.end());
            if (mx < mn) {
                mn = mx;
                mn_ind = i;
            }
        }
        return mn_ind;
    }
};

题目清单

下面是 minimax 算法的题目清单，解决方案均为 minimax + 搜索/动态规划/数学推导。

292. Nim 游戏

minimax + 数学推导

294. 翻转游戏 II

minimax + 记忆化搜索

464. 我能赢吗

minimax + 状态压缩DP

375. 猜数字大小 II

minimax + 区间DP

486. 预测赢家

minimax + 区间dp
minimax + alpha-beta剪枝

877. 石子游戏

minimax + 线性DP

913. 猫和老鼠

minimax + 染色BFS
minimax + 记忆化搜索

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

数博弈