博弈论基础学习(一)Nim游戏

昨天翻看了一些国内博主写的关于Nim游戏的解析,依旧不是特别理解Nim游戏的内涵,今天翻阅论文的时候发现了一篇哈佛教授很久之前写的论文,如醍醐灌顶,由于文章比较长,就不做翻译,文章的原文地址如下:
http://www.jstor.org/stable/pdf/1967631.pdf
感兴趣的可以看原文,如果没有时间的也可以直接看我的文章,本文将提炼该论文的观点,结合之前所看的文章给出Nim游戏的必胜思路,然后附上两道Nim游戏的例题。

Nim游戏理论部分

首先我们定义一下Nim游戏是什么:

有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人时所有的石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。

下面定义安全组合与不安全组合:
安全组合:先手进行完后留给后手,后手的人无论如何做出改变,都将改变这个状态到一个不安全的状态,而回到先手的人总能将这个情况再次变成一个安全的状态,如此下去,先手的人是必胜的。满足这个性质的组合我们叫做安全组合。
不安全组合:由这个状态无论如何改变都无法变为一个安全的组合,即如果某一次改变之后该玩家得到的是一个不安全组合,那么如果双方是足够聪明的,之后的每次改变,该玩家都不可能再得到一个安全的组合,即他是必败的。满足这个性质的组合我们叫做不安全组合。
下面我们引入一条关于Nim游戏的已知结论,并给出P-position和N-position的定义:
给出若干组二进制数,其二进制位对齐排列,把各列相加,如果各列得到的数字都能被2整除,那么它就是一个安全的组合。以这个情况开局,或者在之后的某一手中,当前是一个安全组合,先手的人无论作出什么改变,都将使这个组合变为一个不安全的组合,而后手的人又总能由不安全的组合拼凑出一个安全的组合,我们称此时先手必败(后手必胜),这个局面称之为P-position,反之,若面临的是一个不安全组合,则其总有办法变为一个安全的组合,到下一个人进行时无论怎么改变都将成为一个不安全组合,此时后手必败(先手必胜),这个局面称之为N-position
用数学公式表达的话,可以知道,假设每一堆所含石子的个数为a1,a2,a3…an,若当前情况满足:
a1^a2^…^an!=0,则属于N-position,此时先手必胜,反之为P-position,后手必胜。
给出一组安全组合为a1,a2,a3=9,5,12,其二进制位对齐后如下:

其第一列相加为2,第二列相加为2,第三列为0,第四列相加为2,则又上面的定义可以知道,它是一个安全组合,此时先手必败。若二人足够聪明,我们可以知道总有一堆先减少为0,则只要处于必胜状态的人保证剩下两堆是相等的,他就是必胜的。(可以从XOR=0来解释两堆的情况)
此时显然有:
a1^a2^a3 = 0成立。
此时归纳Nim游戏的必胜原理:如果二者足够聪明,那么第一个修改当前组合得到安全组合的人最终必将保持每一次修改得到的都是安全组合,而另一个人永远得不到安全组合,则这个人就处在一个必胜态(N-position),另一个人处在一个必败态(P-position)。如果已经明白了这点,那我们判断出一个游戏属于Nim游戏时,便可以定义安全组合与不安全组合,然后推出当前情况究竟是N-position还是P-position。

Nim游戏例题

POJ2234 Matches Game (最基本的Nim游戏模板)

此题目为Nim游戏的原型,即我们可以每次从某一堆中取走任意多的石子(取走个数小于当前堆个数),最终取完的人取得胜利。

下面给出代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int a[30];
int main()
{
int n;
while(cin>>n) {
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]());
int res = 0;
for (int i = 0; i < n; ++i)
res ^= a[i]();
if (res) cout << "Yes" << endl;
else cout << "No" << endl;
}
}

POJ2975 Nim

本题也是基本的Nim游戏,从某一堆中取走m个石子,要我们计算出先手必胜的有几种取法。
我们已经知道得到安全组合的条件为改变后满足a1^a2^a3 = 0,题目若给出的初始状态为不安全组合,那我们必可以修改某一堆使之满足这个条件,否则输出为0。
所以我们现在可以知道我们取得必胜的条件为(ak-m)^(XOR^ak)=0
XOR^ak=0代表从XOR中剔除ak这一项,而又它们的异或等于0我们可以将这个式子转化为ak-m = XOR^ak,即m = ak - XOR^ak
而已经知道1\<=m\<=ak,所以只有当ak > XOR^ak的时候才为一个可行解。公式已经得到了,我们便可以轻松地根据式子写出代码。
下面给出代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int a[1010];
int main() {
int n;
while(scanf("%d",&n)){
if(n==0)
break;
int res=0;
for(int i=0;i<n;++i){
scanf("%d",&ai);
res^=ai;
}
int ans=0;
for(int i=0;i<n;++i){
if(ai>(res^ai))
ans++;
}
cout<<ans<<endl;
}
return 0;
}

总结

Nim游戏虽然道理简单,但却是博弈论的一个绝佳的入门点,如果我们仅仅记住结论,那么只要题目发生了变化,我们就会觉得无从下手,只有对Nim游戏有真正深入的了解,我们接下来的学习才能得心应手,这也是我翻阅论文后写下这篇Blog 的目的,之后还会继续更新几篇关于ACM中博弈论应用的文章,水平有限,希望各位看客能够多多指正。