luogu春令营 D8

博弈论中的基本概念和思考方式

必败态和必胜态

必败态(又称P点)：在游戏中该状态的后继都是必胜态

必胜态(又称N点)：在游戏中该状态的某一后继是必败态

所有游戏的终结点一定是必败态

基本概念

先/后手：游戏开始时先/后操作的一方

先/后手必胜：双方都采取最优策略的同时，先手一定会胜利/失败

这里要注意，参与游戏的两个人一定是足够聪明，所以不会放过任意一个赢的机会，先手必胜和后手必胜都是绝对的

即：先手必胜/败=后手必败/胜

后继状态：当前玩家操作后形成的游戏状态

思考方式

如何判断某一类操作不可能被走？

如果进行该操作之后，对手总能用一步操作来抵消这次操作所带来的影响，所以这类操作不可能被走。

可能无限？

在可能无限进行下去的博弈中，可以先找到能够有限结束的点，之后再反向标记。

经典模型

Naive Game

一共有一堆是n个石子，两个人每次分别从中取一个或两个石子，取到最后一个的人获胜。

这个题算是入门题了，分类讨论。先把n%3，算出余数，如果余数为0，则后手必胜，因为先手不管拿多少个，后手都可以拿(3-x)，这样肯定能拿到最后；如果余数不为0，则先手必胜，先手可以先拿走余数个，这样就变成了后手的必败态了

Nim

从n堆石子里，两人轮流操作，每人每次可以从任意一堆石子中取出任意个，取到最后一个石子的人获胜。

先上结论：当所有堆得石子数xor起来为0时，后手必胜，否则先手必胜。

也就是说，在这个题目中，博弈者想看到的局面是：自己操作之后每堆石子的异或和为0

我们先说这个为什么是这个结论：

当所有堆石子都为0时，异或和也为0，此时谁操作谁输。我们只要一直保证自己操作后每堆石子的异或和为0，就能取得胜利。

那么该怎么拿石子呢？

先把所有堆石子的异或和算出来，设为K，然后算出它最高位的1是哪一位，设为J。

那么根据异或和的计算方法我们可以知道，所有石子堆中，必有一堆第J位为1，设这堆石子中有M个石子，其他堆中的石子异或和为N

那么可列出方程组

N^M=K

M>M^K

所以我们可以通过在这堆中取石子使得M=M^K，来让整个式子异或和为0，证毕。

SG函数/定理

先插播一条和SG定理的证明无关的定理：模仿棋

我们有一个游戏S，有一个游戏X

则(S+S)+X=X

因为如果某人在X中必败，那么他不管在S中做什么，对手都可以在另一个S中模仿，最后把他抵消掉，所以这个游戏就相当于游戏X

SG函数/定理什么时候能用？

对于一个博弈游戏，只要它在游戏的和的意义下与Nim游戏是等价的，我们就可以用SG

游戏的和：

有一个游戏G1，有一个游戏G2，那么我们现在可以同时进行这两个游戏，每一次操作可以在G1里操作，也可以在G2里操作，如果G1不能走，G2还能走，那么游戏没有结束。

那么什么叫做在游戏的和的意义下相等？

我们还有一个游戏Z，可以满足(G1+Z)=(G2+Z)，就是说都是先手必胜或者后手必胜，那么我们可以说对于每一个Z，G1与G2等价。这就是在游戏的和的意义下相等(G1~G2)

那么如果(a~a’)，(b~b’)，我们可以说(a+b)~(a’+b’)

SG函数/定理证明

mex(S)：作用于集合的函数，返回不属于该集合的最小的非负整数

对于每一个博弈游戏，我们都可以把它具象化成一个在DAG上移动棋子的游戏

那么对于nim来说，DAG上每条路的超级汇都对应着nim(0)，而每一个点也都对应着nim(x)

这里nim(x)中的x应该是异或和，nim(x)表示游戏状态

那么我们假设x有一个后继集合{0,1,2,4}

如果我们走到0,1,2不能赢，我们就会去走4，可是我们走到4没用啊，因为对方如果可以走到3，你能选的集合就小于等于{0,1,2}，所以你现在的情况就相等价于mex(sub)，sub为你的后继集合。

所以我们就有了SG函数

sg(x)=mex(sg(sub));

因为对于一个有两堆a,b的nim游戏来说，nim(a)+nim(b)=nim(a^b)

所以我们可以推出SG定理

sg(x)=xor_sigma(sg(son_game));

SG函数/定理应用

要注意，SG函数并不是布尔型的，而是一个整数。

当SG函数不为0时先手必胜，SG函数为0时后手必胜

对于只有一堆的nim，SG(x)=mex(Sub)=x

阶梯博弈

阶梯博弈基于上面提到的nim，所以可以利用SG定理解题

一个 n 级的台阶，每级台阶上有 a[i] 个石头，每人每次可以拿若干个石头到下一级，全部被拿到地面为止，不能操作者输，请问谁会获胜？

这个其实完全可以看做奇数层的nim游戏。两个人在奇数层进行nim游戏，输的那个人就必须要把偶数层的石头移动到奇数层，而赢的人只要模仿棋就能获胜，不解释。

一个 n 级的台阶，每级台阶上有 a[i] 个石头，每人每次可以拿一个石头到下面任何一级？

把每个石子的层数当做一堆，异或起来做nim游戏即可。

Nim-k Game

有若干堆石子，可以同时操作其中的至多k堆石子，每次可以取任意个，谁会赢？

结论为：把n堆石子的石子数用二进制表示，统计每个二进制位上1的个数，若每一位上1的个数mod(k+1)全部为0，则先手必败，否则必胜。

为什么？

其实我们在Nim游戏中取异或和就可以看做在每个二进制位上把1的个数%2

在Nim-k中我们首先可以确定每一位上都没有1的时候是游戏结束，而此时每一位上%(k+1)都是0

在某一次移动中，至少有一堆被改变，也就是说至少有一个二进制位被改变。由于最多只能改变k堆石子，所以对于任何一个二进制位，1的个数至多改变k。而由于原先的总数为k+1的整数倍，所以改变之后必然不可能是k+1的整数倍。

然后对于每一位，我们就可以再通过一次小于等于k个1的改变使游戏回到P点，最后必然取得胜利

但这里要注意一点，SG定理不能运用到这里

SG定理只适用于在和的意义上与nim相等的游戏，但是仔细推一下就知道这两个没法在和的意义上相等，所以我们在nim-k中的解题方法也只适用于nim-k的模型。

树上删边游戏

两个人玩一个游戏：有一棵树，每一次操作需要选择一条边删除，然后把没有和根相连的边和点全部移走，两人轮流操作，无法操作的人输，问谁能赢？

把树转化成链来考虑，对于一条长度为n的独立的链，sg(n)=n

对于一个子树，如果它可以拆成多条链的形式，我们可以把它看做多条链的单独游戏组成的一个大游戏，然后用SG定理

然后我们就可以把这个子树放心大胆的看做一条长度为这几条链异或和的长度的一条链

最后就得出整个树的SG值了

无向图删边游戏

一个图与树的区别就是环如何处理

对于一个单独的偶环，先手必败，因为断掉一条边之后剩下的两条链是一奇一偶，而且该偶数=该奇数+1，SG值必定为1；同理对于一个单独的奇环，SG值必定为0，先手必胜。

所以我们可以用tarjan进行缩点，如果一个强连通分量的边数是偶数，那么就缩成一个SG为1的点，就相当于是一个一条边的链；是奇数的话就相当于是一个点，不做任何操作。