前言

本人其实博弈论也学得不咋的，只是有些蜻蜓点水，并没有深入地研究，而且知识可以说是大部分抄的书上，但是也特作此文以便自己复习和方便各位神犇。

异或

概念

符号：\(\wedge,xor\)

运算法则：对应二进制位下相异为1,相同为0.

异或和：一堆数的异或起来的值。

性质

1. 交换律 \(a\wedge b=b\wedge a\)
2. 结合律 \(a\wedge b\wedge c=a\wedge (b\wedge c)\)
3. \(a=b\Longleftrightarrow a\wedge c=b\wedge c\)
4. 不进位的加法
5. 异或可以与加法减法对应

Nim博弈

基础概念

局面

游戏过程中面临的状态。

先手

游戏中第一个行动者。

后手

游戏中第二个行动者。

必败

在某一局面无论采取什么行动，都会输掉游戏，则称该局面必败。

必胜

在某一局面能采取某种行动，使对手面临必败局面，则称该局面必胜。

Nim博弈

有n堆棋子，第i堆棋子有\(a_i\)颗棋子，对战双方轮流从任意一堆棋子取出任意颗棋子，不能取棋子或不取棋子者失败，问先手是否必胜。

• 注：Nim博弈不存在平局，双方都将采取最优策略，只有先手必胜和必败两种情况。

Nim定理

Nim博弈中，先手必胜当且仅当\(a_1\wedge a_2\wedge...\wedge a_n=\wedge_{i=1}^na_i\neq 0\)。

证明：

博弈论中经常使用数学归纳法证明结论。

考虑边界，没有任何棋子，显然异或和为0。

对于异或和不为0的局面，设\(x=\wedge_{i=1}^na_i\),对于它的最高位考虑，设其为第k位，显然存在一个数\(a_i\)满足其第k位上有1,而令\(a_i\wedge=x\),显然接下来的局面异或和为0,而必然\(a_i\)也变小了，因为它损失了一位上的1，于是因为异或可以和减法对应，我们可以减与异或对应，因此，任何一个异或和不为0的局面都可以将其变为0的局面。

对于异或和为0的局面，显然无论如何选取，必然下一个局面异或和不为0。

总上所诉，当先手在局面异或和不为0的情况下，不妨把异或和不为0的局面记做Q,异或和为0记做q，于是不难得知，接下来的局面发展先手可以做到是\(QqQqQq...q\)，所以后手必然面临必败局面。

同理，当先手异或和为0,接下来的局势发展，后手可以做到\(qQqQ...Q\),此时先手必然面临必败局面。

于是得证。

公平组合游戏(ICG)

ICG定义

若一个游戏满足

1. 由两名玩家交替行动。
2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关。
3. 不能行动的玩家判负。

则称该游戏为公平组合游戏。

解决办法

有向图游戏

定义

给定一个有向无环图(DAG)，图中有唯一一个起点，在起点上放有一枚棋子，两名玩家交替地把这枚棋子沿有向边移动，每次可以移动一步，无法移动者判负，该游戏被称为有向图游戏

性质

任何一个公平组合游戏，都可以被看作有向图游戏。

Mex运算

定义

设S为非负整数集合，定义Mex(S)为求出不属于集合S的最小非负整数的运算，即

\[Mex(S)=\min_{x\in N,x\notin S}x\]

性质

1. 如果\(Mex(S)=x\)，则集合中必然有\(1-x-1\)的数。

SG函数

定义

在有向图游戏中，对于每个节点x，设从x出发有k条有向边，分别到达节点\(y_1,y_2,...,y_k\),定义\(SG(x)\)为x的后继节点的SG函数值构成的集合进行Mex运算后的结果，即

\[SG(x)=Mex\{SG(y_1),SG(y_2),...,SG(y_k)\}\]

特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点S的SG函数值，即\(SG(G)=SG(S)\)。

有向图游戏的和

设\(G_1,G=2,...,G_m\)是m个有向图游戏，定义有向图游戏G，它的行动规则是任选某个有向图\(G_i\)，并在\(G_i\)上行动一步，则G被称为有向图游戏的和。

有向图游戏和的SG函数值被定义为各个子游戏的SG函数值的异或和，即

\[SG(G)=\wedge_{i=1}^nSG(G_i)\]

SG定理

定理1

1. 有向图游戏的某个局面必胜，当且仅当该局面对应的节点的SG函数值大于0.
2. 有向图游戏的某个局面必败，当且仅当该局面对应的节点的SG函数值等于0.

证明：

对于边界考虑，显然末局面即失败的局面，SG函数值为0。

而对于SG函数值不为0的局面，显然它的后继节点存在SG函数值为0的局面，于是对于任意一个SG函数值不为0的局面，都可以到达一个SG函数值为0的局面。

而对于SG函数值为0的局面，显然它的后继节点不可能存在SG函数值为0的局面。于是对于任意一个SG函数值为0的局面，只能到达SG函数值不为0的局面。

总上有，当该局面SG函数值不为0,记不为0局面为\(Q\)，为0局面\(Q\),接下来的局面先手一定可以这样发展\(QqQqQq...q\),使后手面临必败局面。

当该局面的SG函数值为0,后手必然可以使局面按\(qQqQ...q\)发展，而先手必然面临必败局面。

所以得证。

定理2

多个有向图游戏组成的游戏\(\{G_i,n\}\)必胜，当且仅当有向图游戏的和的SG函数值不为0.

证明：

对于末局面，显然有向图游戏的和SG函数值为0。

对于有向图游戏和SG函数值不为0的局面，记\(x=\wedge_{i=1}^nSG(G_i)\),记最高位为第k位，必然有一个\(SG(G_i)\)满足其第k位不为0,而因为Mex操作的性质和异或与减法的对应，我们必然可以将其变为小于\(SG(G_i)\),且接下来的局面有向图游戏的异或和为0.

对于有向图游戏和SG函数值为0的局面，不论怎样操作，必然下一个局面不为0.

于是，对于有向图游戏和SG函数值不为0的局面，记不为0\(Q\),为0\(q\)，先手必然可以按照\(QqQq...q\)发展，使后手必败，同理，为0的局面，后手也可以按照\(qQ...Q\)发展，于是先手必败。

故得证。

套路小结

异或

定位：博弈论中结论常联系的地方

思考方向：

1. 最高位

博弈论证明

1. 数学归纳法
2. 反证法

尾声

笔者本来以为自己能很轻松学会博弈论，结果到现在还是没有真正学会，可能会因此面临\(AFO\)，但是所留下来的学习资源，希望能让读者走的更远。

博弈论小结

原文：https://www.cnblogs.com/a1b3c7d9/p/10852304.html