博弈之 Nim 游戏&poj 3537 Crosses and Crosses

参考链接: [ 博弈之 Nim 游戏和 sg 函数 ](https://software.intel.com/zh-cn/blogs/2014/03/06
/nim-sg)
题目链接: poj 3537 Crosses and Crosses

Nim游戏的定义

Nim游戏是组合游戏(Combinatorial Games)的一种,准确来说,属于“Impartial Combinatorial Games”(以下简称ICG)。满足以下条件的游戏是ICG(可能不太严谨):
  1. 有两名选手;
  1. 两名选手交替对游戏进行移动(move),每次一步,选手可以在(一般而言)有限的合法移动集合中任选一种进行移动;
  1. 对于游戏的任何一种可能的局面,合法的移动集合只取决于这个局面本身,不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素;
  1. 如果轮到某名选手移动,且这个局面的合法的移动集合为空(也就是说此时无法进行移动),则这名选手负。

必败必胜策略的定义

定义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。按照这个定义,如果局面不可能重现,或者说positions的集合可以进行拓扑排序,那么每个position或者是P-
position或者是N-position,而且可以通过定义计算出来。

例子

poj3537就是Nim游戏的一种:
有个2人玩的游戏在一个规模为1*n的棋盘上进行,每次一个人选择一个地方画上’X’,一旦某个人画上X后出现了连续3个X,那么这个人就赢了。给你n(3≤n≤=2000)问先手和后手谁会赢。

仔细思考一下我们发现,xxx的上一步只能是oxx,xox,xxo的其中一种,也就是说如果谁走出一步形成上述局面那么谁就必败。
再进一步说,如果你在第i个格子画x,那么i-1,i-2,i+1,i+2,都不可以画x,因为那样会必败。
这样题目就可以转化为,轮流画x,谁没有格子画x谁就输。
以上例来进行一下计算,假设N为3,也就是OOOO,当前局面有4个子局面,XOOO,OXOO,OOXO,OOOX。
1. XOOO对于当前玩家只有一步可走,就是XOOX(别忘了上面说过每走一步,该位置左右共4个位置都不能),所以XOOO就是一个N-position局面(
后手输)。
2. OXOO对于当前玩家无步可走,所以是一个P-position(先手输)。
3. 4. OOXO,OOOX就不再赘述,前者P,后者N。
** 那么OOOO显然是一个N-position,因为他的子局面中有P-position(他当然会把这种局面留给自己的对手)。 **

根据上面这个过程,可以得到一个递归的算法——对于当前的局面,递归计算它的所有子局面的性质,如果存在某个子局面是P-
position,那么向这个子局面的移动就是必胜策略。当然,会存在大量的重叠子问题,可以用DP或者记忆化搜索的方法以提高效率。
但问题是,利用这个算法,对于某个Nim游戏的局面(a1,a2,…,an)来说,要想判断它的性质以及找出必胜策略,需要计算O(a1a2…*an)个局面的性
质,不管怎样记忆化都无法降低这个时间复杂度。所以我们需要更高效的判断Nim游戏的局面的性质的方法,也就是Bouton’s
Theorem,上面的参考链接里有这个的详细解释与证明,就不贴了。

** 总之,通过Bouton’s Theorem,可以得到,如果a的子局面a1^a2^..^an == 0,a就是一个N-position,否则a是P-position。 **
** 这也解清了我对好多人用异或的一个疑惑。 **

代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

const int N = 2009;
int sg[N];

int getsg(int n)
{
    if(n<=0)
        return 0;
    if(sg[n] != -1)
        return sg[n];
    bool f[N] = {};//对当前局面的子局面进行标记
    for(int i=1; i<=n; i++)
        f[getsg(i-3)^getsg(n-i-2)] = 1;//标记所有的子局面
    for(int i=0; ; i++)//如果子局面没有0,则说明当前局面为P-position。
        if(!f[i])
            return sg[n] = i;
}

int main()
{
    int n;
    while(cin>>n)
    {
        memset(sg, -1, sizeof(sg));
        if(getsg(n))
            cout<<"1"<<endl;
        else
            cout<<"2"<<endl;
    }
    return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!