博弈论入门

一、基础

1、公平组合游戏：是一个满足以下条件的游戏：由两名玩家交替行动；任意时刻每名玩家可进行的的操作规则相同；游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束

2、先手必胜状态和先手必败状态，必胜点（N）和必败点（P）：

（1）、如果后手有一个以上的必败点，那么前驱是必胜点

（2）、如果后手全为必胜点，那么前驱为必败点

由此可以进行NP分析

3、博弈图：给定一个有向图，在图中唯一的起点处有一个棋子，双方轮流按照有向图的边移动棋子，当一方无法移动棋子时则判输，我们称这个图为博弈图。

任何一个公平组合游戏都可以转化为有向图游戏，我们可以把每一个状态看作一个点，对于每一个状态可以进行的操作作为从该点出发的边

4、尼姆博弈（Nim博弈）：

给定N堆物品，第i堆物品有ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜

（1）、最优策略：若在某一局面下存在某种行动，使得行动后对手面临必败局面，则优先采取该行动

（2）、我们定义Nim和为a1​⊕a2​⊕...⊕an。结论：当和为0时，后手必胜，和不为零时，先手必胜

证明：

①若ai的异或和为0，为了使每一位数异或后为0，则对于所有ai在二进制下第k位有偶数个1

②在一次行动中，只能使偶数个（大于等于2）变为奇数个（或奇数个变为偶数个），在偶数个（大于2）的状态时不能一次取完

③因此如果ai的异或和为0且先手取了一定数量的物品（不可能直接获胜），此时后手只需要减少其他堆中的物品并且使异或和再次为0（可能直接获胜，或者到达后手不能直接获胜的状态），故当异或和为0时，后手必胜222

二、SG函数

1、mex运算：若S是一个非负整数的集合，定义mex(S)为求出不属于集合S的最小非负整数的运算

2、SG函数：是对博弈图中每一个结点的评估函数，我们规定终点的SG值为0，除此之外每个结点的SG值为其所有子结点的SG值集合经过mex运算得到的值，即如果y1，y2，....yk为x的子节点，则SG(x)=mex{SG(y1),SG(y2),....,SG(yk)}

3、特别的，整个有向图G的SG函数值被定义为有向图起点s的SG函数值

4、若SG(x)=0，则为必败状态，反之为必胜状态

5、对于1个大的博弈，我们将它拆成许多个小博弈，其实就相当于对这些个小博弈先画出sg(x)的值，然后这几个小博弈就和Nim博弈中的几个石头堆一样，将他们异或起来即可

6、我们可以通过计算机打SG表，从中寻找规律，确定何时先手必胜、必败

7、可以通过dfs来计算SG函数

三、博弈模型

1、巴什博弈：

有1堆石子，总个数是n，两名玩家轮流在石子堆中拿石子，每次至少取1个，至多取m个。取走最后一个石子的玩家为胜者。判定先手和后手谁胜

 结论：若n % (m + 1) == 0则先手必败，否则先手必胜

2、威佐夫博弈：

有两堆石子，石子数可以不同。两人轮流取石子，每次可以在一堆中取，或者从两堆中取走相同个数的石子，数量不限，取走最后一个石头的人获胜。判定先手是否必胜

在此我们称先手必败点为奇异节点，例如（1，2）、（3，5），我们可以将两堆石子的个数放在xy轴坐标上，对于奇异节点（0，0），所有可以通过一次操作到达奇异节点的点即为必胜点，即（x + i，y）、（x，y + i）、（x + i，y + i），如果一个节点经过操作后只能到达必胜点，则该节点为必败点

结论：若两堆石子(a, b)，a >  b，则先手必败当且仅当(b − a) × (sqrt(5) + 1)/2 ​= a

 3、斐波那契博弈：

有一堆个数为 n ( n ≥ 2 ) n(n\ge 2)n(n≥2)的石子，游戏双方轮流取石子，规则如下：

先手不能在第一次把所有的石子取完，至少取1颗；

之后每次可以取的石子数至少为1，至多为对手刚取的石子数的2倍。

约定取走最后一个石子的人为赢家，求必败态

结论：先手必败当且仅当石子数为斐波那契数

4、Anti-SG游戏

决策集合为空的游戏者获胜，也可以理解将所有集合变为空的游戏者即为失败

结论：

先手必胜当且仅当：

（1）、游戏的SG函数值不为0且游戏中某个单一游戏的SG函数值大于1

（2）、游戏的SG函数值为0且游戏中没有任意一个单一游戏的SG函数值大于1 

5、Muti-SG游戏

6、Every-SG游戏

7、阶梯博弈

地面表示第0号阶梯。每次都可以将一个阶梯上的石子向其左侧移动任意个石子，没有可以移动的空间时（及所有石子都位于地面时）输

 对于每次对手的移动，若移动偶数号阶梯，则我们将其移动的石子再向下移动到偶数号，也就是说移动只有奇数到奇数，这样就可以保持奇数堆不变，如果对方移动奇数堆号阶梯，则类似尼姆博弈，所以此时奇数堆的石子就相当于尼姆博弈中的n堆石子，也就是说，将第奇数堆进行异或和，就可以得到SG值，从而判断

8、对称博弈

给你n个硬币排成一圈，编号1-n,只能翻转连续的1~k个的硬币。翻最后一枚硬币者赢

特判是否可以一步取完和k=1情况，之后可以在两回合将一圈硬币分为两块个数相同的硬币堆，然后进行和对方一样的取硬币策略，从而保证后手必胜