| 😊 | Powered By HeartFireY | Game |
一、博弈论简介
博弈论 ，是经济学的一个分支，主要研究具有竞争或对抗性质的对象，在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。
通俗地讲，博弈论主要研究的是：在一个游戏中，进行游戏的多位玩家的策略。
对于算法竞赛中的博弈问题，一般具有以下特征：
- 博弈模型为两人轮流决策的非合作博弈。即两人轮流进行决策，并且两人都使用最优策略来获取胜利。
- 博弈是有限的。即无论两人怎样决策，都会在有限步后决出胜负。
- 公平博弈。即两人进行决策所遵循的规则相同。
二、基本概念
1.公平组合游戏
公平组合游戏的定义如下：
- 游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；
- 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；
- 游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。
大部分的棋类游戏都 不是 公平组合游戏，如国际象棋、中国象棋、围棋、五子棋等（因为双方都不能使用对方的棋子）。
公平游戏具有一个重要的性质：
如果一个游戏者能够讲状态A变为状态B，那么另外一个游戏者必然也能实现这样的操作。
2.博弈图和状态
1).博弈图
如果将每个状态视为一个节点，再从每个状态向它的后继状态连边，我们就可以得到一个博弈状态图。
如上图，我们假定存在博弈状态，表示局面为的状态，则我们可以根据状态的转移确定博弈图。
易知：博弈图必为DAG(有向无环图)。
2).状态
我们首先定义博弈中常用的两种状态：必胜态、必输态
- 必胜态：先手必胜的状态
- 必败态：先手必败的状态
同时我们对决策局面进行定义：
- **P局面：**即为Previous-position，上次移动的人具有必胜策略的局面(先手必败)。
- 任何无法移动的局面都是
P局面
- **N局面：**即为Next-position，当前移动的人具有必胜决策的场面(先手必胜)。
- 可以移动到
P局面
N局面
- 所有移动都导致移动到
N局面
P局面
有了状态的定义，对于博弈图中的状态点我们可以继续定义：
- P点：必败点，某玩家位于此点，只要对方无失误，则必败
- N点：必胜点，某玩家位于此点，只要自己无失误，则必胜
通过推理，我们可以得到以下三条定理：
-
定理 1
P局面
-
定理 2
N局面
P局面
-
定理 3
P局面
N局面
直接这样阐述有些难以理解，我们继续进行解释：
对于
定理 1
，如果游戏进行不下去了，那么这个玩家就输掉了游戏。对于这个状态是十分容易理解的–大多数游戏在此时已经无法继续进行(终结局面)，比如N堆石子任意取游戏，当N堆石子均为空时不会再出现任何的后继状态，此时的状态为必胜状态；
如图，红框内所示的状态点全部为“终结局面”
对于
定理 2
，如果该状态至少有一个后继状态为必败状态，那么玩家可以通过操作到该必败状态；此时对手的状态为必败状态——对手必定是失败的，而相反地，自己就获得了胜利。
换句话说，对于公平游戏而言，只有让对手走到必败状态，自己才能赢
对于
定理 3
，如果不存在一个后继状态为必败状态，那么无论如何，玩家只能操作到必胜状态；此时对手的状态为必胜状态——对手必定是胜利的，自己就输掉了游戏。
换句话说，你能到达必胜点且无法向必败点转移，那么你的对手也能到必胜点，这样你就输了。
如果博弈图是一个有向无环图，则通过这三个定理，我们可以在绘出博弈图的情况下用 的时间（其中 为状态种数，
三、博弈模型
1.巴什博弈
巴什博弈属于基本的博弈问题，其典型特征为：
给定堆物品，两个人轮流从这堆物品中取物品，规定每次最少取个，最多取个，最后取光者为胜。
当时，由于一次最多只能取个，所以无论先取者拿走多少个，后取者都能一次拿走剩余的物品，后取者取胜；
所以当一方面对的局势为（其中为任意自然数，)，如果先取者要取走个物品，如果后取者取走个，那么后取者只要取走个，结果剩下个，以后保持这样的取法，那么先取者肯定获胜，总之，要保持给对手留下的倍数，就能最后获胜。
结论1：若，则先手必败，否则先手必赢
一种常见的变形是“问题改为最后取光的人输”。那么此时的结论：
时先手必输。
2.威佐夫博弈
威佐夫博弈问题具有的典型特征是：
有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
如何解决威佐夫博弈问题？
首先，我们定义表示两堆物品的数量并称其为局势，如果甲面对，那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势，前几个奇异局势为。任意给定一个局势，如下公式可以判断其是否为奇异局势：
面对非奇异局势，先手必胜；面对奇异局势，先手必败。
满足上述公式的局势性质：
我们定义为第个奇异局势。
(1).任何自然数都包含在一个且仅有一个奇异局势中；
(2).为前个奇异局势中没有出现过的最小正整数，；
(3).任何操作都会将奇异局势转化为非奇异局势；
(4).可以采取适当的方法将非奇异局势转化为奇异局势。
我们对以上的分析进行总结，可以得出威佐夫博弈的通解形式：
对于给定的两堆石子，排除操作失误的客观因素，那么先手必败，当且仅当：
我们可以很惊奇的发现：其中的就是我们所熟悉的黄金分割数！
实际上，黄金分割数在其他许多场景中都有很广泛的应用，利用好黄金分割相关的结论能够很轻松的解决许多问题。
在许多场景下，我们面对的并不是奇异局势，对于一部分问题，我们可以将非奇异局势转化为奇异局势。
假设面对的局势是。（大于等于）
如果 ，则同时从两堆中取走 个物体，就变为了奇异局势；
如果 ,那么，取走个物体，即变为奇异局势；
如果 则同时从两堆中拿走 个物体(详见注释1)变为奇异局势；
如果 则从第一堆中拿走多余的数量 即可；
如果, 分两种情况：
第一种，从第二堆里面拿走 即可；
第二种，从第二堆里面拿走 即可（交换）。
如何理解这个转换？
因为奇异局势的项数是有 的差决定，每一个奇异局势的项数都是独一无二的。
也就是说，我们 只能将转化为。
因为他们的差是确定的始终都是 ，故可以转化为 第 项。
由此我们可以 将 转化为奇异局势 也就是。
所以我们可以逆推得出，只要将 两边 同时减去即可。
注：以上局势变换引用自博客 Wythoff Game 非奇异局势变为奇异局势
3.斐波那契(Fibonacci)博弈
斐波那契博弈的典型特征是：
给定一堆个数为的石子，两个玩家轮流取石子，满足：
- 先手不能在第一次把所有的石子取光；
- 第一次取完后的每次可以取得石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)；
- 取走最后一个石子的人为玩家。
如何解决这一类博弈问题？
首先先给出结论：当为斐波那契数的时候，先手必败，即存在先手的必败态当且仅当石头个数为Fibonacci数。
下面给出证明：
根据“Zeckendorf定理”（齐肯多夫定理）：任何正整数可以表示为若干个不连续的Fibonacci数之和。如，我们看看这个分解有什么指导意义：假如先手取2颗，那么后手无法取5颗或更多，而5是一个Fibonacci数，那么一定是先手取走这5颗石子中的最后一颗，同理，接下去先手取走接下来的后21颗中的最后一颗，再取走后55颗中的最后一颗，那么先手赢。
反证：如果是Fibonacci数，如：记先手一开始所取的石子数为
（1）若 颗（也就是的向前两项），那么一定后手赢，因为。
（2） 时剩下的石子数介于到之间，它一定不是一个Fibonacci数，把x分解成Fibonacci数：，若，如果，那么对B就是面临x局面的先手，所以根据之前的分析，后手只要先取个即可，以后再按之前的分析就可保证必胜。
判断斐波那契数的方法可以采用通项公式法或遍历法。如果数据范围大会卡时间则考虑矩阵快速幂优化等。
4.Nim博弈
①.Nim游戏
Nim游戏是一个典型的博弈问题，建立在Nim游戏基础上的博弈一般都具有相同的框架特征。
堆物品，每堆有
例如，如果现在有 堆物品，而每堆分别有 个，那么可以取走第 堆中的 个物品，局面就变成了 ；或者也可以取走第 堆的 个物品，局面就变成了 。
如果现在的局面为 ，甲取走了第 堆的
②.Nim和
首先回顾“博弈图”。我们通过绘画博弈图，可以在
显然，这样的推导方式时间复杂度是非常高的，我们需要换一种思路进行推导。
定义 Nim 和 。
那么当且仅当 Nim 和为
| --> 如何证明Nim和的正确性？为什么异或值会和和状态的胜负有关？ |
为了证明该定理，只需要证明下面三个定理：
-
定理 1
-
定理 2
-
定理 3
对于
定理 1
，没有后继状态的状态只有一个，即全 局面。此时 。
对于
定理 2
，不妨假设 。如果我们要将 改为 ，则 。
根据异或定义，一定有奇数个 在 在二进制下的最高位为 。满足这个条件的 一定也满足 ，因而这也是个合法的移动。
对于
定理 3
，如果我们要将 改为 ，则根据异或运算律可以得出 ，因而这不是个合法的移动。
四、公平组合博弈(ICG)与有向图游戏
1.公平组合博弈-定义
- 两人参与
- 游戏局面的状态集合是有限的
- 对于同一个局面，两个游戏者可操控的集合完全相同
- 游戏者轮流进行游戏
- 当无法进行任何操作时游戏结束，此时不能进行操作的一方为输方
- 无论游戏如何进行，总可以在有限的步数之内结束游戏
实际上，所有的公平组合博弈(ICG)都可以被转换为有向图游戏。
2.ICG模型
给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手轮流交替移动棋子(沿着有向边移动)，无法移动者判定为输家。
我们一般将这种游戏框架模型统一归属为公平组合游戏(ICG).
我们不难发现：任何一个ICG都可以通过把每个局势堪称一个顶点，对每个局势和它的子局势连一条有向边来抽象成这个"有向图游戏"。
3.解决方案(SG函数与SG定理)
现在我们假定给出两个游戏和。如果我们只知道单个游戏的状态和状态是无法正确的进行组合游戏的。这是由于状态和状态的和总是状态；状态和状态的和总是状态；但是状态和状态的和的状态是无法确定的。
因此我们需要对两个状态进行推广。
1.SG函数(Sprague-Grudy’s Function)
首先我们引入函数的定义：
定义 函数的值为不属于集合
例如 ，。
对于状态 和它的所有 个后继状态 ，定义 函数：
2.SG定理(Sprague-Grudy’s Theorem)
根据函数，我们可以导出定理：对于由 个有向图游戏组成的组合游戏，设它们的起点分别为 ，则有定理：当且仅当
接下来，我们对定理的性质进行研究：
-
所有的终结点所对应的顶点，其值为，因为它的后继集合为空集。
即：所有的终结点都是必败点
-
对于一个的顶点，它的所有后继都无法满足。
即：无论如何操作，从必败点（P点）都只能进入必胜点（N点）
-
对于一个的顶点，必定存在一个后继点满足
从任何必胜点（点）操作，至少有一种方法可以进入必败点（点）//就是那种我们要走的方法。
3.应用
(1).将Nim游戏转换为有向图游戏
我们可以将一个有 个物品的堆视为节点 ，则当且仅当 时，节点 可以到达 。
那么，由 个堆组成的 Nim 游戏，就可以视为
根据上面的推论，可以得出 。再根据 SG 定理，就可以得出 Nim 和的结论了。
(2).关于步数的结论
- 可选步数为的连续整数，直接取模即可，;
- 可选步数为任意步，;
- 可选步数为一系列不连续的数，用
以将一个有 个物品的堆视为节点 ，则当且仅当 时，节点 可以到达 。
(2).关于步数的结论
- 可选步数为的连续整数，直接取模即可，;
- 可选步数为任意步，;
- 可选步数为一系列不连续的数，用