博弈论专题——Nim游戏

Nim游戏是一个非常经典的博弈游戏。

具体是这样的，给你若干堆石子，每次可以从一堆石子里取走任意数量的石子，但不能同时从多堆石子中取，不能操作的人就输掉了游戏。

举个栗子吧，假如有三堆石子 (1,3,2)，在你先手的情况下，可以证明你必败无疑。（证明稍后会讲到，下面先举例说明）

你可以取完第一堆石子，局面变成了 (0.3,2)，这时对手只要将局面变成 (0,2,2)，他就能将自己置于不败之地了，因为你在一堆石子里执行什么操作，他就能在另外一堆石子中执行同样的操作。

那么，取走第二堆呢？你可以给对手留下 (1,2,2),(1,1,2),(1,0,2) 这样三种局面，然而结局和上面相同。

取走第三堆也一样，留下的是 (1,3,1),(1,3,0) 的局面，稍稍思考便会发现，结局还是一样。

于是，我们便分析完了 (1,3,2) 这个局面，作为先手的你，并不能取得胜利，我们将这个状态称之为先手必败的状态。

先手必败的状态有一个非常明显的特点，就是它后继的状态都是先手必胜的，而先手必胜的状态，后面至少有一个先手必败的状态。（这个其实并不算太难理解）

那么，这个游戏有什么规律吗？当然是有的。

设每堆石子的数量为 \(a_i\)，当 \(a_1 \oplus a_2 \oplus … \oplus a_n=0\) 时（\( \oplus\) 就是 xor），先手必败，否则先手必胜。

证明在下面：

Nim 的一个典型的先手必败局面是 (0,0,0)，\(0 \oplus 0 \oplus 0=0\)。根据刚才所讲到的，这个先手必败局面一定有一个前驱的先手必胜局面。

设这个必胜局面下石子数量的 xor 和为 \(k\)，我们可以找到它二进制值为1的最高位，设为 \(i\)，我们可以找到一堆石子 \(a_j\)，使得这堆石子的二进制值的第 \(i\) 位为1，然后，我们将这堆石子变成 \(a_j \oplus k\)，使得 xor 和为 0。

但当 xor 和为 0 时，无论怎么操作，都会使得接下来的 xor 和不为 0。

就这样，我们可以在博弈中给对手留下 xor 和为 0 的状态，我们也就可以取得胜利。

对于 (1,2,4) 这样一个局面，因为 \(1 \oplus 2 \oplus 4 != 0\)，所以先手必胜。而我们应该给对手留下一个先手必败的局面，显然，将局面变成 (1,2,3) 即可。

———-题目分割线———-

洛谷 2197 Nim游戏/poj 2234 Matches Game

这就是一道Nim的模板题。

#include <stdio.h>
int m,n;
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int n;
  scanf("%d",&n);
  int flag=0;
  for(int i=1;i<=n;i++)
  {
   scanf("%d",&m);
   flag^=m;
  }
  if(!flag)puts("No");
  else puts("Yes");
 }
 return 0;
}

poj 2975 Nim

计算Nim游戏的胜利走法有多少种。

其实利用上面的结论即可。

#include <stdio.h>
int num[1005];
int main()
{
 int n;
 while((~scanf("%d",&n))&&n)
 {
  int ans=0,sum=0;
  for(int i=1;i<=n;i++)
  {
   scanf("%d",&num[i]);
   sum^=num[i];
  }
  for(int i=1;i<=n;i++)
   if((sum^num[i])<num[i])ans++;
  printf("%d\n",ans);
 }
 return 0;
}