OI-wiki 零和博弈全解从序贯 Minimax 到同时博弈的混合策略与线性规划求解【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki零和博弈zero-sum game是博弈论与算法竞赛的交叉核心两名玩家的收益之和恒为零一方的收益必然是另一方的损失。本文以 OI-wiki 的 零和博弈文档 为骨架系统讲解序贯零和游戏的 Minimax 递推与实战优化、同时零和游戏的收益矩阵与混合策略并完整推导 von Neumann 极小化极大定理及其向线性规划的转化。读完本文你将掌握用动态规划、记忆化搜索、Alpha–Beta 剪枝解决序贯博弈题以及用线性规划求解一般同时零和博弈最优混合策略的完整方法论。前置知识零和博弈在博弈论中的定位在 OI-wiki 的博弈论体系中博弈论简介 定义了基础概念框架零和博弈zero-sum game指无论各方采取何种行为所有参与者的收益总和始终为零的博弈通常讨论的二人零和博弈中一方的收益必然是另一方的损失。与之相对的是非零和博弈含正和、负和博弈。零和游戏可以视为常和游戏的特殊情形——任何常和游戏都可以通过对某一方的收益整体加上或减去一个常数等价地转化为零和游戏因此仅需要讨论零和游戏即可覆盖更广的问题。同时博弈按行动方式可分为同时博弈simultaneous game如剪刀石头布与序贯博弈sequential game玩家依次行动、后行动者能观察到部分先行动者的行为。本文讨论的二人零和游戏在算法竞赛中大致对应这两类序贯零和游戏与同时零和游戏。前者用博弈树刻画、以 Minimax 思想求解后者用收益矩阵刻画、以混合策略和线性规划求解。序贯零和游戏Minimax 递推收益函数的递归结构序贯零和游戏中两名玩家轮流行动直到游戏终止收益函数呈现递归结构。游戏局面 $S$ 可分为三类终止局面 $S_0$、玩家 $1$ 行动的局面 $S_1$、玩家 $2$ 行动的局面 $S_2$。假设终止局面 $s\in S_0$ 处玩家 $1$ 的收益为 $v(s)$则玩家 $2$ 的收益为 $-v(s)$——轮到玩家 $2$ 行动时最大化自身收益等价于最小化玩家 $1$ 的收益。由此假设双方都采取最优策略玩家 $1$ 在局面 $s\in S$ 处能获得的最大收益 $V(s)$ 满足如下递推$$ V(s) \begin{cases} v(s), s \in S_0,\ \max_{t\in s} V(t), s\in S_1,\ \min_{t\in s} V(t), s\in S_2. \end{cases} $$其中 $t\in s$ 表示 $t$ 是 $s$ 的后继局面。这正是 Minimax 算法极小化极大思想 的核心——在搜索树中我方MAX节点取子节点分数最大值对方MIN节点取子节点分数最小值回溯得到根节点在双方最优策略下的分数。四个实战方法论将这一算法应用于实际问题根据局面规模与结构有四种典型方法局面数量较少直接暴力实现该递推即可。局面数量庞大且无特殊结构考虑 Alpha–Beta 剪枝 并结合其他搜索剪枝算法。Alpha–Beta 剪枝维护 $\alpha$我方分数下界与 $\beta$对方分数上界两个变量当 $\alpha\ge\beta$ 时剪掉当前节点剩余分支从而在不改变搜索结果的前提下大幅减少搜索量。单个局面频繁作为多个局面的后继为避免重复搜索采用记忆化搜索或其他动态规划算法将每个局面的 $V(s)$ 只计算一次。收益是全程行动的收益和可以优化建模方式。设到达终局 $s\in S_0$ 时玩家 $i1,2$ 的行动序列分别为 ${a^{(i)}j}{j1}^{k_i}$行动 $a$ 对应收益 $w(a)$玩家 $1$ 的收益函数为$$ v(s) \sum_{j1}^{k_1}w(a_j^{(1)}) - \sum_{j1}^{k_2}w(a_j^{(2)}). $$此时可以设 $\tilde V(s)$ 为当前玩家在局面 $s\in S$ 之后的游戏中能取得的最大分数不再固定以玩家 $1$ 为收益主体而是站在轮到谁行动的视角。对于初始状态 $s_0$ 有 $V(s_0)\tilde V(s_0)$因此求 $\tilde V(\cdot)$ 足以求解原问题。$\tilde V(\cdot)$ 满足更简洁的递推$$ \tilde V(s) \begin{cases} 0, s \in S_0, \ \max_{t\in s} w(a_{s\to t}) - \tilde V(t), s\in S_1\cup S_2. \end{cases} $$其中 $a_{s\to t}$ 表示能使状态从 $s$ 转移到 $t$ 的行动若有多个这样的行动取收益 $w(a)$ 最高的那个。这一当前玩家视角的建模在取石子、棋盘博弈类题目中极为常用。与公平组合游戏的联系公平组合游戏都是序贯零和游戏只需设胜利方收益 $1$、失败方收益 $-1$。此时 $V(\cdot)$ 的递推关系正是 公平组合博弈 中判定必胜状态$\mathcal N$ 态和必败状态$\mathcal P$ 态的引理——没有后继状态的状态是必败状态一个状态必胜当且仅当存在至少一个必败后继一个状态必败当且仅当所有后继均为必胜。这从零和博弈的角度统一了 Sprague–Grundy 理论 所依赖的必胜/必败判定基础。这类问题还有一个常见变形求胜利方最少需要的回合数、失败方最多能坚持的回合数。技巧在于从终止状态开始做 BFS 并按引理判定必胜/必败状态时记录判定各状态胜负时 BFS 进行的轮次数即为所求回合数。原因在于判定为必胜状态只需要一个必败后继它总是由后继状态中轮次数最小的必败状态转移而来判定为必败状态需要所有后继均为必胜它总是由后继状态中轮次数最大的必胜状态转移而来。这一方法同样可以推广到一般的有向图游戏。例题精讲Codeforces 794 E. Choosing Carrot设有一个长度为 $n$ 的数列 ${a_i}$。两名玩家轮流从数列两端取走一个数直到数列仅剩最后一个数字。玩家 $1$ 的目标是最大化这个最后剩下的数字玩家 $2$ 的目标是最小化它。游戏开始前玩家 $1$ 还可先进行 $k$ 次行动。对每个 $k0,1,\dots,n-1$求双方最优策略下最后剩下的数字。数据范围 $1\le n\le 3\times10^5$。分析无论双方如何取数剩余部分总是一段完整区间 $[l,r]$局面可由区间和当前行动玩家 $i1,2$ 描述。设 $f(l,r,i)$ 为局面 $(l,r,i)$ 下游戏最后剩下的数字当 $lr$ 时满足$$ \begin{aligned} f(l,r,1) \max{f(l1,r,2),f(l,r-1,2)},\ f(l,r,2) \min{f(l1,r,1),f(l,r-1,1)}. \end{aligned} $$终值条件 $f(l,l,1)f(l,l,2)a_l$。朴素区间 DP 为 $\Theta(n^2)$无法通过原题数据范围需要优化。优化思路将转移看作对数列整体操作两个转移方程分别对应将相邻数字取最大值/最小值得到新数列称为「最大化操作」和「最小化操作」每次操作使数列长度减一。长度为 $d$ 的区间对应结果共 $(n-d1)$ 个等价于对序列做 $(d-1)$ 次操作得到的序列且 $f(l,r,1)$ 要求最后一次操作是最大化操作。考察连续两次操作的效果先做最小化再做最大化数列 $a_1,a_2,a_3$ 变为$$ \max{\min{a_1,a_2},\min{a_2,a_3}}. $$枚举三者大小关系可知除 $a_2$ 为严格极大值的情形外该式恒等于 $a_2$。也就是说若数列不存在严格极大值点连续两次操作的效果就是删去数列首尾各一个数字。而只要对序列做一次最大化操作就能保证不存在严格极大值点。因此所有偶数次操作的结果可通过对初始数列做两次操作得到的序列逐对删去首尾数字得到所有奇数次操作的结果可通过做一次操作得到的序列逐对删去首尾数字得到。完整操作至多只需 $3$ 次统计答案只需 $2$ 次遍历总复杂度降为 $\Theta(n)$。仓库中的参考代码位于 docs/math/code/zero-sum-game/zero-sum-game-1.cpp核心实现如下#include algorithm #include iostream #include vector int main() { int n; std::cin n; std::vectorint a(n); for (int x : a) std::cin x; std::vectorint ans(n), tmp; tmp a; for (int i 0; i n - 1; i) { tmp[i] std::max(tmp[i], tmp[i 1]); } for (int l n / 2 - 1, r (n - 1) / 2, ma 0; l 0; --l, r) { ma std::max({ma, tmp[l], tmp[r]}); ans[r - l] ma; } tmp a; for (int i 0; i n - 1; i) { tmp[i] std::min(tmp[i], tmp[i 1]); } for (int i 0; i n - 2; i) { tmp[i] std::max(tmp[i], tmp[i 1]); } for (int l (n - 3) / 2, r n / 2 - 1, ma 0; l 0; --l, r) { ma std::max({ma, tmp[l], tmp[r]}); ans[r - l] ma; } ans[n - 1] *std::max_element(a.begin(), a.end()); for (auto x : ans) std::cout x ; std::cout std::endl; return 0; }代码结构印证了上文优化第一段用一次最大化操作后的序列逐对删去首尾处理偶数长度区间第二段用最小化最大化两次操作后的序列处理奇数长度区间ans[n-1]对应整段数列的最终值。仓库中还提供了对应测试数据 zero-sum-game-1.in输入4与数列1 2 3 5及期望输出 zero-sum-game-1.ans3 3 5 5可直接运行验证。序贯零和游戏习题Luogu P2734 USACO3.3 游戏 A GameLuogu P4576 CQOI2013 棋盘游戏Luogu P7097 yLOI2020 牵丝戏Codeforces 388 C. Fox and Card GameCodeforces 794 E. Choosing CarrotCodeforces 1628 D2. Game on Sum (Hard Version)Luogu P3210 HNOI2010 取石头游戏同时零和游戏收益矩阵表示同时零和博弈中两名玩家同时行动通常用收益矩阵表示。设玩家 $i1,2$ 的行动集合为 $A_i$当双方分别采取行动 $a_i\in A_i$ 时收益分别为 $v(a_1,a_2)$ 和 $-v(a_1,a_2)$。以石头剪刀布为例胜利得 $1$ 分、失败得 $-1$ 分、平局得 $0$ 分收益表为$$ \begin{pmatrix} 0,0 1,-1 -1,1 \ -1,1 0,0 1,-1 \ 1,-1 -1,1 0,0 \end{pmatrix}. $$一般的二人同时游戏都可表示为类似形式故也称双矩阵游戏bimatrix game。对零和博弈玩家 $1$ 与玩家 $2$ 的收益矩阵互为相反数因此只需考虑玩家 $1$ 的收益矩阵$$ V (v(a_1,a_2))_{(a_1,a_2)\in A_1\times A_2} \begin{pmatrix} 0 1 -1 \ -1 0 1 \ 1 -1 0 \end{pmatrix}. $$要解决的问题是给定收益矩阵 $V$如何求出两名玩家的最优策略和最大收益为什么纯策略分析不够序贯视角的局限既然已经解决了序贯零和游戏一个自然的想法是把同时游戏看成它的序贯版本。若假定玩家 $1$ 先行动、玩家 $2$ 后行动那么游戏结束时玩家 $1$ 的收益由$$ w_-\max_{a_1\in A_1}\min_{a_2\in A_2} v(a_1,a_2) $$给出——玩家 $1$ 的行动对玩家 $2$ 单向透明这是玩家 $1$ 能获得的最差结果。对称地若玩家 $2$ 先行动玩家 $1$ 的收益为$$ w_ \min_{a_2\in A_2}\max_{a_1\in A_1} v(a_1,a_2) $$——这是玩家 $1$ 能获得的最好结果。玩家 $1$ 应期待实际收益 $w\in[w_-,w_]$。尽管不等式 $w_-\le w_$ 总是成立证明参见 线性规划的对偶原理但等号未必成立因此仅采用序贯分析无法唯一确定同时游戏的结果。石头剪刀布中如果出手有先后先手必输、后手必赢对应 $w_--1\le1w_$恰为等号不成立的例子。上述分析遗漏了同时游戏的关键因素玩家无法准确预测对手的行动这意味着双方可以采取随机策略。这一想法在序贯博弈中不成立——无论先手如何随机后手总能观测到具体行动并有针对性地回应但在同时游戏中随机策略引入的战略模糊使对手无法有效针对。仍以石头剪刀布为例若玩家 $1$ 均匀随机地选择剪刀、石头、布则按玩家 $2$ 的不同行动玩家 $1$ 的期望收益为$$ \dfrac{1}{3}(0,1,-1)^T \dfrac{1}{3}(-1,0,1)^T \dfrac{1}{3}(1,-1,0)^T (0,0,0)^T, $$无论玩家 $2$ 如何行动期望收益恒为 $0$显然优于确定性选择单个行动。混合策略由此引入混合策略mixed strategy概念同时游戏中玩家 $i$ 的混合策略是指函数 $s_i:A_i\to[0,1]$且满足 $\sum_{a_i\in A_i}s_i(a_i)1$——即行动集合 $A_i$ 上的一个概率分布。玩家 $i$ 全体混合策略的集合记作 $S_i\Delta(A_i)$。若 $s_i$ 是退化的概率分布存在 $a\in A_i$ 使 $s_i(a)1$则称其为纯策略pure strategy。混合策略的收益就是各行动收益的期望$$ v(s_1,s_2) \sum_{a_1\in A_1}\sum_{a_2\in A_2}s_1(a_1)s_2(a_2)v(a_1,a_2). $$将单个行动看作对应的纯策略行动集合 $A_i$ 就嵌入到策略集合 $S_i$ 中上式将 $v(a_1,a_2)$ 从 $A_1\times A_2$ 延拓到 $S_1\times S_2$ 上。von Neumann 定理极小化极大与极大化极小的统一引入混合策略后极大化极小思想与极小化极大思想得到的结果一致同时零和游戏的结果被唯一确定。这就是经典的 von Neumann 定理定理von Neumann允许混合策略的同时零和游戏中若双方都采取最优策略玩家 $1$ 的最大收益为$$ w \max_{s_1\in S_1}\min_{s_2\in S_2} v(s_1,s_2) \min_{s_2\in S_2}\max_{s_1\in S_1} v(s_1,s_2), $$玩家 $2$ 的最大收益为 $-w$。证明要点原文给出了完整推导设 $w \max_{s_1}\min_{s_2}v(s_1,s_2)$。由 $v(s_1,s_2)\sum_{a_2}s_2(a_2)v(s_1,a_2)$ 可知内层最小化问题的最优解可由纯策略达到即 $w\max_{s_1\in S_1}\min_{a_2\in A_2}v(s_1,a_2)$。引入辅助变量 $u$ 后改写为约束优化问题并结合混合策略的定义与收益函数表达式等价于线性规划问题 (P)$$ (P) \qquad \begin{aligned} w \max_{u,s_1}; u\ \text{subject to } \sum_{a_1\in A_1}s_1(a_1)v(a_1,a_2) \ge u,~\forall a_2\in A_2,\ \sum_{a_1\in A_1}s_1(a_1) 1,\ s_1(a_1) \ge 0,~\forall a_1\in A_1. \end{aligned} $$该问题可行且有最优解。根据 对偶原理其最优解等于对偶问题 (D) 的最优解$$ (D) \qquad \begin{aligned} w \min_{t,s_2}; t\ \text{subject to }\sum_{a_2\in A_2}s_2(a_2)v(a_1,a_2) \le t,~\forall a_1\in A_1,\ \sum_{a_2\in A_2}s_2(a_2) 1,\ s_2(a_2)\ge 0,~\forall a_2\in A_2. \end{aligned} $$重复前述步骤(D) 等价于 $\min_{s_2}\max_{s_1}v(s_1,s_2)$定理得证。这一结果正是该游戏的Nash 均衡假定双方都选择均衡中的最优策略没有任何玩家能从偏离均衡策略中严格获益。转化为线性规划具体求解方法von Neumann 定理的证明同时指出了求解方法。设 $n$、$m$ 分别为玩家 $1$、$2$ 的可行动作数目给定玩家 $1$ 的收益矩阵 $V\in\mathbf R^{n\times m}$求解如下线性规划$$ \begin{aligned} w \max_{(u,s)\in\mathbf R\times\mathbf R^n}; u\ \text{subject to } V^Ts \ge u\mathbf 1,\ \mathbf 1^Ts 1,\ s \ge 0. \end{aligned} $$这是一个规模为 $\Theta(nm)$ 的线性规划问题可用 单纯形法 高效求解。算法得到的最优解 $s$ 就是玩家 $1$ 的最优混合策略玩家 $2$ 的最优策略只需从单纯形表中获得该问题最优解的**对偶变量影子价格**即可。实操要点收益矩阵 $V$ 的每一行对应玩家 $1$ 的一个行动、每一列对应玩家 $2$ 的一个行动约束 $V^Ts\ge u\mathbf 1$ 保证无论玩家 $2$ 怎么选玩家 $1$ 的期望收益都不低于 $u$$\mathbf 1^Ts1$ 与 $s\ge 0$ 保证 $s$ 是概率分布。若 $V$ 中存在负数元素需按线性规划惯例平移矩阵保证变量非负约束的可行性配合对偶问题的影子价格读取玩家 $2$ 的策略。同时零和游戏习题Luogu P4232 无意识之外的捉迷藏参考资料与注释原文依据均为仓库内文档博弈论简介零和/非零和博弈、同时/序贯博弈、完美/完全信息等基础概念公平组合博弈必胜/必败状态引理、有向图游戏与 BFS 轮次判定Minimax 算法与 Alpha–Beta 剪枝序贯零和博弈的搜索理论基础线性规划对偶原理与线性规划问题的形式化单纯形法线性规划的高效求解算法零和博弈参考代码 及 测试数据、期望输出外部学术背景原文引用的文献主题Zero-sum game 与 Minimax theorem 的数学定义可参见维基百科对应条目双矩阵游戏bimatrix game与 Nash 均衡的概念可参见博弈论标准教材。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考