该笔记还未完成整理，待日后继续整理……
博弈论
博弈论简介
在OI中，博弈论一般就是两位玩家玩游戏，游戏有一定规则，双方均在这规则之下进行回合制游戏，并且最终一定会分出胜负。
同时这两位玩家都是超高校级的游戏玩家x，一定会按照当前最优策略进行游戏（就是想方设法让自己赢）。
而你任务则为试着分析出这两位最终的输赢情况。
公平组合游戏
OI中所玩的博弈论游戏，几乎都是“公平组合游戏”(Impartial Combinatorial Games, ICG)。
也就是说：几乎所有博弈论问题都可以建模为基本的ICG来分析处理。
满足以下条件的游戏是ICG：
- 竞争性：只有两名玩家，且两名玩家交替行动。
- 公平性：在游戏进程的任意游戏状态，可以执行的行动只取决于当前局面，而与轮到哪名玩家、以前的任何操作等其他因素无关。
也就是说，两人都有能力让当前游戏状态行动到可到达的所有状态。象棋等常见棋类不属于ICG则正是因为这个原因。
因为每个人只能移动自己势力的棋子，而不是所有棋子。
使得自己不能移动对方的棋子而执行某一行动，从而使能执行的行动取决于轮到哪名玩家。 - 不可回溯性：游戏中的同一个游戏状态不可能再次抵达。
也就是说，ICG为线性游戏，不可能回到之前经历过的某一游戏状态。 - 有穷性：游戏以玩家无法行动为结束，并一定会在有限步后以非平局结束。
必胜必败状态
首先对于公平组合游戏，我们需要了解两个奇妙的状态，他们是：
必胜状态
必败状态
定义
- 必胜状态：处于该状态的玩家，至少能有一种行动，让接下来的状态变为必败状态留给另一位玩家，使其面临必败。
一般称必胜状态为N-Position，简称为N状态。部分也称为非奇异状态、非平衡状态。 - 必败状态：无论怎么行动，只能使接下来的状态变为必胜状态留给另一位玩家，使其必胜。（或者说不可能走到必败状态，使另一位玩家陷入必败从而扭转局势）
一般称必败状态为P-Position，简称为P状态，部分也称为奇异状态、平衡状态。
以下为了区分必胜必败状态与场上游戏状态（局面），特将“游戏状态”统称为“局面”。
性质
由定义，我们可以找到必胜必败状态的基本性质，或者说判别必胜必败状态的基本方式：
- 必胜状态：可以走到某一个必败状态。
- 必败状态：只能走到必胜状态，或说走不到任何一个必败状态。
性质
对于ICG，存在性质：
性质1：游戏中每一种局面，对处于该局面的玩家来说，只有可能是必胜或必败状态，并且无法逆转局势（也就是不存在不确定状态）。
那么由此可以得到推论：
推论1-1：游戏的开始局面也处于必胜状态或必败状态，因此对于先手玩家来说，其胜负是一开始就被决定好了的。
推论1-2：整个游戏的流程是按照：“A处于必胜状态→B处于必败状态→A处于必胜状态→……→A最终获胜”（或者反之）来进行的。
关于终止局面的误区：
- 终止局面：无法行动/没有子状态的游戏状态。
不一定最终局面是必败状态，只是因为一般都规定：终止局面为必败状态——当某一方无法行动宣布败北。
但也完全可以规定终止局面为必胜状态——当某一方无法行动宣布胜利。
要根据题目游戏规则，确定终止局面是必败状态还是必胜状态。
如果只听了结论感觉有点疑惑，可以点开这个看看x……
其实个人对于这里纠结理解了很久，
主要疑惑就在于：
- 为什么一定只存在必胜或必败状态，而不存在一个中间或不确定状态，此时玩家的行动不会决定结果？
- 这给目为什么一开始就决定好了玩家的胜负，不能靠自己的操作改变命运？
- 为什么会有必败状态，处于此状态的玩家为什么不能一转攻势？
等等等等之类的问题……
其实这种疑问主要来自于我们日常玩的游戏都不是ICG，
并且我们也不是智械文明，很难保证每次都能找到并选择最优策略。
首先，对于最难绕过来的第一个问题，其实可以这样想：
首先如果某状态不是“不确定状态”，又因为游戏最终只有某方胜或败的结果，
那么该状态肯定就是必胜或必败状态，
也就是只可能存在：必胜、必败、不确定三种状态。
这点是可以肯定的吧！……
那么排列组合，对于某一状态，其子状态（之后可以到达的状态）只有7种情况：
- 全是不确定状态
- 全是必胜状态
- 全是必败状态
- 既有不确定状态、也有必胜状态
- 既有不确定状态、也有必败状态
- 既有必胜状态、也有必败状态
- 不确定状态、必胜状态、必败状态都有
根据两玩家都总会选择最优策略的思想，以及必胜必败状态的定义可以知道：
- 对于情况②，则该状态一定为必败状态（玩家在这里怎么行动，都会让对方必胜）
- 对于情况③、⑤、⑥、⑦，则该状态一定是必胜状态（玩家在这里只要走向必败状态，就能让对方陷入必败）
所以只有子状态情况为①和④的状态，才能将该状态称为“不确定状态”。
下面来分析这两种“不确定状态”中玩家的选择：
由于玩家都要确保自己尽量能赢，所以自己的回合，除非万不得已只能选择必胜状态行动，将胜利拱手让给对方（即自己陷入了必败状态），否则自己肯定打死不走必胜状态。
因此对于情况④，处于这种“不确定状态”，当前玩家肯定会选择走“不确定状态”。 对于情况①，没什么说的，只能走“不确定状态”。
这两情况发现什么没？
就：若处于“不确定状态”，玩家只会选择继续走“不确定状态”！
那么场面就会变得奇怪了起来：
明明ICG的定义就说好最终会分出胜负，但却一直处于“不确定状态”。
因此直接異議あり！断言不可能存在“不确定状态”。
可能有人最后这里还有点小疑惑：
如果就让双方就这样一直在“不确定状态”下反复横跳，直到最终有人只能走那个“必胜状态”输掉游戏怎么样？
请牢记：如果只能走必胜状态，那么该状态就是必败状态了。
【感觉有点哲学是吧23333……
那么如果第一个问题明白了，其他问题也就好解决了。
因为不存在不确定状态，命运就像链条一样被决定好了，不然怎么叫必胜和必败呢？
注意：对于必胜状态和必败状态，我们统一是针对于先手来分析的。
由此自然而然我们可以想到一种解决博弈问题的思路：
由题目要求得到终止局面是必胜状态还是必败状态，
再由终止局面反推，得到某一局面是必胜状态还是必败状态。
这种思路也就是搜索解法。
但需要注意的是有可能不能直接分析出终止局面是（先手）必败状态还是必胜状态，
需要先倒推到终止局面的前驱局面，分析这一局面是什么状态，才能得到终止局面是什么状态。
或者不用分析终止局面是什么状态，直接由终止局面的前驱局面来倒推分析。
如下例中的“皇后问题”。
博弈状态图
我们将每一个局面视为一个节点**，再从每个局面向它的后继局面连边，这样就能得到一个博弈状态图。
结合上面提到的倒推解题思路，我们可以从终止局面节点搜索，得到各种局面的状态。
可将处于必败状态的节点成为P节点，必胜状态的节点成为N节点。
引例——挪动皇后游戏
游戏规则：
将一个皇后放在棋盘（任意$n*n$大小）上某一格子内，皇后只能向左、下、正左下（即同时向左和向下走相同格数）走任意格且至少移动1格，最先到达最左下角的玩家胜利。
我们就这个引例来分析其博弈状态图。
先可将局面抽象为皇后在棋盘上的坐标，如$(2,3)$、$(5,5)$。
则对于任意局面$(n,m)$，其后继局面为：
- $(n-k,m) (k∈N^+)$
- $(n,m-k) (k∈N^+)$
- $(n-k,m-k) (k∈N^+)$
我们可以用棋盘本身来代表状态图。
而对于处于坐标$(n,m)$格子上的皇后，其可移动局面即为横向向左，竖向向下、斜向向左下直线的所有格子。
那么对于这个问题来说，其终止局面为$(0,0)$。
而从$(0,0)$反推，其右方、上方、右上方的节点均对于（先手）必胜状态。
则由$(0,0)$局面易得出处于N状态（必胜状态）的局面，如下图绿色区域表示：
接下来根据必胜必败状态的性质，可以发现有且仅有$(1,2)$、$(2,1)$这两点，无论怎么移动都只能到达必胜状态（如蓝箭头所示）。
因此这两点即为P节点。
接下来我们又可以从找到的P节点倒推，得到新的N节点（其右、上、右上的节点，如蓝箭头所示）。
（为了区别将第一次倒推出的N节点颜色加深了。）
最终这么分析下去，会得到如下博弈状态图。
其中蓝色节点为必胜节点，白色部分为必败节点。
图片来自于Matrix67的笔记“捡石子游戏、Wythoff数表和一切的Fibonacci数列”。
可能有同学就会发现，在这里的P节点有点规律的样子，大致好像连成了一条直线。
其实这个发现是正确的，这个游戏也叫做“威佐夫博弈”（Wythoff Game），将在后面的部分具体讲解。
作用
对于任何ICG，其都可以转化为一种“有向图游戏”。
有向图游戏：
给定一个有向无环图，图中有一个唯一的起点（初始局面），在起点上有一枚棋子。
两名玩家需要交替地将该棋子沿着有向边进行移动，每次必须移动一步。
无法移动者（来到终止局面）将被判负（也有可能判赢）。
具体转换方法为：
- 将每一种局面看成有向无环图的节点。
- 对于每一种局面，和能合法到达的下一种局面，将这两节点建立有向边。
这样，我们就能将各种博弈问题转化为统一的一种模型，方便我们思考与解决。