初探Nim游戏与SG函数

博弈问题我也没有怎么好好研究,只是在碰到具体题目的时候简单看了一下。现在学习一下一个博弈游戏的模板,也带有一点投机取巧的意味吧,但是一定还是没有办法解决所有问题的。

Nim游戏

Nim游戏是一个古老而经典的博弈问题。题意大概如下:

有n堆石子,A和B轮流取,每次可以从任意一堆中取走任意多的石子(不能不拿),如果没有石子可以拿则为输,另一方为赢。假设双方都采取最优策略,在当前情况下,先手是赢还是输?

我们可以考虑记忆化深搜或DP。可是如果石子数量一多,这就非常非常难办了。

我们应该像对付POJ1740的时候一样,先从简单的问题开始考虑。

逐步考虑

一堆石子

为了不让对方赢,我们的最优策略当然是直接把所有的石子拿走啊!先手必赢。

二(两)堆石子

首先我们不能直接拿完一堆,否则转换后对方为先手而且只剩一堆,对方必赢。

但是我们有的时候必须拿完一堆,否则就没有办法拿了。这种情况出现在1 1的时候。 假如说我们想赢,怎么把对方逼到1 1?我们只需要每次取完石子之后使两堆石子的数量一样就可以了。对手一定会破坏这个平衡,但是对手足够聪明的话,一定不会取完;而破坏平衡之后我们又能恢复平衡。最终达到1 1状态的一定是对手。

所以在两堆石子的时候,两堆石子一样多就先手必输,两堆石子不一样就后手必输。

多堆石子

这个规律不会很好想的……Nim游戏简单而又伟大之处就在这里。

为了清晰地解释问题,我还是得拿一组数据来讲话。

19 26 7 14

我们不能简单地考虑成两两组成一个两堆石子的游戏,因为假如轮到你的时候全部不一样,你只能维持一个两堆你是必赢的状态,其他的堆你是没有办法干涉的,这就给对手了机会。

考虑将石子的数量转化为二进制,倒着写(左边是低位):

11001
01011
111
0111

竖着看齐了!一位一位对上!

拿最小的一位说话吧。有两个1,两个0.这就是两堆石子的1 1情况啊!在第一位上,我们必输。

接着就可以发现,在所有的位上,先手必输。

如果综合起来考虑呢?先手还是必输吗?

譬如说,我们从19的堆里拿了5个,那么前面的状态就变成了这样:

0111
01011
111
0111

这个时候后手就有能力把每一位上的游戏再次转换回1 1的情况,强行把26那一堆变成111:

0111
111
111
0111

如此这般下去,先手必输啊。

为什么这一定做得到恢复1 1状态?这只是改变了每一位上1个数的奇偶性而已。

结论

等等,奇偶性?这看起来十分像异或的概念啊!我们想要知道一个状态先手的输赢状态,只需要强行将所有数异或起来,假如结果是0,说明每一位上都是1 1状态,先手必输;否则先手有条件转化为异或结果为0的状态,先手必赢。

更形式化的证明如下:

  1. 无法进行任何移动的局面是必败态;最终局面只有一个,就是全0,异或仍然是0。
  2. 可以移动到必败态的局面是非必败态;对于某个局面(a1,a2,...,an)(a_ 1,a_ 2,...,a_ n),若$ a_ 1 \oplus a_ 2 \oplus … \oplus a_ n\neq 0\oplus表示异或运算),一定存在某个合法的移动,将a_ i改变后满足a_ 1 \oplus a_ 2 \oplus … \oplus a_ n= 0。不妨设a_ 1 \oplus a_ 2 \oplus … \oplus a_ n= k,则一定存在某个a_ i,使得a_ i\oplus k<a_ i成立。则我们可以将a_ i改变成a_ i \oplus k,此时a_ 1 \oplus a_ 2 \oplus … \oplus a_ n\oplus k= 0$。
  3. 在必败态做的所有操作的结果都是非必败态。对于某个局面(a1,a2,...,an)(a_ 1,a_ 2,...,a_ n),若a1a2...an=0a_ 1 \oplus a_ 2 \oplus ... \oplus a_ n= 0,一定不存在某个合法的移动,将aia_ i改变后满足a1a2...an=0a_ 1 \oplus a_ 2 \oplus ... \oplus a_ n= 0。因为异或运算满足消去率,若改变后所有aa异或的到的值还是0,说明aia_ i根本就没有改变。

ICG中的NP

定义P-position和N-position,其中P代表Previous,N代表Next。直观的说,上一次move的人有必胜策略的局面是P-position,也就是“后手可保证必胜”或者“先手必败”,现在轮到move的人有必胜策略的局面是N-position,也就是“先手可保证必胜”。

更严谨的定义是:

  1. 无法进行任何移动的局面(也就是terminal position)是P-position;
  2. 可以移动到P-position的局面是N-position;
  3. 所有移动都导致N-position的局面是P-position。

其实上面Nim游戏最终证明的就是这三个命题。

与图的联系

我们完全可以建立一个图来普遍地描述这些博弈游戏。

对于某个状态来说,它可以转移到另外一个状态,我们就将这两个状态设为两个点,之间用有向边连接。

解决问题

从终点的必输态开始往回染色,就可以得到每个点的NP属性。

SG函数

Sprague-Grundy函数使用了一个非常精巧的方式解决了一类(ICG)博弈问题。定义一个函数sg[x],x为某一个状态。若sg[x]=0,则状态x为必输态。

mex函数

mex{}的意思是第一个不存在于集合中的自然数。

SG函数转移

SG函数是建立在博弈模型上的,所以具有能够转移状态的性质。我们设A为从状态x能够达到的状态的集合,有sg[x]=mex{yAsg[y]}sg[x]=mex\{y\in A|sg[y]\}。这样定义出来的sg函数有一个性质:对于状态x,可以转移到所有小于sg[x]的sg函数值的状态。这就相当于,我们如果有sg[x]个石子,取了一些石子之后,剩少于sg[x]个石子。

这有什么用?

如果我们不仅仅是一个游戏,而是很多个游戏同时玩,那么就完全等同于最经典的nim游戏了。想要求整个游戏的胜或者负,只需要把每个单独游戏的sg函数值异或起来就行了。

例题:HDU5724

这道题已经不能再模板了。因为只有20的宽,所以可以先预处理出所有的情况的sg函数,并不会怎么超时,用状态压缩储存在数组里面。状压的细节嘛,只要有棋子的就是1,没有的就是0,还用不上bitset,直接上int就好。另外做的一个小优化是把第20列看作第0位,这样思考起来比较简单。

但是HDU和Openjudge今天同时出了问题,不知道应该怎么提交,先写出来再说:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1<<20;
int sg[N];
bool exist[100];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    sg[0]=0;
    int last,t,n,pos,num,cur,ans;
    for(int i=1;i<N;i++){
        last=-1;
        memset(exist,0,sizeof(exist));
        for(int j=0;j<20;j++){
            if((i>>j)&1){
                if(last!=-1){
                    exist[sg[i^(1<<j)|(1<<last)]]=true;
                }
            }else{
                last=j;
            }
        }
        for(sg[i]=0;exist[sg[i]];sg[i]++);
    }
    for(cin>>t;t--;){
        ans=0;
        for(cin>>n;n--;){
            cur=0;
            for(cin>>num;num--;){
                cin>>pos;
                cur|=1<<(20-pos);
            }
            ans^=sg[cur];
        }
        if(ans){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
}
avatar
Kerry Su