博弈论学习笔记

面对各类 ACM 模拟赛与 CF 比赛中频繁出现的博弈类问题，我们可以借着网课小作复习。

一. 定义与一些概念

一个博弈类游戏必须满足以下条件：

1. 有两个玩家轮流操作；
2. 操作状态的集合是有限的；
3. 当一方不能将游戏继续下去后，该玩家便输掉游戏；
4. 游戏一定会在有限次操作后结束。

概念：必败点 与 必胜点，它包含以下属性：

1. 所有终结点是必败点（因此可以直接标记）；
2. 从 必胜点 操作，至少有一种方式可以进入必败点；
3. 无论怎么操作，由 必败点 必将进入必胜点。

对于小规模数据，可根据以上属性进行推导。因此 记住 总是没错的。

二.取石子游戏模型（Nim 游戏）

给定 n 堆石子，每堆有 $a_i$ 个，两个玩家轮流取走任意一堆的任意个物品，取不了的人输掉游戏。

假设两人都以最优策略进行游戏，问在任意状态下是必败还是必胜？

1. Nim 和：

我们引入 Nim和 的概念：对于 n 堆石子，其 Nim 和 $=a_1\oplus a_2\oplus a_3...$。

有如下定理：若 Nim 和等于0，则该状态为必败状态，反之为必胜状态。

证明：

1. Nim 游戏里终结位置的 Nim 和为0.
2. 根据属性 2，对于 Nim 和非 0 的情况，至少有一个方法，取出某一堆中的若干石子，使其整体的 Nim 和变成 0 。
3. 根据属性 3，对于 Nim 和为 0 的情况，无论移动多少石子，必将走到 Nim 和非 0 的状态。

Nim 游戏是一个模型，很多乱起八糟的规则可以通过一系列过程转换为该模型。

2. Anti-Nim

若将规则更改为：取到最后一个石子的人输掉游戏，就成了反 Nim 游戏。

根据以下规则推导：

1. 若存在奇数个 “只有一个石子” 的堆，则此时为必败点；
2. 否则，若该状态的 SG 函数值非 0，且当只有一堆石子多于 1 个，我们可以将其转换为情况 1，使得当前状态为必胜点；或是通过常规 Nim 游戏的套路将其转化为 SG 值为 0的情况；
3. 若 SG 值为 0，由于此时必存在两堆以上的石子的数目多于 1，下个状态 SG 值必大于 0，因此最终会回到必败点。

综上，若石子堆都只有一个石子的话就按奇偶，否则就正常分析。

三. DAG 游戏与 SG 函数

假若博弈论游戏的各个状态可以构成一个 DAG（或状态转移图），则我们可以引入 SG函数，将博弈问题转化为搜索问题从而暴力解决（？）

给出 SG函数的定义：对于某一状态 x，$SG(x)=mex(S)$，其中 S 是 x 状态所有后继状态的集合，而 mex 函数表示该集合内 最小且不存在的 非负整数。

有如下定理：若$sg(x)=0$则为必败点，反之为必胜点。

证明：

1. DAG 里终结位置的 sg(x)=0；
2. 若某状态 x 能走到必败点位置（sg 值为0），则由定义可知该状态的 sg 值必不为 0，满足属性 2；
3. 若某状态 x 是必败点，则其前驱节点的 sg 值大于 0，满足属性 3；

四. 组合游戏的并

1. 假设 A和B两人轮流从一个有 n 颗石子的石子堆中，取走 1,2 或 3 颗。A 先取，取走最后一颗石子的人获胜。问 A 是否必胜？

对于上述问题，我们不妨利用 sg 函数进行简单分析，发现有 sg(n)=n%4 如此规律。即石子数是四的倍数时为必胜状态。

2. 那假如对于 n 堆石子，每堆石子有 $a_i$，同样的规则进行博弈，答案又将如何？

我们不妨将其看做三个 组合游戏的并，将大问题分解为若干个小问题。

便有以下定理：
对于一个 DAG 游戏是若干组合游戏的并，即 $G=G_1+G_2+...$，且 $g_i$ 为 $G_i$ 的 sg值，则 G 的 sg 值即为 $g_1\oplus g_2\oplus g_3...$

然后就可以套之前那个定理了。