博弈论
- 以下主要内容来自于对集训队论文《组合游戏略述——浅谈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函数是对游戏图中每一个节点的评估函数。满足如下等式：
其中(mex(x_1, x_2...x_t))是定义在非负整数集合上的操作，自变量是任一非负整数集合。得到的结果是不属于该集合的最小自然数。即：
性质：
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.
(ecause)当前局面的SG函数为0，又(ecause)SG函数性质(1)
( herefore)它所能转移到的任何一个局面的SG值不为0
(ecause)当前局面的SG值为0且游戏中某个单一游戏的SG函数大于1.
( herefore)当前局面中必定至少有2个单一游戏的SG函数大于1
又(ecause)每次之多只能更改一个单一游戏的SG值
( herefore)它能转移到的任何一个局面都至少有一个单一游戏的SG值大于1
由上述得：情况一所能转移到的任何一个局面都为先手必胜局
情况二：局面的SG函数不为0且游戏中没有单一游戏的SG函数大于1
可以发现，当前局面一定有奇数个游戏的SG值为1，其余游戏的SG值为0.
1，将某个单一游戏的SG值更改为大于1的数。
(ecause)转移前没有单一游戏的SG值大于1，而转移将某个单一游戏的SG值更改为大于1的数
( herefore)转移后的局面一定有且只有一个单一游戏的SG值大于1
( herefore)后继局面的SG值一定不为0
因此，后继局面一定为先手必胜局
2，将某个单一游戏的SG值更改为0或1.
(ecause)转移是将某个SG值为0的单一游戏改成SG值为1的单一游戏，或将某个SG值为1的单一游戏改成SG值为0的单一游戏。
( herefore)转移后的局面一定有偶数个SG值为1的单一局面,且不含有SG值大于1的局面(什么意思？？？)
( herefore)后继局面一定为先手必胜
情况三：局面的SG函数不为0且游戏中某个单一游戏的SG函数大于1.
1，局面中只有1个单一游戏的SG值大于1。
选择更改SG最大的单一游戏，可以将其更改为0或1来保证转移后的局面有且只有奇数个SG值为1的单一游戏。(同anti-nim游戏)
2，局面中至少有2个单一游戏的SG值大于1。
根据SG函数性质2，总存在一种决策可以将后继局面的SG值变为0.
(ecause)局面中至少有2个单一游戏的SG值大于1
又(ecause)每次最多只能改变一个单一游戏的SG值。
( herefore)后继局面中至少有一个游戏的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)函数来表示这个值
定理：对于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)个奇异局势为：
令(k)表示奇异局势的编号，则((a[k], b[k]))表示第(k)个奇异局势，其中((0, 0))为第(0)个奇异局势。
可以发现：(a[k])是未在前面出现过的最小自然数，而(b[k] = a[k] + k).
性质：任何自然数都包含在一个，且仅有一个自然数里。
证明：(ecause a[k])是未在前面出现过的最小自然数，所以有
所以(b,a)都不会重复，显然会包含所有的自然数。
结论：奇异局势满足如下等式：
斐波那契博弈
问题：有一堆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}).
(ecause 0 le 0 quad herefore {0 | 0})不合法
(ecause {|0} < 0 < {0|} quad herefore{|0} = -1, {0|} = 1)
利用0, 1, -1可以构造出7个合法的SN：
(ecause {1 | } > 1, {| 1} < -1 quad herefore {1 | } = 2, {| 1} = -2)
(ecause 0 < {0 | 1} < 1)且({0 | 1} + {0 | 1} = 1 quad herefore {0 | 1} = frac{1}{2}) 同理({-1 | 0} = - frac{1}{2})
(Delta)如此类推，可以构造出所有形如(frac{j}{2^k})的有理数,定义达利函数为：
定理：对于一个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)