博弈论之Nim游戏

时间:2023-02-09 16:01:17

Nim游戏是组合游戏(Combinatorial Games)的一种,属于“Impartial Combinatorial Games”(以下简称ICG)。

通常的Nim游戏的定义是这样的:有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人时所有的石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。

        我们都知道,对于N堆石子,判断第一个人是否赢是将每个石子进行异或运算,如果结果为0则第一个人取得必输,否则必赢。

        但主要是为什么用异或?为什么等于零则是先者必输?

        首先先说一下大家都知道的定义吧:P-position和N-position。

        P-position:P即Previous,该局面为P-position,则代表着这个局面先行者必输,后行者必赢。

        N-position:N即Next,该局面为N-position,则代表着这个局面的后行者必输,先行者必赢。

很显然,对于无法移动的局面(Terminal position)为P-position;可以移动到P-position局面的必为N-position局面(就是这个局面是先行者必输的话,它的上一个局面一定是后行者必输);所有移动都导致N-position局面的是P-position。

        也就是说,对于一个局面A是 P-position还是N-position,如果它的子局面(所谓子局面就是这个局面的能够发展成的后续局面,比如两个石子堆个数为(3,3),那么它的子局面为(0,3)(1,3)(2,3))存在先者必输P-position的局面,那么局面A就是后者必输N-position的局面,如果它的子局面全部是后者必输N-position的局面,那么局面A就是先者必输P-position的局面(子局面的后者就是局面A的操作者)。

为此我们要判断的就是一开始是属于什么局面,根据上述定义可知这个局面的判定取决于它的子局面,而它的子局面又取决于它的子子局面……直到这个局面能够独立判断是P-position还是N-position,然后再回溯判断,对于这个递归的算法你可能已经敏锐地看到有大量重复的子问题了,需要记忆化搜索或DP,这实际上也就是博弈论的本质而已,只是我们存在一种比搜索更优的方法——异或。

为什么用异或呢?因为异或有一种我们需要的神奇的性质——消去律。

1.对于Terminal position只有一个,也就是全为0,结果也为0,故先行者必输。

2.某个局面(a1,a2,...,an),若a1^a2^......^an=k(k不等于0),则必有一种局面ai能够通过合法的步骤转换为ai',使结果变为0(k二进制中的某一位中的1必定是某个ai贡献过来的),其中ai^k=ai'<ai(ai在k的二进制下最高位是1),所以是后行者必输。

3.某个局面(a1,a2,...,an),若a1^a2^......^an=0,若ai能够通过合法的步骤转换成另一个局面ai'使结果也为0,那么a1^a2^..^ai^...^an=a1^a2^..^ai'^...^an,根据消去律,得到ai=ai',这是不合法的移动(因为还是它本身),所以是先行者必输。

而这样,我们就可以在O(n)内知道应该是先行还是后行了。

关于SG函数,我们先定义一种作用在集合的运算mex,定义结果为该集合中未出现的最小非负整数,如mex{0,1,2,4}=3、 mex{2,3,5}=0、mex{}=0。

对于一个给定的有向无环图,定义关于图的每个顶点的Sprague-Garundy函数g如下:g(x)=mex{ g(y) | y是x的后继(就是子局面) }。

实际上,所以Nim游戏都可以抽象成一个模型:一个有向图中,一个棋子代表着当前局面,每个顶点代表着每个局面,而每位选手则负责移动棋子,直到某个选手无法移动棋子则为负。

所以对于SG函数的性质,跟上面所讲的1,2,3是一样的:

1.对于Terminal position对应的顶点,就是没有出边,其g(x)=0;

2.若该点ai的g(ai)不为0,则它的后继里存在一个顶点ai'它的g(ai')=0;

3.若该点ai的g(ai)=0;则它的后继里没有一个顶点ai'它的g(ai')=0。

事实上,如果有多堆石子,我们可以把每堆石子都抽象成一个棋子在图中移动,那么我们所要做的就是讲每个棋子所在顶点的SG值算出来,异或一下即可。

稍微变一下,有n堆石子,每次可以从第1堆石子里取1颗、2颗或3颗,可以从第2堆石子里取奇数颗,可以从第3堆及以后石子里取任意颗, 我们可以把它看作3个子游戏,第1个子游戏只有一堆x颗石子,每次可以取1、2、3颗,很容易看出x颗石子的局面的SG值是x%4(数学归纳法可以证明)。第2个子游戏也是只有一堆 石子,每次可以取奇数颗,经过简单的画图可以知道这个游戏有x颗石子时的SG值是x%2。第3个游戏有n-2堆石子,就是一个Nim游戏。对于原游戏的每 个局面,把三个子游戏的SG值异或一下就得到了整个游戏的SG值,然后就可以根据这个SG值判断是否有必胜策略以及做出决策了。

g(x)=b,说明当前局面可以移动到g(a)=b-1,b-2,b-3.......1,0上。

所以,对于我们来说,我们是将一个复杂的游戏分成许许多多若干个简单的小游戏,再分别求出SG值,再全部异或起来就是原游戏的SG值了。