博弈论总结(已更新二分图博弈)

目录

• 博弈论
  • 组合游戏基础定义
    • 游戏的定义：
    • 游戏的表示：
    • 游戏的和：
  • 组合游戏模型
    • SG游戏中的SG函数与相关定理
    • Anti-SG游戏和SJ定理
    • Multi-SG游戏
    • Every-SG游戏
  • 常见博弈模型
    • Nim游戏
    • NimK游戏
    • 巴什博弈
    • 威佐夫博弈
    • 斐波那契博弈
    • 翻硬币游戏
    • 无向图删边游戏
    • 二分图博弈
  • 不平等博弈
    • Surreal Number

博弈论

---

• 以下主要内容来自于对集训队论文《组合游戏略述——浅谈SG游戏的若干拓展及变形》的整理与从其他地方收集补充的一些经典模型
• 博弈论还在学习过程中，可能还会补充一些东西
  ---update in 2019.1.31---已更新二分图博弈

组合游戏基础定义

游戏的定义：

• 游戏有2名参与者，两人轮流操作
• 游戏过程中的任意时刻有确定的状态
• 参与者操作时将游戏从当前状态转移到另一状态，且规则规定了在任意状态时，可以到达的状态集合
• 在有限步数之内结束(没有平局)
• 参与者拥有完全的信息

游戏的表示：

定义：对于一个游戏，如果当前状态$P$，玩家$L$可以转移到的状态为$P_L$,玩家$R$可以转移到的状态为$P_R$,那么记$P = {P_L | P_R}$
例子：假设当前状态为$P$,玩家$L$可以转移到的状态为$A, B, C$,玩家$R$可以转移到的状态为$D$。
那么$P = \{A, B, C | D\}$

游戏的和：

如果一个游戏$G$,可以被分解成若干个不相交的子游戏$G_1, G_2, G_3...G_n$,且满足在$G$中的操作等价与在子游戏中选一个进行操作，那么我们称$G$是这若干个子游戏的和，即$G = \sum_{i = 1}^{n}G_i$

组合游戏模型

SG游戏中的SG函数与相关定理

SG游戏定义：

这样一类组合游戏：无法操作者输

SG函数定义：

SG函数是对游戏图中每一个节点的评估函数。满足如下等式：

$$SG(v) = mex\{SG(u) | 图中有一条从v到u的边\}$$
其中$mex(x_1, x_2...x_t)$是定义在非负整数集合上的操作，自变量是任一非负整数集合。得到的结果是不属于该集合的最小自然数。即：
$$mex{S} = min(k | k \notin A \land k \in N)$$

性质：

1,对于任意局面，如果它的SG值为0，那么它的任意后继SG值不为0
2,对于任意局面，如果它的SG值不为0，那么一定有一个后继状态的SG值为0
在SG游戏中，SG值为0时先手必败。
3，在每次只能进行一步操作的情况下，对于任何游戏的和，如果将其中任一单一SG-组合游戏换成数目为它SG值的一堆石子，则该单一SG-组合游戏的规则变为取石子游戏的规则(可以任意取)，则游戏的和的胜负不变。

变式：

若只考虑游戏的和，我们可以将其中任一游戏换成SG值相等的其他游戏，游戏的和的SG值不变。

因此，在考虑游戏的和时，我们不关心每个单一游戏具体是什么，我们唯一要关心的就是这个单一游戏的SG值。由此可见，我们可以把任意游戏的和转换为Nim游戏,这样计算起来就很方便了。

Anti-SG游戏和SJ定理

Anti-SG游戏定义：

走完最后一步者输，即决策集合为空者赢(因为无法操作)

$\Delta$求解Anti-SG游戏时，依然可以使用SG函数求解。

anti-nim游戏

定义：

• 有$n$堆石子，参与者轮流取石子。
• 每次可以从一堆中取出任意数目的石子，不能不取
• 取走最后一个石子者败

结论：
先手必胜当且仅当

• 所有堆的石子数都为$1$且游戏的SG值为$0$
• 有些堆的石子数大于$1$且游戏的SG值不为$0$

证明：
两种情况：

• 有$n$个堆，每个堆只有一个石子。显然，先手必胜当且仅当$n$为偶数
• 其他情况：
• 当SG不为$0$时
  　　若还有至少两堆石子的数目大于$1$，则先手将SG值变为$0$即可;若只有一堆石子数大于$1$ 则先手总可以将状态变为有奇数个$1$(通过取完or取到只剩一个).所以先手必胜。
• 当SG为$0$时
  　　若至少有两堆石子的数目大于$1$，则先手决策完之后，必定至少有一堆石子大于$1$，且SG值不为$0$，所以先手必败。

但上述证明只对anti-nim游戏成立，因为在证明SG性质时，用到了这样一个性质：SG值为0的局面不一定为终止局面。

SJ定理

尝试将上述方法推广。
先看一个错命题

先手必胜当且仅当：
1，所有单一游戏的SG值小于$2$且游戏的SG值为$0$
2，存在单一游戏的SG值大于$1$且游戏的SG值不为$0$

在上图中，这个命题就不成立

定义：

对于任意一个Anti-SG游戏，如果我们规定当局面中所有的单一游戏的SG值为0时，游戏结束，则先手必胜当且仅当：
1，游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1
2，游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1

证明：
需要证明如下3种情况：
1，所有终止局面为先手必胜.(终止局面指决策集合为空的局面,即无法决策)
2，游戏中任何一个先手必败局一定只能转移到先手必胜局。
3，游戏中的任何一个先手必胜局一定能转移到至少一个先手必败局。

情况一：局面的SG函数为0且游戏中某个单一游戏的SG函数大于1.
$\because$当前局面的SG函数为0，又$\because$SG函数性质(1)
$\therefore$它所能转移到的任何一个局面的SG值不为0
$\because$当前局面的SG值为0且游戏中某个单一游戏的SG函数大于1.
$\therefore$当前局面中必定至少有2个单一游戏的SG函数大于1
又$\because$每次之多只能更改一个单一游戏的SG值
$\therefore$它能转移到的任何一个局面都至少有一个单一游戏的SG值大于1
由上述得：情况一所能转移到的任何一个局面都为先手必胜局

情况二：局面的SG函数不为0且游戏中没有单一游戏的SG函数大于1
可以发现，当前局面一定有奇数个游戏的SG值为1，其余游戏的SG值为0.
1，将某个单一游戏的SG值更改为大于1的数。
$\because$转移前没有单一游戏的SG值大于1，而转移将某个单一游戏的SG值更改为大于1的数
$\therefore$转移后的局面一定有且只有一个单一游戏的SG值大于1
$\therefore$后继局面的SG值一定不为0
因此，后继局面一定为先手必胜局
2，将某个单一游戏的SG值更改为0或1.
$\because$转移是将某个SG值为0的单一游戏改成SG值为1的单一游戏，或将某个SG值为1的单一游戏改成SG值为0的单一游戏。
$\therefore$转移后的局面一定有偶数个SG值为1的单一局面,且不含有SG值大于1的局面(什么意思？？？)
$\therefore$后继局面一定为先手必胜

情况三：局面的SG函数不为0且游戏中某个单一游戏的SG函数大于1.
1，局面中只有1个单一游戏的SG值大于1。
选择更改SG最大的单一游戏，可以将其更改为0或1来保证转移后的局面有且只有奇数个SG值为1的单一游戏。(同anti-nim游戏)
2，局面中至少有2个单一游戏的SG值大于1。
根据SG函数性质2，总存在一种决策可以将后继局面的SG值变为0.
$\because$局面中至少有2个单一游戏的SG值大于1
又$\because$每次最多只能改变一个单一游戏的SG值。
$\therefore$后继局面中至少有一个游戏的SG值大于1
因此，后继局面为先手必败

情况四：局面的SG函数为0且游戏中没有单一游戏的SG函数大于1.
当局面中所有单一游戏的SG值为0时，游戏结束，先手必败。(？？？)
否则，局面有且仅有偶数个SG值为1的单一游戏，其余游戏的SG值为0.
我们只需要将其中的某一个SG值为1的单一游戏的SG值变为0，游戏中即可出现奇数个SG值为1的单一游戏，到达先手必败态

$\Delta$SJ定理中的："规定当局面中所有单一游戏的SG值为0时，游戏结束"可以被替换为"当局面中所有单一游戏的SG值为0时，存在一个单一游戏满足SG值能够通过一次操作变为1"

Multi-SG游戏

定义：

1，在符合拓扑原则的前提下，一个单一游戏的后继可以为多个单一游戏
2，其他规则与SG游戏相同

求解：

可以通过将SG函数适当变形来解决。只需要证明：我们依然可以用SG函数来定义局面。
因为局面在游戏树中满足拓扑关系(无环)，所以我们可以根据拓扑关系用数学归纳法来证明。

Every-SG游戏

定义:

1，对于任意单一游戏，如果还未结束，那么就必须操作
2，其他规则同SG游戏

求解：

对于我们必胜的单一游戏，必定是玩的时间越长越优，对于必输的单一游戏，肯定是玩的时间越短越优。
那么据此有如下解法：
通过游戏图计算某个状态的SG函数(只需得知是否为0即可)，对于SG为0的点，需要知道最快几步可以结束游戏，对于SG不为0的点，需要知道最慢几步游戏会结束，用$step$函数来表示这个值

$$step(v) \begin{cases} 0 \quad v为终止状态\\ max(step(u)) + 1 \quad SG(v) > 0 \land u为v的后继状态\\ min(step(u)) + 1 \quad SG(v) = 0 \land u为v的后继状态\\ \end{cases}$$

定理：对于Every-SG游戏，先手必胜当且仅当单一游戏中最大的step为奇数。

证明：略……

常见博弈模型

Nim游戏

问题：$n$堆石子，每次从某一堆中拿若干个，无法操作者输。
结论：所有石子数异或和为$0$则后手胜，否则前手胜。
证明：
基于一个发现：如果有且只有$2$堆相同数量的石子，那么后手必胜。
这个发现可以进行推广，如果一个状态可以被一分为二到$2$个相同状态，那么后手必胜。
可以看做把$n$堆石子分为$2$组，每一组完全相同，那么A不管对其中的某一组做了什么操作，B都可以对另外一组做完全相同的对称性可知，B一定会赢。满足这样的一个条件的状态异或和为0；
用归纳法来尝试证明：(不严谨)
如果任意一个状态必输，实质上都是由于一个集合S内的若干个状态必输(可以通过SG函数的推导转化过来)，那么称集合S为基础必输态集合。
根据游戏的定义，nim游戏的基础必输态集合大小为1，里面只有一个元素，$S = \{0\}$.
而$0$的异或和为$0$。
因此只需要证明对于任意一个异或和不为$0$的状态，都可以通过某种方式变为异或和为$0$的状态。对于任意一个异或和为$0$的状态，无法通过任意转移变为异或和为$0$的状态。

对于异或和不为$0$的状态。设它们的异或和最高位为$k$，则一定有一个数的最高位也为$k$。

因此我们可以考虑对这个数进行操作。如果异或和的某一位为$0$，则我们不对这个数的这一位做任何改变；反之，我们对这一位取反。那么由异或和的特效可以得知，所有为$0$的位不变，依然为$0$.而所有为$1$的位状态改变，不再为$1$，因此这个后继状态的异或和就为$0$了。而因为第$k$位变为了$0$，且其他状态取反的位都小于$k$，因此这个数一定会减小，因此我们一定可以取出一定数量的石子达到目的。

对于异或和为$0$的状态，因为只能改变某一堆石子且必须做出改动，所以不管改哪一堆石子，都必然会使得至少一位的状态改变，从$0$变为$1$.

NimK游戏

问题：$n$堆石子轮流取，每次可以任选$m$堆取任意个，无法操作者输，求是否先手必胜。
结论：在二进制意义上，如果每一位的$1$的个数都是$m + 1$的倍数，那么先手必输。Nim游戏可以看做$m = 1$的NimK游戏。因为异或就相当于把每一位$1$的个数加起来对$2$取模.

巴什博弈

问题：一堆n个物品，2人轮流从这堆物品中取物，每次取$1$~$m$个，无法操作者输。
结论(解法)： 若$n = (m + 1)r + s$其中$r$为任意自然数，$s \le m$,即$n \% (m + 1) != 0$，则先手必胜。
证明：根据题意，如果剩下的石子小于等于$m$个,那么此时先手必胜。因此如果剩下的石子是m + 1个，那么先手取后，必定剩下小于等于$m$个石子，因此$m + 1$是先手必败态。
所以如果$n \% (m + 1) != 0$，那么先手只需要每次保持下一次的石子数是$m + 1$的倍数即可，这显然是可做到的。

威佐夫博弈

问题：有两堆若干个物品，两个人轮流从某一堆或同时从$2$堆中取同样多的物品，规定每次可以取任意个，但必须取。无法操作者输。
奇异局势：称先手必败局为奇异局势，那么前$n$个奇异局势为：

$$(0, 0), (1, 2), (3, 5), (4, 7), (6, 10), (8, 13)……$$
令$k$表示奇异局势的编号，则$(a[k], b[k])$表示第$k$个奇异局势，其中$(0, 0)$为第$0$个奇异局势。
可以发现：$a[k]$是未在前面出现过的最小自然数，而$b[k] = a[k] + k$.
性质：任何自然数都包含在一个，且仅有一个自然数里。
证明：$\because a[k]$是未在前面出现过的最小自然数，所以有
$$a[k] > a[k - 1]$$
$$b[k] = a[k] + k > a[k - 1] + k > a[k - 1] + k - 1 = b[k - 1] > a[k - 1]$$
所以$b,a$都不会重复，显然会包含所有的自然数。
结论：奇异局势满足如下等式：
$$a[k] = \frac{b[k] - a[k]}{1.618} = \frac{b[k] - a[k]}{\frac{\sqrt{5} + 1}{2}}$$

斐波那契博弈

问题：有一堆n个石子，2人轮流取，先取者可以取走任意多个，但不能全取完，以后每人取的石子数不能超过上个人的2倍，无法操作者输。
结论：先手必败当且仅当石子数为斐波那契数

翻硬币游戏

问题：一般的翻硬币游戏规则如下：

• $n$枚硬币排成一排，有的正面朝上，有的反面朝上，从左到右依次编号。
• 游戏者根据某些约束翻硬币(如：每次只能翻1或2枚，或者每次只能翻动连续的几枚)，但他所翻动的硬币中，最右边的那个必须是从正面翻到反面
• 无法操作者输
  结论：局面的SG值为局面中每个正面朝上的棋子单一存在时的SG值的异或和。
  
  $\Delta$在某种意义上，它的决策与Nim游戏完全等价。

无向图删边游戏

树的删边游戏

问题：有如下规则：

• 给出一个有$n$个节点的有根树。
• 游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。
• 无法操作者输
  结论：叶子节点的SG值为0，中间节点的SG值为它所有子节点的SG值加1后的异或和。

无向图删边游戏

• 一个无向联通图，有一个点作为图的根
• 游戏者轮流从图中删去边，删去一条边后，不与根相连的部分将被移走。
• 无法操作者输

Fusion Principle定理

对无向图做如下改动：将图中任意一个偶环缩成一个新点，任意一个奇环缩成一个新点加一个新边；所有连到原先环上的边全部与新点相连，这样的改动不会影响图的SG值。

因此可以将任意无向图改成树形结构。

二分图博弈

问题：基于以下几点：
1，共2人参与。
2，博弈状态(对应节点)可分为两类，任意合法转移都是在两类状态之间转移，而不能在任意一类状态内部转移。
3，不可以转移到已访问状态
4，无法转移者输
解法：
观察题目的特殊性，我们发现，将每个状态看做一个点，那么这些点和合法转移会构成一个二分图。
将S集合视作轮到先手决策的点，T集合则代表轮到后手决策的点。
我们先跑一遍二分图匹配，对于任意一点x，有2种情况：
1，不属于最大匹配(非匹配点)
　　走一步后必然会走到一个匹配点，否则如果遇到一个非匹配点就会形成一条增广路，那么就不符合最大匹配的前提。而走到一个匹配点后，对方可以不断沿着匹配边走，最后必然会停留在S集合，也就是先手必输。因为如果停留在T集合，依然相当于找到了一条增广路，不符合前提。
2，属于最大匹配
　　根据1中的描述可知，这个点先手必胜。
其他：

如果一个点$x$,在某种情况下不属于最大匹配，那么不管它怎么走，走到的目标节点一定会在某种情况下属于最大匹配，因此如果从点$x$开始会导致先手必败。反之，如果一个点$x$在任意情况下都属于最大匹配(即为最大匹配的必须点)，则先手必胜。

如何检验？
1，最暴力的方法：把$x$从原图中删去，再跑最大匹配，如果跑出的最大匹配大小不变，则说明是非必须点。
2，稍微巧妙一点的方法：考虑一个$x$是必须点，相当于没有点可以取代$x$，因此我们从$x$开始遍历，看是否可以找到一个同侧的未匹配点，如果可以找到，则说明$x$为非必须点。
即我们在用匹配点来寻找是否有点可以替换掉它。因此我们可以在$n + m$的时间内判断出一个点是否为必须点。

将这个做法进行推广，我们可以得到一个判断二分图中有没有$x$是非必须点的方法：
从每个未匹配点$x$开始遍历，将经过的同侧点打上标记，最后检验是否有匹配点被打上标记，有则图中至少有一个非必须点，因此如果后手可以选择开始的位置，那么先手必败。

不平等博弈

Surreal Number

以下内容主要参考自:

现在看不懂……以后再看……
睡前说：超现实数
实数、超实数和博弈游戏：数学的结构之美
浅谈算法——博弈论
博弈论的总结
简单博弈论
博弈论总结
《浅谈如何解决不平等博弈问题》
Wiki百科

定义：

SN的定义：

为了简便起见，下文中将Surreal Number简写为SN.
定义SN为一个由左集合与右集合组成，表示为$\{L | R\}$的一个东西。且满足如下性质：
左集合和右集合中的元素也是SN，且左集合中的元素严格小于右集合中的元素

符号的定义：

• $\le$:对于$x = \{ X_L | X_R \}$和$y = \{Y_L | Y_R\}$,我们称$x \le y$当且仅当不存在$x_L \in X_L$使得$y \le x_L$，以及不存在$y_R \in Y_R$使得$y_R \le x$
• $<$:$x < y$表示$x \le y \land \urcorner (y \le x)$
• $=$:$x = y$表示$x \le y \land y \le x$
• $+$:设有$x = \{ X_L | X_R\}$和$y = \{Y_L | Y_R\}$.那么 $$x + y = \{ X_L | X_R\} + \{Y_L | Y_R\} = \{X_L + y, x + Y_L | X_R + y, x + Y_R\}$$
  其中对于集合$X$与SN$y$的运算：$X + y = {x + y : x \in X}$
  边界情况:$\varnothing + n = \varnothing$

SN的构造方法:

首先有$\{\varnothing | \varnothing\} = \{ | \} = 0$,因此我们可以用0来构造其他SN，可以得到$\{0 | \}, \{| 0\}, \{0 | 0\}$.
$\because 0 \le 0 \quad \therefore \{0 | 0\}$不合法
$\because \{|0\} < 0 < \{0|\} \quad \therefore\{|0\} = -1, \{0|\} = 1$
利用0, 1, -1可以构造出7个合法的SN：
$\because \{1 | \} > 1, \{| 1\} < -1 \quad \therefore \{1 | \} = 2, \{| 1\} = -2$
$\because 0 < \{0 | 1\} < 1$且$\{0 | 1\} + \{0 | 1\} = 1 \quad \therefore \{0 | 1\} = \frac{1}{2}$ 同理$\{-1 | 0\} = - \frac{1}{2}$
$\Delta$如此类推，可以构造出所有形如$\frac{j}{2^k}$的有理数,定义达利函数为：

$$\delta(x) \begin{cases} \{1\},\quad x = 0 \\ \{\delta(x - 1)|\}, \quad x > 0 \land x \in z\\ \{|\delta(x + 1)\}, \quad x < 0 \land x \in z\\ \{\delta(\frac{j - 1}{2^k}) | \delta(\frac{j + 1}{2^k})\}, \quad x = \frac{j}{2^k} \land j, k \in z \land k > 0 \end{cases}$$

定理：对于一个SN $x = \{L | R\}$,若$L$中有最大元素$L_{max}$,那么$\{L_{max} | R\} = x$ ;类似的，若集合$R$中有最小元素$R_{min}$，那么$\{L | R_{min}\} = x$
例如：$\{2, 3 | 4, 5\} = \{3 | 4, 5\} = \{2, 3 | 4\} = \{3 | 4\}$

SN在游戏中的应用

对于一个游戏$G$,有如下结论：

• 如果$G > 0$,那么不论先手还是后手，$L$都会获胜
• 如果$G < 0$,那么不论先手还是后手，$R$都会获胜
• 如果$G = 0$,那么谁后手谁获胜

定理：如果$G = (SN)x, H = (SN)y \Longrightarrow G + H = (SN) x + y$