跳转至

# 零和游戏

前置知识：博弈论简介

本文讨论（二人）零和游戏．

在零和游戏中，两名玩家的收益之和恒为零，一方的收益必然意味着另一方的损失．零和游戏可以视为常和游戏的特殊情形．不过，任何常和游戏都可以通过对某一方的收益整体加上或减去一个常数，等价地转化为零和游戏，所以仅需要讨论零和游戏．

在算法竞赛中常见的零和游戏大致可分为两类：序贯零和游戏与同时零和游戏．

## 序贯零和游戏

序贯零和游戏中，两名玩家轮流行动，直到游戏终止．

序贯零和游戏中，玩家的收益函数呈现递归结构．游戏局面 𝑆 S 可以分为三类，即终止局面 𝑆 0 S 0、玩家 1 1 行动的局面 𝑆 1 S 1 和玩家 2 2 行动的局面 𝑆 2 S 2．假设终止局面 𝑠 ∈𝑆 0 s∈S 0 处，玩家 1 1 的收益为 𝑣(𝑠)v(s)，相应地，玩家 2 2 的收益为 −𝑣(𝑠)−v(s)．因此，轮到玩家 2 2 行动时，最大化它的收益就相当于最小化玩家 1 1 的收益．由此，假设双方都采取最优策略，玩家 1 1 在局面 𝑠 ∈𝑆 s∈S 处能够获得的最大收益 𝑉(𝑠)V(s) 满足如下递推关系：

𝑉(𝑠)=⎧{ {⎨{ {⎩𝑣(𝑠),𝑠∈𝑆 0,m a x 𝑡∈𝑠 𝑉(𝑡),𝑠∈𝑆 1,m i n 𝑡∈𝑠 𝑉(𝑡),𝑠∈𝑆 2.V(s)={v(s),s∈S 0,max t∈s V(t),s∈S 1,min t∈s V(t),s∈S 2.

其中，𝑡 ∈𝑠 t∈s 表示 𝑡 t 是 𝑠 s 的后继局面．这就是 极小化极大思想．

将这一算法应用于实际问题中，通常有如下具体方法：

- 如果游戏中涉及的局面数量较少，直接暴力实现这一算法即可．

- 如果游戏中涉及的局面数量较为庞大且没有特殊结构，可以考虑 Alpha–Beta 剪枝 并结合其他搜索剪枝算法使用．

- 如果游戏中单个局面经常是多个局面的后继局面，为避免重复搜索，可以考虑记忆化搜索或其他动态规划算法．

- 如果游戏中玩家的最终收益是终局前所有行动的收益和，可以适当优化建模方式．具体地，假设到达终局 𝑠 ∈𝑆 0 s∈S 0 时，玩家 𝑖 =1,2 i=1,2 的行动序列分别为 {𝑎(𝑖)𝑗}𝑘 𝑖 𝑗=1{a j(i)}j=1 k i，行动 𝑎 a 对应的收益为 𝑤(𝑎)w(a)，玩家 1 1 的收益函数为

  𝑣(𝑠)=𝑘 1∑𝑗=1 𝑤(𝑎(1)𝑗)−𝑘 2∑𝑗=1 𝑤(𝑎(2)𝑗).v(s)=∑j=1 k 1 w(a j(1))−∑j=1 k 2 w(a j(2)).

  那么，可以设 ˜𝑉(𝑠)V~(s) 为当前玩家在局面 𝑠 ∈𝑆 s∈S 之后的游戏中能够取得的最大分数．对于初始状态 𝑠 0 s 0，有 𝑉(𝑠 0) =˜𝑉(𝑠 0)V(s 0)=V~(s 0)，因此求出 ˜𝑉( ⋅)V~(⋅) 足以求解原问题．对于 ˜𝑉( ⋅)V~(⋅)，有如下递推关系：

  ˜𝑉(𝑠)={0,𝑠∈𝑆 0,m a x 𝑡∈𝑠 𝑤(𝑎 𝑠→𝑡)−˜𝑉(𝑡),𝑠∈𝑆 1∪𝑆 2.V~(s)={0,s∈S 0,max t∈s w(a s→t)−V~(t),s∈S 1∪S 2.

  其中，𝑎 𝑠→𝑡 a s→t 表示可以使得状态从 𝑠 s 转移到 𝑡 t 的行动，如果有多个这样的行动，取收益 𝑤(𝑎)w(a) 最高的那个．

- 公平组合游戏都是序贯零和游戏，只需要设游戏中胜利方和失败方的收益分别为 +1+1 和 −1−1．此时，收益函数 𝑉( ⋅)V(⋅) 的递推关系其实就是判定必胜状态和必败状态的 引理．

  这类问题还有一种常见的变形，即求胜利方最少需要的回合数和失败方最多可以坚持的回合数．为此，只需要注意到从终止状态开始做 BFS 并按照引理判定必胜状态和必败状态时，记录判定必胜状态和必败状态时 BFS 进行到的轮次数，就是所求的回合数．这是因为判定为必胜状态只需要一个后继状态是必败状态即可，它总是由后继状态中轮次数最小的必败状态转移而来；而判定为必败状态需要所有后继状态都是必胜状态，它总是由后继状态中轮次数最大的必胜状态转移而来．

  这一方法同样可以推广到一般的 有向图游戏．

### 例题

Codeforces 794 E. Choosing Carrot

设有一个长度为 𝑛 n 的数列 𝑎 𝑖 a i．两名玩家 1 1 和 2 2 轮流从数列的两端取走一个数，直到数列中仅剩下最后一个数字为止．玩家 1 1 的目标是最大化这个最后剩下的数字，玩家 2 2 的目标是最小化它．在游戏正式开始前，玩家 1 1 还可以先进行 𝑘 k 次行动．假设两名玩家在整个过程中都采取最优策略．对于每一个 𝑘 =0,1,2,⋯,𝑛 −1 k=0,1,2,⋯,n−1，求出游戏结束时最后剩下的数字．其中，1 ≤𝑛 ≤3 ×1 0 5 1≤n≤3×10 5．

解答

因为无论双方怎样取走数字，数列剩余部分都是一段完整的区间．所以，游戏中的局面可以仅由区间 [𝑙,𝑟][l,r] 和当前行动的玩家 𝑖 =1,2 i=1,2 描述，可以使用动态规划算法求解．设 𝑓(𝑙,𝑟,𝑖)f(l,r,i) 为局面由 (𝑙,𝑟,𝑖)(l,r,i) 描述时，游戏最后剩下的数字．由前文分析可知，当 𝑙 <𝑟 l<r 时，这一函数满足状态转移方程：

𝑓(𝑙,𝑟,1)=m a x{𝑓(𝑙+1,𝑟,2),𝑓(𝑙,𝑟−1,2)},𝑓(𝑙,𝑟,2)=m i n{𝑓(𝑙+1,𝑟,1),𝑓(𝑙,𝑟−1,1)}.f(l,r,1)=max{f(l+1,r,2),f(l,r−1,2)},f(l,r,2)=min{f(l+1,r,1),f(l,r−1,1)}.

终值条件为 𝑓(𝑙,𝑙,1) =𝑓(𝑙,𝑙,2) =𝑎 𝑙 f(l,l,1)=f(l,l,2)=a l．据此，可以在 Θ(𝑛 2)Θ(n 2) 时间内求出所有可能局面的函数值．对于每个 𝑘 k，答案就是

𝑔(𝑘)=m a x 𝑓(𝑙,𝑟,1) s u b j e c t t o 𝑟−𝑙+1=𝑘.g(k)=max f(l,r,1) subject to r−l+1=k.

这一算法无法通过原题所设的数据范围，因此需要考虑优化转移．此处有很多种处理方法，本文只提供其中一种．

将状态转移方程看作是对数列整体的操作．两个转移方程分别表示将相邻数字取最大值和最小值得到新数列，将它们分别称为「最大化操作」和「最小化操作」．每次操作都会使得数列长度减一．所有长度为 𝑑 d 的区间对应结果共计 (𝑛 −𝑑 +1)(n−d+1) 个，这就相当于对序列进行 (𝑑 −1)(d−1) 次操作得到的序列．另外，要得到 𝑓(𝑙,𝑟,1)f(l,r,1) 的结果，就需要保证最后一次操作是最大化操作．因此，这些操作序列的结尾总是最大化操作．

考虑连续两次操作给数列带来的变化．不妨考虑首先做最小化操作，再做最大化操作．此时，数列 𝑎 1,𝑎 2,𝑎 3 a 1,a 2,a 3 将变为

m a x{m i n{𝑎 1,𝑎 2},m i n{𝑎 2,𝑎 3}}.max{min{a 1,a 2},min{a 2,a 3}}.

枚举 𝑎 1,𝑎 2,𝑎 3 a 1,a 2,a 3 三个数字之间所有可能的大小关系可知，除了 𝑎 1 <𝑎 2 a 1<a 2 且 𝑎 2 >𝑎 3 a 2>a 3（即 𝑎 2 a 2 是严格极大值）这种情形外，这一表达式总是等于 𝑎 2 a 2．也就是说，如果一个数列不存在任何严格极大值点，那么，连续两次操作对它的唯一影响就是删去了数列首尾各一个数字．这显然大幅简化了转移．剩下唯一的问题就是：如何保证数列不存在任何严格极大值点？事实上，只要对序列做一次最大化操作，就能保证不存在严格极大值点．故而，所有偶数次操作的结果，可以通过对初始数列进行两次操作得到的序列，逐对删去首尾数字得到；所有奇数次操作的结果，可以通过对初始数列进行一次操作得到的序列，逐对删去首尾数字得到．

由于对序列的完整操作至多只需要进行 3 3 次，而后续统计答案只需要 2 2 次遍历，所以该算法的总时间复杂度为 Θ(𝑛)Θ(n)．

参考代码

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #include <algorithm>
    #include <iostream>
    #include <vector>

    int main() {
      int n;
      std::cin >> n;
      std::vector<int> a(n);
      for (int& x : a) std::cin >> x;
      std::vector<int> 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;
    }

### 习题

- Luogu P2734 [USACO3.3] 游戏 A Game
- Luogu P4576 [CQOI2013] 棋盘游戏
- Luogu P7097 [yLOI2020] 牵丝戏
- Codeforces 388 C. Fox and Card Game
- Codeforces 794 E. Choosing Carrot
- Codeforces 1628 D2. Game on Sum (Hard Version)
- Luogu P3210 [HNOI2010] 取石头游戏

## 同时零和游戏

同时零和博弈中，两名玩家同时行动．

同时零和游戏通常采用收益矩阵表示．假设玩家 𝑖 =1,2 i=1,2 的行动集合为 𝐴 𝑖 A i，且当玩家 𝑖 =1,2 i=1,2 分别采取行动 𝑎 𝑖 ∈𝐴 𝑖 a i∈A i 时，两人的收益分别是 𝑣(𝑎 1,𝑎 2)v(a 1,a 2) 和 −𝑣(𝑎 1,𝑎 2)−v(a 1,a 2)．

例子

考虑石头剪刀布游戏．假定胜利得 1 1 分，失败得 −1−1 分，平局得 0 0 分．那么，游戏中两人的收益可以表示为

⎛⎜ ⎜ ⎜⎝0,0 1,−1−1,1−1,1 0,0 1,−1 1,−1−1,1 0,0⎞⎟ ⎟ ⎟⎠.(0,0 1,−1−1,1−1,1 0,0 1,−1 1,−1−1,1 0,0).

一般的二人同时游戏也可以表示为类似形式，故而也称为 双矩阵游戏（bimatrix game）．对于零和博弈，由于玩家 1 1 的收益矩阵和玩家 2 2 的收益矩阵互为相反数，所以可以只考虑玩家 1 1 的收益矩阵：

𝑉=(𝑣(𝑎 1,𝑎 2))(𝑎 1,𝑎 2)∈𝐴 1×𝐴 2=⎛⎜ ⎜ ⎜⎝0 1−1−1 0 1 1−1 0⎞⎟ ⎟ ⎟⎠.V=(v(a 1,a 2))(a 1,a 2)∈A 1×A 2=(0 1−1−1 0 1 1−1 0).

需要解决的问题是：给定收益矩阵 𝑉 =(𝑣(𝑎 1,𝑎 2))(𝑎 1,𝑎 2)∈𝐴 1×𝐴 2 V=(v(a 1,a 2))(a 1,a 2)∈A 1×A 2，如何求出两名玩家的最优策略和最大收益？

### 混合策略

相较于序贯零和游戏，同时游戏中两名玩家的角色是对称的．但是，既然已经解决了序贯零和游戏，那么不妨考虑同时游戏的序贯版本．例如，如果假定玩家 1 1 首先做出行动，玩家 2 2 再做出行动，那么，根据前文讨论，游戏结束时玩家 1 1 的收益将由

𝑤−=m a x 𝑎 1∈𝐴 1 m i n 𝑎 2∈𝐴 2 𝑣(𝑎 1,𝑎 2)w−=max a 1∈A 1 min a 2∈A 2 v(a 1,a 2)

给出．由于玩家 1 1 的行动对于玩家 2 2 单向透明，这应该是玩家 1 1 所能获得的最差结果．对称地，如果假定玩家 2 2 首先行动，那么，玩家 1 1 的收益将由

𝑤+=m i n 𝑎 2∈𝐴 2 m a x 𝑎 1∈𝐴 1 𝑣(𝑎 1,𝑎 2)w+=min a 2∈A 2 max a 1∈A 1 v(a 1,a 2)

给出．由于玩家 2 2 的行动对于玩家 1 1 单向透明，这应该是玩家 1 1 所能获得的最好结果．玩家 1 1 应该期待实际进行游戏时，所能获得的收益 𝑤 ∈[𝑤−,𝑤+]w∈[w−,w+]．尽管不等式 𝑤− ≤𝑤+w−≤w+ 总是成立（证明参见 弱对偶定理），但是由于等号未必成立，所以，仅采用序贯游戏的分析手段，一般情况下没有办法唯一确定游戏结果．

例子（续）

石头剪刀布游戏中，如果出手有先后，那么先手必输，后手必赢．转换为数学语言，这就是下列不等式：

𝑤−=−1≤+1=𝑤+.w−=−1≤+1=w+.

此时，𝑤− ≠𝑤+w−≠w+ 并不成立．

上述分析过程遗漏了同时游戏的一个关键因素，就是玩家无法准确预测对手的行动．形式上，这意味着双方可以采取某种随机策略．这一想法在序贯博弈的语境下并不成立，因为无论先手玩家如何随机选择行动，后手玩家总能准确地观测到这一行动，并有针对性地回应．但是，对于同时游戏，随机策略引入的战略模糊将使得对手无法有效地针对己方的行动．

例子（续）

石头剪刀布游戏中，如果玩家 1 1 均匀随机地选择剪刀、石头、布三个行动之一，那么，根据玩家 2 2 的行动不同，玩家 1 1 可能获得的收益是

1 3(0,1,−1)𝑇+1 3(−1,0,1)𝑇+1 3(1,−1,0)𝑇=(0,0,0)𝑇.1 3(0,1,−1)T+1 3(−1,0,1)T+1 3(1,−1,0)T=(0,0,0)T.

此时，无论玩家 2 2 如何选择行动，玩家 1 1 的期望收益总是 0 0．这显然好于确定性地选择单个行动．

由此，就引入了混合策略的概念．

混合策略

同时游戏中，玩家 𝑖 i 的 混合策略（mixed strategy），简称 策略，是指函数 𝑠 𝑖 :𝐴 𝑖 →[0,1]s i:A i→[0,1]，且它满足 ∑𝑎 𝑖∈𝐴 𝑖 𝑠 𝑖(𝑎 𝑖) =1∑a i∈A i s i(a i)=1．也就是说，策略 𝑠 𝑖 s i 就是玩家 𝑖 i 的行动集合 𝐴 𝑖 A i 上的一个概率分布．玩家 𝑖 i 全体混合策略的集合记作 𝑆 𝑖 =Δ(𝐴 𝑖)S i=Δ(A i)，其中，Δ(𝐴 𝑖)Δ(A i) 表示 𝐴 𝑖 A i 上的全体概率分布的集合．如果 𝑠 𝑖 s i 是退化的概率分布，即存在 𝑎 ∈𝐴 𝑖 a∈A i 使得 𝑠 𝑖(𝑎) =1 s i(a)=1，那么，也称策略 𝑠 𝑖 s i 为 纯策略（pure strategy）．

混合策略的收益就是单个行动收益的期望：

𝑣(𝑠 1,𝑠 2)=∑𝑎 1∈𝐴 1∑𝑎 2∈𝐴 2 𝑠 1(𝑎 1)𝑠 2(𝑎 2)𝑣(𝑎 1,𝑎 2).v(s 1,s 2)=∑a 1∈A 1∑a 2∈A 2 s 1(a 1)s 2(a 2)v(a 1,a 2).

将单个行动看作对应的纯策略，那么，就可以将行动集合 𝐴 𝑖 A i 嵌入（混合）策略集合 𝑆 𝑖 S i 中，且上式定义的 𝑣(𝑠 1,𝑠 2)v(s 1,s 2) 就可以看作是将 𝑣(𝑎 1,𝑎 2)v(a 1,a 2) 从 𝐴 1 ×𝐴 2 A 1×A 2 延拓到 𝑆 1 ×𝑆 2 S 1×S 2 上．

### von Neumann 定理

引入混合策略后，极大化极小思想和极小化极大思想得到的结果是一致的，由此，同时零和游戏的结果也是唯一确定的．

定理（von Neumann）

允许混合策略的同时零和游戏中，如果双方都采取最优策略，那么，玩家 1 1 的最大收益为

𝑤=m a x 𝑠 1∈𝑆 1 m i n 𝑠 2∈𝑆 2 𝑣(𝑠 1,𝑠 2)=m i n 𝑠 2∈𝑆 2 m a x 𝑠 1∈𝑆 1 𝑣(𝑠 1,𝑠 2),w=max s 1∈S 1 min s 2∈S 2 v(s 1,s 2)=min s 2∈S 2 max s 1∈S 1 v(s 1,s 2),

玩家 2 2 的最大收益为 −𝑤−w．

证明

设 𝑤 =m a x 𝑠 1∈𝑆 1 m i n 𝑠 2∈𝑆 2 𝑣(𝑠 1,𝑠 2)w=max s 1∈S 1 min s 2∈S 2 v(s 1,s 2)．考虑内层最小化问题，因为 𝑣(𝑠 1,𝑠 2) =∑𝑎 2∈𝐴 2 𝑠 2(𝑎 2)𝑣(𝑠 1,𝑎 2)v(s 1,s 2)=∑a 2∈A 2 s 2(a 2)v(s 1,a 2)，所以，m a x 𝑠 2∈𝑆 2 𝑣(𝑠 1,𝑠 2) =m a x 𝑎 2∈𝐴 2 𝑣(𝑠 1,𝑎 2)max s 2∈S 2 v(s 1,s 2)=max a 2∈A 2 v(s 1,a 2)，前者的最优解就是后者的最优解对应的纯策略．因此，有 𝑤 =m a x 𝑠 1∈𝑆 1 m i n 𝑎 2∈𝐴 2 𝑣(𝑠 1,𝑎 2)w=max s 1∈S 1 min a 2∈A 2 v(s 1,a 2)．进而，引入辅助变量 𝑢 u，问题就可以改写为

𝑤=m a x 𝑠 1∈𝑆 1 𝑢 s u b j e c t t o 𝑢≤m i n 𝑎 2∈𝐴 2 𝑣(𝑠 1,𝑎 2).w=max s 1∈S 1 u subject to u≤min a 2∈A 2 v(s 1,a 2).

因为这个约束就等价于 𝑢 ≤𝑣(𝑠 1,𝑎 2)u≤v(s 1,a 2) 对于所有 𝑎 2 ∈𝐴 2 a 2∈A 2 都成立．最后，引入混合策略 𝑠 1 s 1 的定义和收益函数 𝑣(𝑠 1,𝑎 2)v(s 1,a 2) 的表达式，原问题就等价于 线性规划问题

(𝑃)𝑤=m a x 𝑢,𝑠 1 𝑢 s u b j e c t t o ∑𝑎 1∈𝐴 1 𝑠 1(𝑎 1)𝑣(𝑎 1,𝑎 2)≥𝑢, ∀𝑎 2∈𝐴 2,∑𝑎 1∈𝐴 1 𝑠 1(𝑎 1)=1,𝑠 1(𝑎 1)≥0, ∀𝑎 1∈𝐴 1.(P)w=max u,s 1 u subject to ∑a 1∈A 1 s 1(a 1)v(a 1,a 2)≥u, ∀a 2∈A 2,∑a 1∈A 1 s 1(a 1)=1,s 1(a 1)≥0, ∀a 1∈A 1.

这个问题显然是可行的，且最优解有解．根据 对偶原理 可知，它的最优解就等于对偶问题的最优解：

(𝐷)𝑤=m i n 𝑡,𝑠 2 𝑡 s u b j e c t t o ∑𝑎 2∈𝐴 2 𝑠 2(𝑎 2)𝑣(𝑎 1,𝑎 2)≤𝑡, ∀𝑎 1∈𝐴 1,∑𝑎 2∈𝐴 2 𝑠 2(𝑎 2)=1,𝑠 2(𝑎 2)≥0, ∀𝑎 2∈𝐴 2.(D)w=min t,s 2 t subject to ∑a 2∈A 2 s 2(a 2)v(a 1,a 2)≤t, ∀a 1∈A 1,∑a 2∈A 2 s 2(a 2)=1,s 2(a 2)≥0, ∀a 2∈A 2.

重复前文的步骤，这一问题就等价于 m i n 𝑠 2∈𝐴 2 m i n 𝑠 1∈𝑆 1 𝑣(𝑠 1,𝑠 2)min s 2∈A 2 min s 1∈S 1 v(s 1,s 2)．定理得证．

这一结果正是这一游戏的 Nash 均衡．也就是说，假定双方都选择均衡中的最优策略，那么，没有任何玩家能够从偏离均衡策略中严格获益．

### 转化为线性规划问题

von Neumann 定理的证明同时也指出了同时零和游戏的求解方法．设 𝑛 n 和 𝑚 m 分别是玩家 1 1 和 2 2 可采取的行动数目．给定玩家 1 1 的收益矩阵 𝑉 ∈𝐑 𝑛×𝑚 V∈R n×m，可以求解如下线性规划问题：

𝑤=m a x(𝑢,𝑠)∈𝐑×𝐑 𝑛 𝑢 s u b j e c t t o 𝑉 𝑇 𝑠≥𝑢 𝟏,𝟏 𝑇 𝑠=1,𝑠≥0.w=max(u,s)∈R×R n u subject to V T s≥u 1,1 T s=1,s≥0.

这是一个规模为 Θ(𝑛 +𝑚)Θ(n+m) 的线性规划问题，可以用 单纯形法 高效求解．算法得到的最优解 𝑠 s 就是玩家 1 1 的最优（混合）策略．要求得玩家 2 2 的最优策略，只需要从单纯形表中获得该问题最优解的对偶变量（即影子价格）即可．

### 习题

- Luogu P4232 无意识之外的捉迷藏

## 参考资料与注释

- Zero-sum game - Wikipedia
- Minimax theorem - Wikipedia

> 本页面最近更新：2025/10/17 09:50:13，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：c-forrest
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用