博弈论入坑导论

如果你对博弈论感兴趣,并且对自己的英文水平有很自信,并且有大把大把时间,可以读一读”GAME THEORY”–Tomas S.Ferguson
经过我40分钟的阅读,我认为该教材写的十分详细,但是由于内容较多并不适合作为竞赛学习的资料,不过大家按自己的实际情况随便读一读未尝不好。
教材下载:GAME THEORY–Thomas S.Ferguson

1.定义

这篇文章所讨论的游戏有如下几个性质。

  • 1.游戏有两个玩家
  • 2.游戏总状态数一般有限,且有唯一的初始状态
  • 3.对每个状态,两种玩家可行的决策完全相同
  • 4.两个玩家交替执行决策
  • 5.无论游戏怎样进行,总步数有限
  • 6.游戏最终达到一种状态(终态),两玩家均不能继续操作,这时分出胜负(一般为不能操作者输)

这也是我们所说的“组合游戏”。

所谓状态,就是一个游戏局面。比如跳棋中每个棋子的位置决定了一个游戏局面,如果两个局面不同,那这两个局面就对应这不同的状态。

根据性质4,我们可以知道组合游戏的状态一定不存在环,所以我们可以认为所有可达到的游戏状态构成一个DAG。

我们对这个DAG上的每一个状态给出如下定义:

  • 如果这个状态下的先手可以保证自己绝对不会输,这个状态叫必胜态,简称P (previous)
  • 如果这个状态下的后手可以保证自己绝对不会输,这个状态叫必败态,简称N (next)

接着,我们根据这两个定义继续给出必胜态和必败态的判定方法:

  • 终态为给定的必胜/必败态
  • 可以转移到必败态的状态是必胜态
  • 只能转移到必胜态的状态是必败态

2.游戏之母:Nim Game

为什么

为什么叫Nim游戏为游戏之母呢?因为所有组合游戏都可以相互规约,而我们不妨将所有组合游戏都规约为最简单的Nim游戏。

只要知道了Nim游戏必胜的判定方法,我们就能通过这种规约得到所有组合游戏的必胜判定方法。当然,为了简单,我们这里谈到的组合游戏都是“第一个不能操作的人输”的游戏。要注意:如果这个定义改成“第一个不能操作的人赢”,先手和后手的获胜并不是简单的交换一下,因为必胜态的定义不是对称的。

规则

  • 初始有n堆石头,每堆$x_i$个石头
  • 两人轮流取石子,第一个不能取的人输
  • 每个人只能在一堆中取至少一个石子,可以将整堆取完

判定

令$S=X_1\oplus X_2 \oplus X_3\cdots\oplus X_n$

其中$X_i$为第i堆的石头数的二进制表示。

若S为0,则先手必败,反之先手必胜。对于任何一个状态该定理都成立。

证明

下面给出一种比较容易理解的证明。

当前S为零,如果后手可以采取一种策略,无论先手如何操作,S始终为0,则后手一定可以达到所有石子为0的状态,这时后手胜利了。因为无论先手怎么操作,先手只能把S=0变成非零的数,而非零的数意味着场上还有石子,因此先手不可能胜利。

下面我们就证明,当S一开始为0的时候,后手的确存在一种策略,将S保持为0。证明了这个,我们还可以知道,当S一开始不为0的时候,先手可以把非零变成0,这样先手就占据了主动,最终赢得游戏。

如果先手将S变成了非0的数,假设此时$S=\overline{1X}$,那么至少有一堆石子个数的最高位和这个数一样,为1。假设这堆石子有Y个。那么我们就在这一堆中取石子,使得这一堆的最高位变成0,同时剩余位与其他堆的异或为0。这是一定可以做到的。因为最高位变成0后

即一定存在$Z\leq Y$使得$S\oplus Y\oplus Z=0$,即把Y用Z替换之后,S转而变成了0。

证明完毕。

3.SG函数

移石子游戏1.0

现在考虑一个看似比较好玩的游戏:移石子游戏。

  • 给出一个DAG,DAG中某个点上有一个石子
  • 两玩家交替沿DAG的有向边移动石子
  • 最先不能移动石子的玩家失败

这个游戏有着十分强的代表性。

首先,这个DAG上的节点可以看成任何一种组合游戏的所有状态,而所有状态之间又存在单向转移。而石子可以看成当前状态。这样,所有组合游戏都可以抽象为移石子游戏。下面,我们将把移石子游戏抽象为Nim游戏。

mex函数 & SG函数

为了解决上面这个问题,我们首先定义这样一个函数,这个函数相当于是移石子游戏(也就是所有组合游戏)和Nim游戏之间最直接的桥梁。

  • 定义$mex(S)$为集合S中第一个没有出现的自然数(包含0)
  • 定义$SG(X)=\mathop{mex}\limits_{X->Y}(SG(Y))$,其中所有终态由于没有后续状态,所以SG值为0

于是,有定理称:一个组合游戏后手必胜当且仅当SG(X)=0.

具体原因可以大致这样理解:mex函数的功能类似于Nim游戏对某一堆去石子的逆操作。即:一堆石子可以变少为任意一个小于它本身的数,不能变多或不变。而类似的,SG函数也表明一个状态可以转移到任意一个SG值小于它的状态。因此SG函数的值就是抽象的石子数。

所以,我们只要按移石子游戏中的拓扑序求每个状态的SG函数值即可明确每个状态的胜负情况。

移石子游戏2.0

若有多个DAG,每个DAG上有一个石子,游戏状态数的规模将会变得非常大,是每个DAG点数的乘积。但是类似于Nim游戏,我们只需要将每个石子在所在DAG上的SG函数值异或起来,将是整个”移石子游戏2.0“的SG值。

4.整理

现在我们知道了如何快速(当然也不是很快)求一个组合游戏的任意一个状态的胜负情况。

  • 对于一个大型组合游戏,由多个独立的子游戏组成,那么其SG值为子游戏SG值的异或
  • 对于一个独立的游戏的一个状态X,$SG(X)=\mathop{mex}\limits_{X->Y}(SG(Y))$
  • 若一个状态$SG(X)=0$则后手必胜
  • 若一个状态$SG(X)\neq 0$则先手必胜

5.实践导论

世界上有许许多多的组合游戏。组合游戏,如果是非常有吸引力的游戏,一般状态数都很多,比如大到$10^9$这个级别以上的比比皆是。如果每个组合游戏我们都只采用上文提到的做法,未免解决起来有点吃力了。

所以,现在的主要矛盾是:如何寻找到一个高效的直接判断胜负或通过求SG函数判断胜负的方法?

答案是:暂时不存在一个普适的方法。

但是并不意味着每个游戏我们都需要列出所有状态进行Dp,而是可以采用一些非常高级的方法去求解,那就是打表。除了这个,还有一些针对特殊游戏的特殊方法(主要学习自”https://blog.csdn.net/kyleyoung_ymj/article/details/51494139″):

  • Bash Game
    • 没人最多一次取m个石子,其他规则同Nim
    • SG(X)=X mod (m+1)
  • Nim~K~ Game
    • 每个人最多从最多K堆石子中取出任意多个,其他规则同Nim
    • 在二进制下将石子数每一位的1的个数累加,当每一位的1的个数均为(K+1)的倍数时后手必胜,反之
  • X~K~ Game
    • 每个人最多在最多K个子游戏中操作
    • 同Nim~K~游戏,在二进制下累加每个游戏SG函数值中每位1的个数,当每一位的1的个数均为(K+1)的倍数时后手必胜,反之。可以看成是在$K+1$这个周期下的异或
  • Misère Nim
    • 不能取的一方获胜,其他规则同Nim
    • 当SG不为0且至少有一堆石子数大于1,先手必胜
    • SG为0且不存在石子数大于1的堆,先手必胜
    • 反之后手必胜
  • Staircase Nim
    • 每个人可以从某一堆取走若干个石子,放到前一堆中,第一队取出的石子消失,其他规则同Nim
    • 当且仅当奇数编号的石子异或为0时后手必胜
  • Wythoff Game
    • 两堆石子,双方轮流从某一堆取走若干石子或从两堆取走相同数目的石子,不能取者输
    • 另一个题面是:双方在棋盘上轮流向左或下或左下移动一个皇后,不能移动者输
    • 利用棋盘我们可以发现,只有少数点后手必胜,这些点满足坐标:$(\lfloor n\cdot \frac{\sqrt{5}+1}{2}\rfloor,\lfloor n\cdot \frac{\sqrt{5}+3}{2}\rfloor)$
    • 每个点的横坐标对应第一堆石子,纵坐标对应第二堆石子,就是Wythoff Game
分类: 所有

2 条评论

XZYQvQ · 2018年6月3日 10:05 下午

WTF我才发现你已经发了一篇博弈论的文章了QvQ
另外为什么会是【教程】。。。
我已经改成了【算法】了。。。

    boshi · 2018年6月10日 11:38 上午

    好的

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *