博弈论入门学习笔记

几个月前的笔记，才疏学浅，仅供参考~

基本概念 #

PN 点 #

什么是 PN 点 #

P 点：前一个选手（previous person) 将取胜的点，即必败点。
N 点：下一个选手（next person) 将取胜的点，即必胜点。

注意：PN 点是相对于某个点的属性，与先后手无关，所以我们可以说先手的 P 点或后手的 P 点，也就是说无论是先手还时后手，走到 P 点都是必败的。

PN 点的属性 #

所有终结状态均为 P 点。
从任何 N 点都至少有一种方法进入 P 点。（当前玩家的必胜点一定可以走到下一个玩家的必败点）
从 P 点只能进入 N 点。（如果能走到 P 点的话就相当于胜负局势变化了，这样就不是必败的了）

注意：这里说的都是走到最后状态的玩家获胜的游戏。

SG 函数 #

如果游戏条件比较复杂，为了判断每个点的胜负状态，就需要引入 SG 函数。

定义： #

$\operatorname{sg}(u)=\operatorname{mex}\{\operatorname{sg}(v)\}$

其中 v 为 u 的后继状态，mex 函数是作用于整数集合的函数，函数值是不属于该集合的最小自然数。

$\operatorname{mex}(A)=\min\{k | k\in\complement_NA\}$

那么，终止状态的 SG 值显然为 0，并且 SG 值为 0 的状态就是 P 状态，SG 值不为 0 的状态就是 N 状态。证明则非常显然，SG 值为 0 的状态，说明它的所有后继状态都不为 0，也就是它只能转移到非 0 状态，而 SG 值不为 0 的状态则不一样，后继状态一定有 0，可能有其他非负整数。那么 SG 值为 0 的状态就是必败状态的定义，SG 值不为 0 的状态就是必胜状态的定。

求法 #

从定义可以看出 sg 函数使用的递归定义，所以我们既可以从 sg 为 0 的状态递推，也可以采用递归的方法求。

有些题目的 sg 函数的有规律的，通过打表或者思考可以发现规律;有些是没有规律的，需要自己写 sg 函数来打表。

一般的 sg 函数打表模板：注：需要打表的一般是简单的取石子游戏，且在取石子的数量上有限制。这种问题的状态方便用数字表示，所以实现简单。

bool flag[N];
int sg[N];
void getsg(){
    for1(i,N){
        ms(flag,0);
        //枚举后继状态
        for(int j=1;j<=K;j++){//K 为能取不同个数石子的种类数
            flag[sg[i-shizi[j]]]=1;
        }
        //找 mex
        forn(j,N){
            if(flag[j]==0){
                sg[i]=j;
                break;
            }
        }
    }
}

有规律的 sg 函数：HDU-1847

打表可发现 sg 函数是 0，1，2，0，1，2……变化的。

稍微难一点找规律：LightOJ-1296

规律：如果 n 是奇数 gx(n)=gx(n/2),如果为偶数，gx(x)=x/2;

需要打表的题：HDU-1848

巴什博弈 #

题目描述 #

只有一堆 n 个石子，两个人轮流从这堆石子中取石子，规定每次至少取一个，最多取 m 个，最后取完的人获胜。

分析 #

当 n = m+1 的时候，由于先手最多取走 m 个，无论其取走多少个，剩下的后手均可以一次取完，显然后手胜。
根据以上分析，我们可以将 n 写成 $n=k(m+1)+r$ 的形式。对于先手玩家，我们可以取走 r 个，给对方造成剩下 $k(m+1)$ 的情形。此时无论对手取走多少个，假设对手取走 n 个，我们一定可以做到取走 $m+1-n$ 个，此时剩下 $(k-1)(m+1)$ 个，那么留给对方又是 (m+1) 的整数倍，如此就可以保证先手取胜。

结论 #

当 $n\mod(m+1)!=0$ 时，先手胜，否则后手胜。

威佐夫博弈 #

题目描述 #

有两堆各若干个石子，两个人轮流从某一堆或者两堆中取同样多的物品，规定每次至少取一个，多着不限，最后取完石子的人获胜。

分析 #

我们用 $(a_k,b_k),a_k \leq b_k,k \in[0,n]$ 表示一种局势，先手必输的局势我们称为奇异局势，显然 $(0,0)$ 是一种奇异局势。那么 $(0,k),(k,k)$ 必然是非奇异局势，因为可以通过一步到达奇异局势。我们可以发现 $(1,2)$ 不论如何操作都将成为非奇异局势，所以 $(1,2)$ 是下一个奇异局势，所以 $(1+k,2),(1,2+k),(1+k,2+k)$ 也都是非奇异局势，以此类推我们可以发现之后的几个奇异局势是 $(3,5),(4,7),(6,10)$ 。

通过观察我们可以发现 $a_0=b_0=0,a_k$ 为前面没出现过的最小正整数， $b_k=a_k+k$ 。

奇异局势有以下三条性质

任何正整数都包含在奇异局势中。
任何操作都会将奇异局势变为非奇异局势。
采取适当的操作可以将非奇异局势变为奇异局势。

事实上， $a_n,b_n$ 是一对 beatty 数列。

Beatty 数列 #

取两个无理数 $\alpha,\beta$ 使得 $\frac 1 \alpha+\frac1\beta=1$ 。

一对 Beatty 数列就是 $a_n=\lfloor n\alpha\rfloor,b_n=\lfloor n\beta\rfloor$ 。

Rayleigh 定理 (Beatty 定理) #

$a_n,b_n$ 划分正整数，也就是说每个正整数只在两个数列中出现一次。

我们再回到这个问题， $\because a_n+n=\lfloor n\alpha\rfloor+n=b_n=\lfloor n\beta \rfloor$

$\therefore \lfloor n \alpha \rfloor+n= \lfloor n \beta \rfloor$

$\therefore \lfloor n \alpha+n \rfloor= \lfloor n \beta \rfloor$

$\therefore \beta = \alpha+1$

根据 $\frac 1 \alpha+\frac 1 {\alpha+1}=1$ 解得 $\alpha=\frac {\sqrt 5+1} 2=\phi$ 。我们可得到通项 $a_n=\lfloor n \phi \rfloor,b_n=a_n+n$

对于任意局势 $(x,y),x\leq y$ 我们只需判断 $\lfloor (y-x)\phi\rfloor\stackrel{?}{=}x$

常见的几类问题 #

给出局势判断是否是奇异局势。
给出局势 $(x,y),x\leq y$ ，判断是否先手赢，若赢，给出第一步走法。

例题：HDU-2177

先把所有奇异局势求出来，然后判断是不是，如果不是：

先判断能否两堆同时取，设 $k=y-x$ 判断 $x-a_k?=y-b_k(x-a_k>0)$ 如果成立就可以同时取到 $(a_k,b_k)$ 。
判断取一堆的。先判断 $x?=a_n\land y?>b_n$ ,如果成立就可以取到 $(a_n,b_n)$ ,如果不成立那么 $a=b_n$ ，此时 $y>a_n$ ，所以可以取到 $(a_n,b_n)$ 。

Nim 博弈 #

题目描述 #

有 n 堆石子，数量分别为 $x_1,x_2,...,x_n$ 每人每次可在任意一堆中取走任意数量（不少于 1）的石子。

结论 #

Nim 游戏中先手必败当且仅当 $x_1XOR x_2XOR...XORx_n=0$ 时

扩展 #

事实上，我们可以将 Nim 游戏视做多个子游戏的合集，根据 Nim 定理，总游戏的 sg 值等于所有子游戏的 sg 值的异或和。

证明 #

异或有一条性质， $xXORy=xXORz \implies y=z$ ，根据 sg 的定义，子游戏走一步，sg 值必然发生改变，根据异或的性质所以总游戏的 sg 值也一定发生改变，0 一定会变成非 0，非 0 经过某一步可以变成 0，所以当且仅当和游戏的 sg 为 0 时，先手必输，因为后手总可以控制 sg 值回到 0。

例题：HDU-2176