【学习笔记】博弈论

博弈论基(寄)础

几个基本的知识

有限博弈

先手必胜当且仅当先手将当前状态变为先手必败态
先手必败当且仅当先手不能将当前状态变为先手必败态

有向无环图博弈

给定一个 $DAG$ ，初始 $1$ 号点有一个棋子，小 $A$ 和小 $B$ 可以将棋子沿出边移动一次，最后无法移动的为输者。

SG 函数

基本描述：
- 对于有向无环图博弈， $S G (i) = mex (S G (j) | e d g e (i, j) \in E)$ ， $mex$ 即未出现过的最小非负整数。则先手必胜则意味着 $S G (1) \neq 0$ ，也就是 $S G (1) = 0$ 意味着先手必败态。
- 证明： 我们将分以下三个部分证明， $S G (1) \neq 0$ 时先手必胜：
  - 最终态是必败态：
    - 显然最终态就是无法移动，也就是 $S G = 0$ ，也就是必败态。
  - 必胜态可以走向必败态：
    - 若 $S G (1) \neq 0$ ，意味着我们可以走向 $S G = 0$ 的点，也就是可以走向必败态
  - 必败态只能走向必胜态：
    - 当 $S G (1) = 0$ 时，显然不能走到 $S G = 0$ 的点，所以只能走向必胜态

子游戏

问题描述：
- 给定 $m$ 个 $DAG$ ，小 $A$ 和小 $B$ 每次可以选择一个 $DAG$ ，并将其上的棋子沿出边移动一次，移动不了为输。
- SG定理： 先手必胜当且仅当每个 $DAG$ 的起点的 $S G$ 的异或值不等于 $0$
- 证明： 依旧分以下三个部分证明：
  - 最终态是必败态：
    - 最终态就是无法移动，所有的 $S G$ 都等于 $0$ ，显然是必败态
  - 必胜态可以走向必败态：
    - 若 $\oplus_{i = 1}^{m} S G (i) = a \neq 0$ ，显然我们可以通过某个 $DAG$ 上走一步，使得 $\oplus_{i = 1}^{m} S G (i) = 0$ ，也就是可以走向必胜态。因为我们最终的答案里面的每一个 $1$ ，肯定都可以通过在某一个 $DAG$ 上走一步，使得答案除去当前起点的值导致最高位消掉，我们再走到含有剩下的 $1$ 的点，这样加入贡献之后这些 $1$ 也消掉了。
  - 必败态只能走向必胜态：
    - 显然无法移动一步，使得移动后的 $S G$ 的异或和等于现在的异或和，也就是一定走向必胜态。

Nim 游戏

题目描述：
- 有 $n$ 堆石子，第 $i$ 堆石子有 $a_{i}$ 个， $A$ 和 $B$ 每次可以从任意一堆中取出至少一个，不能取的人为输，请问谁有必胜策略。
题目分析：
- 显然每一堆石子都是一个子游戏，我们可以以石子数为 $DAG$ 上的点，那么对于起点 $i$ 它的 $S G$ 显然等于 $a_{i}$ ，因为我们可以将图理解为如下样子：
- 显然从底向上 $S G$ 值依次为： $0, 1, 2, 3$ 。注意最底端的节点代表 $0$ 个石子。

例题

题目描述：
- 给定 $n$ 行，第 $i$ 行的长度为 $a_{i}$ ，每行最左边有一颗白子，最右边有一颗黑子， $A$ 可以移动白子， $B$ 可以移动黑子，不能跨过对方的棋子，不能移动为输。
题目分析：
- 我们棋子向边上走肯定不优，因为根据模仿的思想，假设白子向左移 $x$ ，那么黑子也可以向左移 $x$ ，这样显然使得白子的局势不会更优。那么我们就考虑向中间走 $1$ ，就理解为拿一颗石子，那么对于第 $i$ 行就是相当于有 $a_{i} - 2$ 个石子，也就是成为了我们的 Nim 游戏。

K-Nim 游戏

题目描述：
- 有 $n$ 堆石子，第 $i$ 堆石子有 $a_{i}$ 个， $A$ 和 $B$ 轮流进行操作，每次操作最多可以选择 $K$ 堆石子每堆石子拿至少一个，不能取的人为输，问谁有必胜策略。
- 定理： 将 $a_{i}$ 按二进制拆分，若每个二进制位上为 $1$ 的个数对 $K + 1$ 取模等于 $0$ ，则先手必败
- 证明：
  - 最终态是必败态：显然最终态为必败态，因为已经全部取完了
  - 必胜态可以走向必败态：
    - 假设我们已经改变了 $m$ 堆，使得第 $i$ 位之前的位都是 $K + 1$ 倍数，那么就要找到一种方式使得第 $i$ 位也是 $K + 1$ 的整数倍。显然对于考虑完的 $m$ 堆，我们可以任意的选择其第 $i$ 位是 $0$ 或 $1$ ，那么我们记不考虑这 $m$ 堆，剩下的堆里第 $i$ 位 $1$ 的个数为 $s u m$ 。
      - 若 $s u m \leq K - m$ ，显然可以将这 $s u m$ 个 $1$ 都变成 $0$ ，然后将 $m$ 堆的 $1$ 也都变成 $0$ 。这样就相当于第 $i$ 位的总数为 $0$ ，符合条件。
      - 若 $s u m > K - m$ ，我们在这 $m$ 堆里，选出 $K + 1 - s u m$ 堆变成 $1$ ，这样两者一加就是 $K + 1$ 个 $1$ ，符合条件。化简一下就能得到 $K + 1 - s u m \leq m$
  - 必败态只能走向必胜态：
    - 我们每次最多将某一个二进制位上的 $1$ 改变 $K$ 个，最少将某一个二进制位上的 $1$ 改变 $1$ ，因为我们最少改变一堆最多改变 $K$ 堆。因为我们原来的每一个二进制位都是 $K + 1$ 的倍数，所以我们更改之后一定不都是，即一定是必胜态。

例题

题目来源：
- [SDOI2011]黑白棋
题目分析：
- ~~这个题其实最麻烦的是证明 K-Nim 游戏，不过我证了~~
  我们考虑如果初始状态给定，那么这就是一个 K-Nim 游戏，我们依旧将距离视为石子也就能发现了。然后根据 K-Nim 游戏的过程，我们可以想出一个显然巨难的状态： $d p [i] [j]$ 表示前 $i - 1$ 位取模后全部是 $0$ ，当前放了 $j$ 个棋子的方案数，也就是先手必输的方案数。
- 那么转移就是我们枚举第 $i$ 位是 $d + 1$ 的多少倍，然后也就是从这 $\frac{k}{2}$ 个堆里，选 $x (d + 1)$ 个，也就是乘一个组合数 $(\binom{\frac{k}{2}}{x (d + 1)})$ ，然后我们最后还要搞一下这些堆在哪里，也就是乘 $(\binom{n - i - \frac{k}{2}}{\frac{k}{2}})$

反 Nim 游戏

题目描述：
- 有 $n$ 堆石子，第 $i$ 堆石子的个数为 $a_{i}$ ， $A$ 和 $B$ 轮流从一堆中选择至少一个石子，取到最后一个的人为输，问谁有必胜策略。
题目分析：
- Anti-SG定理： 假设当所有子游戏的 $S G$ 均为 $0$ 时游戏结束，那么满足如下条件之一先手必胜：
  - 所有子游戏的 $S G$ 的异或和不为 $0$ ，且某个游戏的 $S G$ 值大于 $1$
  - 所有子游戏的 $S G$ 的异或和为 $0$ ，且所有游戏的 $S G$ 值都小于等于 1
- 证明：
  - 我们定义如下的四个状态：
    - $A$ ： $S G$ 的异或和等于 $0$ ，且存在某个游戏的 $S G$ 大于 $1$ （先手必败）
    - $B$ ： $S G$ 的异或和等于 $0$ ，且任意游戏的 $S G$ 小于等于 $1$ （先手必胜）
    - $C$ ： $S G$ 的异或和不等于 $0$ ，且存在某个游戏的 $S G$ 大于 $1$ （先手必胜）
    - $D$ ： $S G$ 的异或和不等于 $0$ ，且任意游戏的 $S G$ 小于等于 $1$ （先手必败）
  - 最终态是必胜态：
    - 因为最终态就是所有的子游戏 $S G$ 值都为 $0$ ，显然此时先手必胜
  - 必胜态可以走向必败态：
    - 若满足状态 $C$
      - 若只有一个游戏的 $S G$ 大于 $1$ ，那么显然可以将这个游戏的 $S G$ 值变成 $0$ 或 $1$ ，而我们 $S G$ 的异或和不为 $0$ ，所以就走到了状态 $D$ ，必败态。
      - 若有多个游戏的 $S G$ 大于 $1$ ，则可以使用类似 $S G$ 定理的推导过程，将 $S G$ 的异或和变为 $0$ ，且存在某个游戏的 $S G$ 大于 $1$ ，即走到了状态 $A$ ，必败态
    - 若满足状态 $B$
      - 若到达终止条件，即全是 $0$ ，则直接胜利并终止游戏
      - 若某个游戏的 $S G$ 值为 $1$ ，则将这个值变为 $0$ ，那么就到达了状态 $D$ ，必败态
  - 必败态必须走向必胜态
    - 若满足状态 $A$
      - 若多个游戏的 $S G$ 值大于 $1$ ，显然只能转化为状态 $C$ ，必胜态。因为此时 $S G$ 的异或值不可能为 $0$ ，而且也存在某个游戏的 $S G$ 值大于 $1$
      - 若只有一个游戏的 $S G$ 值大于 $1$ ，显然这种条件下不可能导致 $S G$ 的异或值不等于 $0$
    - 若满足状态 $D$
      - 若将某一个 $S G$ 值为 $1$ 的游戏的 $S G$ 值改为 $0$ ，显然对于 $S G$ 的异或和是取反的，因为原来异或的值只有 $1$ 或 $0$ ，异或之后依旧是 $1$ 或 $0$ ，这样就会到达状态 $B$ ，必胜态。
      - 若将一个 $S G$ 值为 $0$ 的游戏的 $S G$ 值改为 $1$ ，显然也是取反，会到达状态 $B$ ，必胜态.
      - 若将一个 $S G$ 值为 $0$ 的游戏的 $S G$ 值改为大于 $1$ 的值，显然会到达状态 $C$ ，必胜态。因为此时显然 $S G$ 异或和不会等于 $0$ ，而有的游戏的 $S G$ 值大于 $1$ 。

阶梯博弈

题目描述：
- 有 $n$ 个阶梯呈编号升序排列，每个阶梯上有若干个石子，可行的操作是将一个阶梯上的石子移至少一个到前一个台阶。当没有可行操作时，即所有石子都被移动到了地面（第 $0$ 号台阶）输。
题目分析：
- 定理： 阶梯博弈相当于奇数号台阶的 Nim 游戏，即当奇数号台阶上的石子数的异或和不为 $0$ 时，先手必胜。
- 证明：
  - 最终态是必败态：
    - 显然最终态是所有的石子数为 $0$ ，仅考虑奇数也是必败态
  - 必胜态可以走到必败态：
    - 我们一定可以把某一些石子放到偶数堆上，也就是能使得奇数堆的异或和为 $0$ ，即走到必败态
  - 必败态必定走到必胜态：
    - 显然我们无法通过调整石子数使得异或和保持 $0$ 不变，所以必败态必定会走到必胜态。

例题

题目描述
- 给定 $n$ 堆石子，第 $i$ 堆石子的个数为 $a_{i}$ 个，保证初始石子数单调不降， $A$ 和 $B$ 轮流操作，每次可以从某一堆石子中移走至少一个，需要满足在任意时刻石子数均单调不降，不能取的人输。
题目分析
- 对石子数差分，然后倒序编号，也就相当于阶梯博弈的模型。

相关阅读:
list转map
通用Mapper获取数据表中id为0解决方法。千万别瞎改int为integer了
酷柚易汛ERP - 系统初始化操作指南
【监控系统】日志可视化监控体系ELK搭建
给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个? 如果得到子序列A删除的位置与得到子序列B删除的位置不同，那么认为A和B就是不同的。
kubeflow核心功能
JDBC（一）
是时候重视官网了，寄生平台的生意表达，就是在给平台打工
【牛客 - 剑指offer】JZ77 按之字形顺序打印二叉树 Java实现
1.16 - 校验码

原文地址：https://www.cnblogs.com/linyihdfj/p/16545186.html