博弈论小结

目录

前言

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

异或

概念

符号：(wedge,xor)

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

异或和：一堆数的异或起来的值,如({x_1,x_2,..,x_n})的异或和为(x_1wedge x_2wedge ...wedge x_n=wedge_{i=1}^n x_i)。

异或和图的性质

  1. 你可以凭空到达任意一个位置
  2. 环等同于异或空间
  3. 链可以由环更改路径

性质

  1. 交换律 (awedge b=bwedge a)
  2. 结合律 (awedge bwedge c=awedge (bwedge c))
  3. (a=bLongleftrightarrow awedge c=bwedge c)
    1.推论： 不同的数异或同一个数得到结果不同
  4. 不进位的加法
  5. 异或可以与加法减法对应

线性基

性质：

  1. 线性基由原序列的一些数构成
  2. 异或和为0即线性基无法加入该数（应用：异或和为0的判断）
  3. 异或空间为2的线性基个数的次方，多次异或没有意义
  4. 有n个 不同的 数，设线性基个数k，每个数重复(2^{n-k})次。

证明：

对于k个基，剩下的n-k个数每个数与基所产生的数进行异或，必然值各不相同,所以必然每个值重复一次，于是总的来说重复(2^{n-k})次。

Nim博弈

基础概念

局面

游戏过程中面临的状态。

先手

游戏中第一个行动者。

后手

游戏中第二个行动者。

必败

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

必胜

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

Nim博弈

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

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

Nim定理

Nim博弈中，先手必胜当且仅当(a_1wedge a_2wedge...wedge a_n=wedge_{i=1}^na_i eq 0)。

证明：

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

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

对于异或和不为0的局面，设(x=wedge_{i=1}^na_i),对于它的最高位考虑，设其为第k位，显然存在一个数(a_i)满足其第k位上有1,而令(a_iwedge=x),显然接下来的局面异或和为0,而必然(a_i)也变小了，因为它损失了较高的一位上的1，于是因为异或可以和减法对应，我们可以减与异或对应，因此，任何一个异或和不为0的局面都可以将其变为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_{xin N,x otin S}x ]

性质

  1. 暴力求时间复杂度(O(n))
  2. 如果(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))。

另外对于失败局面的SG函数值定义为0.

有向图游戏的和

设(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)wedge=x),我们必然可以将其变为小于(SG(G_i)),且接下来的局面有向图游戏的异或和为0.

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

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

故得证。

理解

Nim游戏

其实Nim游戏就是特殊的公平组合游戏（ICG），自然也可以利用公平组合游戏证明，它是多个有向图游戏组成的游戏，末状态一定每个子游戏是全部面临必败局面。

证明：

在Nim游戏中，对于一个子图而言，即有多少枚棋子，不妨有i枚棋子记做(i),于是它的SG函数值记做(SG(i))

对于初始状态，即必败局面，必然(SG(0)=0),设(SG(0)=0,SG(1)=1,...,SG(i-1)=i-1),设(SG(i))它所算出用的集合为({SG(0),SG(1),...,SG(i-1)}),即({0,1,2,...,i-1}),不难得知结果为i，于是根据数学归纳法(SG(i)=i)。

根据ICG定理2,公平组合游戏的和为(wedge_{i=1}^n SG(a_i)=wedge_{i=1}^n a_i))，故得证。

套路小结

异或

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

思考方向：

  1. 最高位

博弈论证明

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

问题转化办法

  1. 阶梯博弈，捆绑法

习题

新新Nim游戏

有k组棋子，每组棋子有若干堆棋子，给出(a[i][j])，表示第i组棋子第j堆棋子的棋子个数，两名玩家轮流行动，每次操作可以可以选择一组中的一堆棋子拿走任意多颗棋子，不能行动的玩家失败，询问先手是否必胜，(sum_{i=1}^k|a[i]|leq 10^8)。

勇士

给出一个(n imes m)的网格图，有些位置存在障碍物，显然坐标已经给出，有一个棋子放在位置((1,1))，两名玩家轮流操作，每次可以选择棋子向下移动或者向右移动，不能移动的玩家判负，询问先手是否必胜，(n imes mleq 10^8)。

尾声

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

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/a1b3c7d9/p/10852304.html