博弈论

并不是NOIp常考的内容,不过还是稍微学了下.

基本概念

我们定义几个概念

N状态(next position)表示一个状态先手必胜
P状态(previous position)表示一个状态先手必败

根据博弈规则,我们容易发现几个规律

一个状态不是P就是N
游戏结束时的状态为P
N状态有一个后继状态为P,这样先手只要转移到这个状态就能使对手必败
P状态所有后继状态都是N,先手无论如何转移对手都必胜

接着我们定义一个特殊的函数SG函数

这个函数是一个从游戏状态集到非负整数集的映射

它的定义利用一个特殊运算$mex$.$mex(s)$表示不属于非负整数集s的最小非负整数

例如$mex({0,1,2,3})=4$,$mex({0,1,3,4})=2$

$SG$函数通过递归定义:

若状态$x$是P状态,$SG(x)=0$
若状态$x$是N状态,设$x$的所有后继状态为$y_1,y_2,y_3\dots y_n$,则$SG(x)=mex({SG(y_1),SG(y_2),SG(y_3)\dots SG(y_n)})$

那么,$SG$函数的意义何在?

Nim游戏

Nim游戏是指这样一个游戏

给一个有$n$颗石子的石堆,两人轮流取若干颗石子,最后取完所有石子的人获胜

这是一个极简单的一维Nim游戏

很明显,$n=0$时先手必败,否则先手必胜

接下来我们从上述几个概念的角度理解这个游戏.

状态:一维Nim游戏的状态可以用一个非负整数表示,即石子数量
N和P:设状态为$x$,则$x=0$时为P状态,否则就是N状态
SG:设状态$y$是当前状态$x$的后继状态,显然$y$可以是任何小于$x$的非负整数.根据$SG$函数的定义,我们发现$SG(x)=x$

因此,笔者认为$SG$函数缘于Nim游戏

如何计算复杂状态的$SG$值呢?

$SG$函数的运算

给若$n$个有$A_i$颗石子的石堆,两人轮流取若干颗石子,最后取完所有石子的人获胜

这是一个多维的Nim游戏

状态:游戏状态可以用一个非负整数集$s={x_1,x_2\dots x_n}$来表示.
N和P:$s={0,0\dots 0}$是一个P状态

其它状态的$SG$怎么求呢?

接下来定义Nim游戏中$SG$函数的运算规则:

Bouton’s Theorem

首先我们给出结论:

对于一个状态$s$,$SG(s)=x_1\ xor\ x_2\ xor… xor\ x_n$

接下来我们归纳证明这个结论的正确性:

根据游戏规则,设状态$s_1={x_1,x_2,\dots ,x_n}$有一个后继状态$s_2={x_1-m,x_2,\dots x_n}$

$SG(s_2)$

$=(x_1-m)xor\ x_2\ xor\dots xor\ x_n$

$=(x_1-m)xor\ x_2\ xor\dots xor\ x_n\ xor\ x_1\ xor\ x_1$

$=(x_1-m)xor\ SG(s_1)xor\ x_1$

1.$SG(s_1)=0,s_1$是P状态

因为$(x_1-m)\neq x_1$,所以$SG(s_2)\neq SG(s_1)\neq 0$,$s_2$是N状态

同理得$s_1$的其它所有后继状态都是N状态.满足博弈规则

2.$SG(s_1)\neq 0,s_1$ 是N状态

根据博弈规则,$s_1$一定有个后继状态$SG(s_i)=0$,也就是一定存在$x_j$满足:

$SG(s_i)=(x_j-m)xor\ SG(s_1)xor\ x_j=0$

即:

$x_j-m=SG(s_1)xor\ x_j$

因为一定存在$x_j$,其二进制最高位和$SG(s_1)$的二进制最高位相同(否则无法得到$SG(s_1)$最高位上的$1$)

所以$SG(s_1)xor\ x_j$的这个位置上一定为$0$,则一定$x_j>SG(s_1)xor\ x_j$,因此一定存在$m$满足上式

由此我们简单证明了Bouton's Theorem:在Nim游戏中,$SG(s)=x_1\ xor\ x_2\ xor… xor\ x_n$

推广至一般博弈游戏

$SG$函数就是一维Nim游戏

根据$SG$函数的定义$SG(x)=mex({SG(y_1),SG(y_2),\dots ,SG(y_n)})$,我们得到$SG$函数的性质:

若$SG(y)<SG(x)$,那么状态$x$一定可以转移到状态$y$

这和一维Nim游戏完全相同

如果对于更复杂的游戏,我们计算出每个状态的$SG$值,那么我们就把这个游戏变成了一个一维Nim

而N/P状态规律就是:$SG(x)=0$时状态$x$为P,否则状态为N

那么对于复杂游戏,$SG$函数又有什么运算规则呢?

Sprague-Grundy Therem

若复杂状态$s$可以看作若干个互不干涉的简单状态$x_1,x_2\dots x_n$的合成,那么:

$SG(s)=SG(x_1)xorSG(x_2)xor\dots xorSG(x_n)$

这实际上是对Bouton's Theorem的推广

对于Nim游戏:$SG(s)=x_1\ xor\ x_2\ xor… xor\ x_n$
对于一维Nim游戏:$SG(x)=x$

类比Bouton's Theorem,我们可以用同样的方式证明Sprague-Grundy Therem

综上所述

求解博弈论问题的一般步骤是

将复杂的博弈问题分解成一个个独立的简单博弈问题
通过定义递归求得简单状态的$SG$函数
通过Sprague-Grundy Therem将其合并成复杂状态的$SG$函数

$SG$函数源于Nim又高于Nim,它是利用Nim游戏的性质构造出来的函数,目的是把一般博弈问题都当成Nim求解

文结.

文章参考Estimator的博客

银河美术馆-Beautyyu

博弈论,SG函数和Nim游戏|笔记

博弈论