Nim博弈变式(一)阶梯博弈

众所周知,Nim博弈存在着多种变形,但是万变不离其宗,这里分析的是变形之一的阶梯博弈,研究怎么用Nim博弈的思想去解决这一类问题。

什么是阶梯博弈?

阶梯博弈(Staircase Nim)描述的是类似如下的一种问题:
一个阶梯有n阶,每一阶上面都可以存放个数不限的硬币。现在我们用n元组(x1,x2,…,xn) 来代表第 i (1 ≤ i ≤ n)个硬币存放在第xi个阶梯上面。阶梯博弈中的一次移动可以把任意正整数个的硬币从某一阶移动到下面的一阶,也即是从第 j 阶移动到第j - 1阶。当硬币到达地面(第0阶)时,这个硬币就不可再移动了。双方轮流落子,直到有一方不能再落子。
下面直接给出一个结论:
N元组(x1,x2,…,xn) 代表一个P-position 当且仅当它奇数步数位置上面的Nim数之和(异或)等于0。

为什么能够把阶梯博弈转化为Nim博弈处理?

我们试着回想之前介绍的Nim博弈的内容,双方轮流进行,每次进行处于P-position的一方进行任意减石子的操作都将把这个情况转化为一个N-position。
我们再看看阶梯博弈,能不能存在一种策略,使它与Nim博弈成为同一类型的博弈呢?答案是肯定的。
假定我们此时把奇数堆看做Nim游戏的石堆,此时你是N-position,根据Nim博弈的必胜策略,你可以通过一次操作使奇数堆的硬币数目变为一个安全的组合,此时你处于必胜态。那么接下来我们就知道怎么应对对方的决策了:
(1)如果对方选择在奇数堆中移动n个硬币到一个偶数堆,那么就相当于Nim博弈中把n个石子从某个堆中移走,那么此时你就可以继续根据Nim博弈的必胜决策使奇数堆中的硬币维持在一个必胜态。
(2)如果对方选择从偶数堆中移动了n个硬币到一个奇数堆,那么我们此时可以把这n个硬币再次移动到一个偶数堆,相当于次数奇数堆的硬币数目没有发生任何改变,只是把硬币从上一个偶数堆移动到了下一个偶数堆,你依然处在一个必胜态。
游戏进行到后面,只剩下奇数堆的石子,就是一个纯粹的Nim博弈了,我们只要根据必胜决策进行,最后肯定是把最后一堆移动到终点(Terminal-position)的,所以整个游戏其实就是一个抽象的Nim博弈。

几道阶梯博弈习题

POJ1704 Georgia and Bob

这是一道典型的阶梯博弈,题意是Georgia和Bob轮流进行博弈,初始状态下给定的n个位置上面都含有一个石子,我们可以对任意一个石子移动k个位置,但是这个石子不能超过前面的石子,不能在进行任何移动的人输掉比赛。
显然我们可以根据前面介绍过的思想把这个游戏化为纯粹的Nim博弈。
我们可以把石子两两绑定,那么每一对就可以看成一个Nim石堆,注意,如果此时的石子数目是奇数的话,第一个石子就需要和边界进行绑定。
这样处理之后,只要我们把初始状态进行Nim数的求和就可以判断它处于什么状态进而知道谁是必胜的了。
这里还有一个问题要注意,为什么两两绑定而不考虑石子之间的间隙呢?这是因为如果对手移动了前一个石子到前面,那么我们总是可以移动与之匹配的另一个石子到前面,这样做就相当于Nim堆的数目是不变的,我们总是可以维持自己的必胜态。

给出代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
using namespace std;
int pos[1010];
int main() {
int q;
cin>>q;
while(q--){
int n;
scanf("%d",&n);
pos[0]=0;
for(int i=1;i<=n;++i) {
scanf("%d", &pos[i]);
}
sort(pos,pos+n+1);
int ans=0;
for(int i=n;i>0;i-=2)
ans^=(pos[i]-pos[i-1]-1);
if(!ans) puts("Bob will win");
else puts("Georgia will win");
}
return 0;
}

HDU4315 Climbing the Hill

这题比上一题多了一个King要处理,首先把King移动到终点的人获胜,但其实仔细分析会发现本质上和上一题是一样的,我们只要把King看成是普通人即可,但是在决策中多了几个限制,需要我们加以特判,因为他们破坏了Nim游戏的结构:
(1)如果k=1,那么只要Alice直接把他移动到终点就可以了。
(2)如果k=2,那么显然谁也不愿意把第一个棋子移动到终点,因为这样一来第二个人就可以直接把king移动到终点直接赢得比赛。既然不能处理,那么我们就只能把第一堆无视处理,无视的方法是第一堆的大小减去1,代表可以移动的位置减少了1(不能把第一个移动到终点),我们可以知道这样根本不影响Nim博弈的结果,此时的胜负决定于后面余下堆的Nim博弈。

给出代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
int pos[1010];
using namespace std;
int main() {
int n,k;
while(~scanf("%d%d",&n,&k)){
for(int i=0;i<n;++i){
scanf("%d",&pos[i]);
}
sort(pos,pos+n);
int ans=0;
if(n&1) ans = pos[0] -(k==2);
for(int i=(n&1);i<n-1;i+=2){
ans^=(pos[i+1]-pos[i]-1);
}
if(ans || k==1) puts("Alice");
else puts("Bob");
}
return 0;
}

HDU3389 Game

这题就是一个裸的阶梯博弈啊,只是移动范围减少了,有些地方不能走,如果你接触过离散化的思想你就会知道这并没有什么影响,首先老规矩分析一下Terminal-position究竟有哪些,显然的我们可以找出1、3、4这几个位置是不能再进行任何移动了,接下来打表,找出哪些点对应一个奇数的步数,哪一些点对应一个偶数的步数,可以发现的是对6取模余0、2、5的位置对应的都是一个奇数的步数,其他位置都是一个偶数的步数,值得一提的是,无论你是一步到位,还是经过偶步数再经过奇步数到某一个位置,都不会影响该个位置的奇偶性(这不是废话嘛!不然我打表观察做什么)

给出代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
int table[101];
int main() {
/*
int mark=3;
int count=3;
for(int i=3;i<=10010;++i){
if((mark+i)%3==0 && (mark+i)%2==1) {
table[i] = count%2;
++count;
mark = i;
}a
else
table[i]=2;
}
for(int i=1;i<=101;++i){
cout<<"CASE "<<i<<":"<<table[i]<<endl;
}
return 0;
*/
int q;
int qnum=1;
cin>>q;
while(q--){
int num;
scanf("%d",&num);
int ans=0;
int temp;
for(int i=1;i<=num;++i){
scanf("%d",&temp);
if(i%6==0 || i%6==2 || i%6==5)
ans^=temp;
}
if(ans) printf("Case %d: %s\n",qnum,"Alice");
else printf("Case %d: %s\n",qnum,"Bob");
qnum++;
}
return 0;
}

总结

还是那句话吧,永远不要以为自己懂的足够多,特别在ACM赛场上,题目千变万化,就一个Nim博弈的变形就有很多种,不要以为自己掌握了一个取石子就天下无敌了,这是我始终在警醒自己的。最近还在看
《GAME THEORY》 By Thomas S.Ferguson,受益良多,每天都有新的收获,我会很乐意继续更新这部分的内容分享给大家,也请大家对我说的不对或者不好的地方进行批评和指正,不胜感激。