博弈论专题——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;
}

《博弈论专题——Nim游戏》上有1条评论

发表评论

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