【leetcode-292】Nim 游戏——博弈论初步

Nim 游戏

看到这标题，我还是觉得有趣的，因为 Nim 是一门十岁半的语言，满有趣的

但是我看到题目我还是很奇怪的，看上去好像很简单诶，做起来感觉又很奇怪，然后翻了评论，看到了这么一个博弈论的东西

CPP

class Solution {
public:
    bool canWinNim(int n) {
        return n%4>0;
    }
};

C

bool canWinNim(int n){ return n%4>0; }

Lua

function canWinNim (n) return n%4>0 end

巴什博奕

巴什博奕：

两个顶尖聪明的人在玩游戏，有n 个石子，每人可以随便拿1−m 个石子，不能拿的人为败者，问谁会胜利

巴什博奕是博弈论问题中基础的问题

它是最简单的一种情形对应一种状态的博弈

回到顶部
博弈分析
我们从最简单的情景开始分析

当石子有1−m 个时，毫无疑问，先手必胜

当石子有m+1 个时，先手无论拿几个，后手都可以拿干净，先手必败

当石子有m+2−2m 时，先手可以拿走几个，剩下m+1 个，先手必胜

我们不难发现，面临m+1 个石子的人一定失败。

这样的话两个人的最优策略一定是通过拿走石子，使得对方拿石子时还有m+1 个

我们考虑往一般情况推广

设当前的石子数为n=k∗(m+1)+r
先手会首先拿走r 个，接下来假设后手拿走x 个，先手会拿走m+1−x 个，这样博弈下去后手最终一定失败

设当前的石子数为n=k∗(m+1)
假设先手拿x 个，后手一定会拿m+1−x 个，这样下去先手一定失败

1. 巴什博奕 (Bash Game)
   首先我们来玩一个比较古老的报数游戏。A 和 B 一起报数，每个人每次最少报一个，最多报 4 个。轮流报数，看谁先报到 30.
   如果不知道巴什博弈的可能会觉得这个是个有运气成分的问题，但是如果知道的人一定知道怎样一定可以赢。

我们先看下一个一眼就能看出答案的例子 比如说我们报到 5 (4+1), 每次报最多报 4 个，最少报 1 个。那么是不是后者一定可以赢呢？答案是肯定的。好了到这巴什博弈的精髓基本就 OK 了。
那么如果我们要报到 n+1, 每次最多报 n 个，最少报 1 个的话，后者一定能够赢。

现在我们需要报数到 n, 而每次最多报数 m 个，最少报数 1 个。我们可以化成这样
n = k*(1+m)+r (0 <= r <= m）这样的话如果 r 不等于 0 那么先手一定会赢，为什么呢？首先先手报 r 个，那么剩下 k 倍 (1+m) 个数，那么我们每次报数 1+m-k (B) 个数就一定能保证最后剩下 1+m 个，那么就到了上面我们说的那个了，先手就一定会赢，如果 r=0 那么后手一定会赢，道理一样的。
(r 为任意自然数，s≤m), 即 n%(m+1) != 0, 则先取者肯定获胜

代码：

import java.util.Scanner;

/**

• Created by YYL on 2017/2/24.
  */

//先报数到n者胜，每次最少报m1,最大报m2，且1<=m1<m2<n;
public class BashGame {

public static void main(String[] args) {
    Scanner scanner=new Scanner(System.in);
    int n=scanner.nextInt();
    int m1=scanner.nextInt();
    int m2=scanner.nextInt();
    if(m1<1||m2>=n);
    else {
        if(n%(m1+m2)!=0)
            System.out.println("第一个人获胜");
        else
            System.out.println("第二个人获胜");
    }

}

}
运行结果：

30 2 6
第一个人获胜

其他实例：

1. 大学英语四级考试就要来临了， Kiki 和 Cici 在紧张的复习之余喜欢打牌放松。“升级”？“斗地主”？那多俗啊！作为计算机学院的学生，Kiki 和 Cici 打牌的时候可没忘记专业，她们打牌的规则是这样的：
   1、 总共 n 张牌；
   2、 双方轮流抓牌；
   3、 每人每次抓牌的个数只能是 2 的幂次（即：1，2，4，8，16…）
   4、 抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；
   假设 Kiki 和 Cici 都是足够聪明并且每次都是 Kiki 先抓牌，请问谁能赢呢？

Input
输入数据包含多个测试用例，每个测试用例占一行，包含一个整数 n（1<=n<=1000）。

Output
若 Kiki 能赢的话输出 “Kiki”，否则输出 “Cici”，每个实例的输出占一行。

Sample Input
1
3

Sample Output
Kiki
Cici
分析：

如果你是先手，考虑你的必胜态。注意，因为任何正整数都能写成若干个 2 的整数次方幂之和 (相当于十进制转二进制)。由于规定只能取 2 的某个整数次方幂，只要你留给对手的牌数为 3 的倍数时，那么你就必赢，因为留下 3 的倍数时，对手有两种情况：
1：如果轮到对方抓牌时只剩 3 张牌，对方要么取 1 张，要么取 2 张，剩下的你全取走，必赢！
2：如果轮到对方抓牌时还剩 3k 张牌，对手不管取多少，剩下的牌数是 3x+1 或者 3x+2。轮到你时，你又可以构造一个 3 的倍数。 所以无论哪种情况，当你留给对手为 3k 的时候，你是必胜的。
题目说 Kiki 先抓牌，那么当牌数为 3 的倍数时，Kiki 就输了。否则 Kiki 就能利用先手优势将留给对方的牌数变成 3 的倍数，就必胜。

代码如下：

#include <iostream>
using namespace std;
int main () {
    int num;
    while (cin>>num ) {  
        if(num%3!=0) cout<<"Kiki"<<endl;
        else cout<<"Cici"<<endl; 
    }
    return 0; 
}

2. 土地拍卖
   Problem Description
   小鸡同学和鹏程同学始终没有逃过退学的命运，因为他们没有在程序设计竞赛中获奖，还为了争抢莎莎大打出手。现在等待他们的只能回家种田。要种田得有田才行，小鸡听说街上正在举行一场拍卖会，拍卖的物品正好就是一块田地。于是，小鸡带上他的全部积蓄，冲往拍卖会。后来发现，整个拍卖会只有小鸡和他的死对头鹏程。通过打听，小鸡知道这场拍卖的规则是这样的：刚开始底价为 0，两个人轮流开始加价，不过每次加价的幅度要在 1～N 之间，当价格大于或等于田地的成本价 M 时，就把这块田地卖给这次叫价的人。小鸡和鹏程虽然比赛不行，但是对拍卖却十分精通，而且他们两个人都十分想得到这块田地。所以他们每次都是选对自己最有利的方式进行加价。由于抽签决定，所以每次都是由小鸡先开始加价，请问，第一次加价的时候，小鸡要出多少才能保证自己买得到这块地呢？

Input
本题目包含多组测试，请处理到文件结束 (EOF)。每组测试占一行。每组测试包含两个整数 M 和 N (含义见题目描述，0

# include<stdio.h>
int main() {
    int n,m;
    while(scanf("%d %d",&m,&n)!=EOF) {
        if(m%(n+1)==0) {
            printf("none\\n");
            continue;
        } 
        if(m<=n) {
            printf("%d",m);
            for(int i=m+1; i<=n; i++) printf(" %d",i);
            printf("\\n");
            continue;
        } 
        printf("%d\\n",m%(n+1));
    } 
    return 0;
}

2. 威佐夫博奕（Wythoff Game）

这种博弈比前面一种要稍微复杂一点。我们来看下下面这个游戏。
有两堆火柴棍，每次可以从某一堆取至少 1 根火柴棍 (无上限)，或者从两堆取相同的火柴棍数。最后取完的是胜利者。好了，如果你不知道这个博弈定理，对于小数目的火柴棍数，可能还能推出来，但是如果火柴棍数一多，就不行了。看了下面的这个介绍，你也会有一种被骗的感觉。
首先我们知道两堆火柴是没有差别的，也就是说第一堆有 a 根，第二堆有 b 根和第一堆有 b 根，第二堆有 a 根是一样的结果。
我们用一个二维的状态（a,b) 来记录当前剩下的火柴数，表示第一堆剩下 a 根火柴，第二堆剩下 b 根火柴。同样我们假设两个人的编号是 A 和 B，且 A 先取。
那么如果某个人遇到了这样的状态 (0,0) 那么也就是说这个人输了。这样的状态我们叫做奇异状态 , 也可以叫做失败态。
那么接下来的几个失败态为 (1,2),(3,5),(4,7),(6,10),(8,13)……
我们用 a [i] 表示失败态中的第一个，b [i] 表示失败态中的第二个.(i 从 0 开始).
那么我们可以看到 b [i] = a [i]+i;（i >= 0）,a [i] 是前面的失败态中没有出现过的最小的整数
下面我们可以得到三个基本的结论。

1. 每个数仅包含在一个失败态中
   首先我们知道 a [k] 是不可能和前面的失败态中的 a [i],b [i] 重复的 (这点由 a [i] 的得到可以知道)
   b [k] = a [k]+k > a [k-1]+k>a [k-1]+k-1+1>a [k-1]+(k-1) = b [k-1]>a [k-1] 这样我们知道每个数仅在一个失败态中。
2. 每个失败态可以转到非失败态。
   加入当前的失败态为 (a,b)，那么如果我们只在一堆中取的话，肯定会变成非失败态 (这点由第一点可以保证), 如果从两堆同时取的话，由于每个失败态的差是不一样的，所以也不可能得到一个失败态。也就是说一个失败态不管你怎么取，都会得到一个非失败态。
3. 每个非失败态都可以转到一个失败态
   对于这个结论，首先我们要知到每个状态 (a,b) 要么 a = a [i], 要么 b = b [i].(每个数都出现在一个失败态中), 下面我们分两种情况来讨论
   I.a = a [i]. 如果 b = a 的话那么一次取完就变成了 (0,0). 如果 b > b [i] 的话，那么我们从第二堆中取走 b-b [i] 就变成了一个失败态。如果 b < b [i]. 那么我们从两堆中同时取走 a-a [b-a [i]] 这样得到失败态 (a [b-a [i]],a [b-a [i]]+b-a [i])(a [i] = a)
   II.b = b [i]. 如果 a > a [i] 那么我们从第一堆中取走 a-a [i] 根火柴.
   如果 a <a [i]. 这里又分两种情况。第一是 a = a k
   那么我们从第二堆取走 b - b [k] 就行了。
   第二是 a = b [k] 这样的话由于两堆火柴是没有区别的，所以我们把 b 变成 a [k] 就行了，也即是从第二堆火柴中取走 b - a [k] 就变成了失败态
   至于怎么判断一个状态是否是失败态。我们可以用下面的方法来判断 (本人暂时还不会证明)
   a[i] = i*(1+√5)/2 b[i] = a[i]+i;
   那么这就是一个失败态

找规律分析
第一个（0 ， 0），先手输，当游戏某一方面对（ 0 ， 0）时，他没有办法取了，那么肯定是先手在上一局取完了，那么输。
第二个 （ 1 ， 2 ），先手输，先手只有四种取法，
1）取 1 中的一个，那么后手取第二堆中两个。
2）取 2 中一个，那么后手在两堆中各取一个。
3）在 2 中取两个，那么后手在第一堆中取一个。
4）两堆中各取一个，那么后手在第二堆中取一个。
可以看出，不论先手怎么取，后说总是能赢。所以先手必输！
第三个 （ 3 ， 5 ），先手必输。首先先手必定不能把任意一堆取完，如果取完了很明显后手取完另一堆先手必输，那么
假如看取一堆的情况，假设先手先在第一堆中取。 取 1 个，后手第二堆中取 4 个，变成（1 ，2）了，上面分析了是先手的必输局。
取 2 个，后手第二堆中取 3 个，也变成（ 1 ， 2）局面了。
假设先手在第二堆中取，取 1 个，那么后手在两堆中各取 2 个，也变成 (1 , 2) 局面了。
取 2 个 ，那么后手可以两堆中都去三个， 变成 （ 0 ， 0）局面，上面分析其必输。
取 3 个，后手两堆各取 1 个 ，变成（ 1 ， 2）局面了。
取 4 个，后手在第一堆中取一个，变成（ 1 ， 2）局面了。
可见不论先手怎么取，其必输！
第四个（4 ， 7），先手必输。
自己推理可以发现不论第一次先手如何取，那么后手总是会变成前面分析过的先手的必输局面。
那么到底有什么规律没有呢，我们继续往下写。
第四个 （ 6 ，10 ）
第五个 （ 8 ，13）
第六个 （ 9 ， 15）
第七个 （ 11 ，18）
会发现他们的差值是递增的，为 0 ， 1 ， 2， 3， 4 ， 5 ， 6， 7…..n
而用数学方法分析发现局面中第一个值为前面局面中没有出现过的第一个值，比如第三个局面，前面出现了 0 1 2，那么第三个局面的第一个值为 3 ，比如第五个局面，前
面出现了 0 1 2 3 4 5 , 那么第五个局面第一个值为 6。
再找规律的话我们会发现，第一个值 = 差值 * 1.618
而 1.618 = （sqrt（5）+ 1） / 2 。
大家都知道 0.618 是黄金分割率。而威佐夫博弈正好是 1.618，这就是博弈的奇妙之处！

下面来看看威佐夫博弈常见的三类问题：

1）给你一个局面，让你求是先手输赢。
有了上面的分析，那么这个问题应该不难解决。首先求出差值，差值 * 1.618 == 最小值 的话后手赢，否则先手赢。（注意这里的 1.618 最好是用上面式子计算出来的，否则精
度要求高的题目会错）

2）给你一个局面，让你求先手输赢，假设先手赢的话输出他第一次的取法。
首先讨论在两边同时取的情况，很明显两边同时取的话，不论怎样取他的差值是不会变的，那么我们可以根据差值计算出其中的小的值，然后加上差值就是大的一个值，当
然能取的条件是求出的最小的值不能大于其中小的一堆的石子数目。
加入在一堆中取的话，可以取任意一堆，那么其差值也是不定的，但是我们可以枚举差值，差值范围是 0 — 大的石子数目，然后根据上面的理论判断满足条件的话就是一种合理的取法。

3. 尼姆博奕（Nimm Game）
   指的是这样的一个博弈游戏，目前有任意堆石子，每堆石子个数也是任意的，双方轮流从中取出石子，规则如下：
   1) 每一步应取走至少一枚石子；每一步只能从某一堆中取走部分或全部石子；
   2) 如果谁取到最后一枚石子就胜。
   也就是尼姆博弈（Nimm Game）。
   必败局面：也叫奇异局势。无论做出何出操作，最终结果都是输的局面。必败局面经过 2 次操作后，可以达到另一个必败局面。
   必胜局面：经过 1 次操作后可以达到必败局面。
   即当前局面不是必败局面就是必胜局面，而必胜局面可以一步转变成必败局面。
   最终状态：
   （1）最后剩下一堆石子；（必胜局面）
   （2）剩下两堆，每堆一个；（必败局面）
   （3）当石子剩下两堆，其中一堆只剩下 1 颗，另一堆剩下多于 n 颗石子时，当前取的人只需将多于 1 颗的那一堆取出 n-1 颗，则局面变为刚才提到的必败局面。（必胜局面）
   判断当前局势是否为必胜（必败）局势：
   1）把所有堆的石子数目用二进制数表示出来，当全部这些数按位异或结果为 0 时当前局面为必败局面，否则为必胜局面；
   2）在必胜局面下，因为所有数按位异或的结果是大于零的，那么通过一次取，将这个（大于其它所有数按位异或的结果的）数下降到其它所有数按位异或的结果，这时局面就变为必败局面了。

我们用 (a，b，c) 表示某种局势

1. 首先 (0，0，0) 显然是奇异局势，无论谁面对奇异局势，都必然失败。
2. 第二种奇异局势是 (0，n，n)，只要与对手拿走一样多的物品，最后都将导致 (0，0，0)。仔细分析一下，(1，2，3) 也是奇异局势，无论对手如何拿，接下来都可以变为 (0，n，n) 的情形。
   对于以上两种情况，均有三个数疑惑后为零。其实，只要取完数后使得剩下局面为三数异或结果为零，则胜。

例如 (14，21，39)，14 (+) 21=27，39-27=12，所以从 39 中拿走 12 个物体即可达到奇异局势 (14，21，27)。
我们来实际进行一盘比赛看看:

甲：(7,8,9)->(1,8,9) 奇异局势

乙：(1,8,9)->(1,8,4)

甲：(1,8,4)->(1,5,4) 奇异局势

乙：(1,5,4)->(1,4,4)

甲：(1,4,4)->(0,4,4) 奇异局势

乙：(0,4,4)->(0,4,2)

甲：(0.4,2)->(0,2,2) 奇异局势

乙：(0,2,2)->(0,2,1)

甲：(0,2,1)->(0,1,1) 奇异局势

乙：(0,1,1)->(0,1,0)

甲：(0,1,0)->(0,0,0) 奇异局势

甲胜。

代码：

import java.util.Scanner;

/**
 * Created by YYL on 2017/2/24.
 */
//A先取，若A面对奇艺局面，则失败
public class NimmGame {
    public static void main(String[] args) {
    Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();//堆数
        int [] temp=new int[n];
        for (int i = 0; i <n ; i++) {
            temp[i]=scanner.nextInt();//初始化每堆的个数
        }
        int result=temp[0];
        for (int i = 1; i <n ; i++) {
            result^=temp[i];
        }
        if(result==0)
            System.out.println("B胜");
        else
            System.out.println("A胜");
    }
}

运行结果

3
7 8 9
A 胜
————————————————

理论： 博弈 2： 巴什博奕（Bash Game）

巴什博奕基础情形
只有一堆 n 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 m 个。最后取光者得胜。

如果 n = m + 1； 我们假设第一个人拿走了 k 个， 还剩下 m + 1 - k。 因为 1<=（m + 1 - k）<= m, 所以， 剩下的部分一定可以被第二个人一次性取走。

现在我们将上述规律加一推广：
如果 n=（m+1）r+s（r∈ N，s<= m)；
那么先取者要拿走 s 个物品，如果后取者拿走 k（k<= m) 个，那么 先取者再拿走 m+1-k 个，结果剩下（m+1）（r-1）个，
以后保持这样的取法，那么先取者肯定获胜

那么在我方取最优解的情况下：
现在我们就发现了巴什博弈的一个必败态： （m + 1）* r （r∈ N）；
那么巴什博弈的必胜态也就可以反推出来： （m + 1）* r + k （1<=k<= m, r ∈N）;

现在我们换一个角度来考虑这个问题：
如果物品数量随机，那么先手一方胜利的概率是 m/(m+1)，后手方胜利的概率是 1/(m+1)

对于上述的问题， 我们可以用 mod 的方法快速的求出答案（其实三种博弈的最优美之处就是能用 %^& 这三个符号完美解答）

`

巴什博弈演变

硬币问题 1
Alice 和 Bob 在玩这样的一个游戏， 给定 k 个数组 a1,a2,a3,……ak。 一开始， 有 x 枚硬币， Alice 和 Bob 轮流取硬币， 每次所取硬币的枚数硬顶要在 a1,a2,a3,……ak 之中。 Alice 先取， 取走最后一枚硬币的一方获胜。 当双方都采取最优策略的时候， 谁会获胜？ 题目假定 a1,a2,a3,……ak 之中一定有 1。

下面我们来分情况讨论到达自己时， 还有 j 枚硬币的胜负情况：

1. 题目规定， 取光所有的硬币就获胜， 这等价于轮到自己时如果没有硬币就失败， 因此 j = 0 时是必败态。
2. 如果对于某个 i（i<=i<= k）, 就 j - ai 是必败态， 那么 j 就是必胜态（如果当前有 j 枚硬币， 只要取走 ai 枚对手就必败→自己必胜）；
3. 如果对于任意的 i（1 <= i <= k）， j - ai 都是必败态的话， j 就是必败态（无论对手这么走， 对手都必胜， 自己必败）

根据这些规则， 我们都能利用动态规划算法按照 j 从小到大的顺序计算必胜态。， 只要看 x 是必胜态还是必败态， 我们就知道谁会取胜；

通常来说， 通过考虑每个小状态的取胜条件， 判断必胜条件和必胜态， 是有胜负的游戏的基础；

上代码

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int x，k;
bool win[100000];
int a[100000];

void Bash()
{//轮到自己没有硬币则必败；
    win[0] = false;

    for (int i = 1; i <= x; i++) {
//如果可以让对手达到必败态， 则自己必胜；
        win[i] = false;
        for (int j = 0; j < k; i++)
            win[i] |= (a[j] <= i && !win[i - a[j]]); // |=   真真为真 真假为真  假假为假
    }
}

int main(void) {
    while (scanf("%d %d", &x, &k) != EOF) {
        for (int i = 0; i < k; i++)
            scanf("%d", &a[i]);
        sort(a, a + k);
        memset(win, 0, sizeof(a));
        Bash();
        if (win[x]) printf("Alicce!\\n");
        else printf("Bob!\\n");
    }
    return 0;
}

硬币问题 2
n 枚硬币排成一个圈。Alice 和 Bob 轮流从中取一枚或者两枚硬币， 不过， 取两枚时这两枚必须是连续的。硬币取走之后留下空位，想个空位的硬币被认为是不连续。 A 开始先取， 取走最后一枚硬币的一方获胜。双方都采取最优策略的时候谁会取胜？

按照上面问题的想法， 我们来拆分一下问题；

首先我们是想一下如下的情况。 将所有的剩余硬币分成完全相同的组别， 这个是必胜状态还是必败状态？

事实上这是必败态， 无论采取什么策略， 对手只要在另一组中使用相同的策略， 就有回到了相同分组的状态， 而最终的相同分组状态就是（0，0）；

接下来， 我们回归正题。A 在第一取走一枚或者两枚硬币之后，称圈的硬币就变成了长度为 n - 1 或者是 n - 2 的。 Bob 只要在中间位置根据链的奇偶性， 在链的中间位置取走 1 或者 2 枚， 就可以把所有的硬币分成长度相同的两个链。

正如我们所说的，这是必败态， 也就是说， Alice 必败， Bob 必胜，只不过， 当 n <= 2， Alice 可以一步取光， 所以胜利的是 Alice， 除此之外， 在都进行最优解的情况下， Alice 必败。

int k;

if(k <= 2) printf("Alice!\\n");
else printf("Bob\\n");

Euclid’s Game(poj 2348)
poj 传送门

题目大意：

给定两个整数 a, b。Alice 和 Bob 轮流用较大的数减去较小的数的整数倍， 并且相减之后的值不小于 0。 如果在自己的回合之内， 相减之后的结果为零， 那么获胜。Alice 先手。

根据上述两个问题我们有两个规律可以用上：1. 将大问题划分为小问题在进行解决 2. 寻找开始（或结束）位置的必败态（或必胜态）在加以正推（或倒推）；

划分： 我们按照后续处理的差别， 将其分为 3 类：
1.b < a, 我们将 a b 进行交换， 使得 b 恒大于 a；
2.a > (b - a)；
3.a < (b - a) ;

对于第一种情况， 为了便于后续处理， 我们将其认为是默认情况；
对于第二种情况， 我么可以选择在 b 的基础上减去 a， 或者减去 2a 和以上；（这一种是有余地的方案）
对于第三种情况， 我们仅仅只有减去 a 这一种方法；

对于第一种情况：默认的调整方式， 我们用来调整 a，b 代表的值， 在这里不用讨论（这里实际指的就是 swap 函数的调用过程）
对于第三种情况， 仅仅只有一种方案： 继续向下迭代， 直到出现最终结局；
对于第二种情况： 假设 x 是使 b - ax <a 成立的整数， 那么在第二种情况中又可以分为两种情况 I. b - ax; II.b - a (x - 1);

下面我们讨论 二.I： 这种情况和第三种情况类似， 只能向下迭代， 寻找最终的结果；
对于情况二.II：这种情况的后继情况就是情况就只有 b - ax 这一种情况， 很巧， 这又回到了情况三。而经过了两次转换， 这种情况依旧是必胜态；

int a, b;

bool flag = true;
while(true) {
    if(a > b) swap(&a, &b);
    if(b % a == 0) break;
    if(b - a > a) break;
    b -= a;
    flag = !flag; 
}
if(flag) printf("Alice!\\n");
else printf("Bob!\\n");

博弈论基础知识：巴什博奕 + 威佐夫博奕 + 尼姆博弈 (及 Staircase)

【嵌牛导读】：介绍一些博弈，因为算法有时候就是应用在博弈问题上。

【嵌牛鼻子】：巴什博奕 (Bash Game)。威佐夫博奕 (Wythoff Game)。尼姆博奕 (Nimm Game)。Nim Staircase 博奕。

【嵌牛提问】：什么是巴什博奕 (Bash Game)。威佐夫博奕 (Wythoff Game)。尼姆博奕 (Nimm Game)。Nim Staircase 博奕？

【嵌牛正文】：

(一) 巴什博奕 (Bash Game):

只有一堆 n 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 m 个。最后取光者得胜.

若 (m+1) | n，则先手必败，否则先手必胜。

显然，如果 n=m+1, 那么由于一次最多只能取 m 个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发

现了如何取胜的法则：如果 n=(m+1) r+s,(r 为任意自然数，s≤m), 那么先取者要拿走 s 个物品，如果后取者拿走 k (≤m) 个，那么先取者再拿

走 m+1-k 个，结果剩下 (m+1)(r-1) 个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下 (m+1) 的倍数，就能最后获胜.

(二) 威佐夫博奕 (Wythoff Game):

有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜.

奇异局势下先手必败，非奇异局势下先手必胜。

这种情况下是颇为复杂的。我们用 (ak,bk)(ak ≤bk ,k=0,1,2,...,n) 表示两堆物品的数量并称其为局势，如果甲面对 (0,0), 那么甲已经

输了，这种局势我们称为奇异局势。前几个奇异局势是：(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20).

可以看出，a0=b0=0,ak 是未在前面出现过的最小自然数，而 bk= ak + k, 奇异局势有如下三条性质：

1、任何自然数都包含在一个且仅有一个奇异局势中.

由于 ak 是未在前面出现过的最小自然数，所以有 ak > ak-1 , 而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 . 所以性质 1. 成立.

2、任意操作都可将奇异局势变为非奇异局势.

事实上，若只改变奇异局势 (ak,bk) 的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使 (ak,bk) 的两

个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势.

3、采用适当的方法，可以将非奇异局势变为奇异局势.

假设面对的局势是 (a,b), 若 b = a, 则同时从两堆中取走 a 个物体，就变为了奇异局势 (0,0)；如果 a = ak ,b > bk, 那么，取走 b - bk 个物

体，即变为奇异局势；如果 a = ak , b <bk , 则同时从两堆中拿走 ak - ab - ak 个物体，变为奇异局势 ( ab - ak , ab - ak+ b - ak)

；如果 a > ak ,b= ak + k, 则从第一堆中拿走多余的数量 a - ak 即可；如果 a <ak ,b= ak + k, 分两种情况，第一种，a=aj (j < k), 从

第二堆里面拿走 b - bj 即可；第二种，a=bj (j < k), 从第二堆里面拿走 b - aj 即可.

从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜.

那么任给一个局势 (a,b), 怎样判断它是不是奇异局势呢？我们有如下公式：

ak =k (1+√5)/2, bk= ak + k (k∈N)

奇妙的是其中出现了有关黄金分割数的式子：$\\frac{1+\\sqrt{5}}{2} = 1.618...$, 若两堆物品个数分别为 x,y (x<y)，则 k=y-x，再判断 x 是否等于 $y-x\\times \\frac{1+\\sqrt{5}}{2}$ 即可得知是否是奇异局势。

参考例题：POJ1067 取石子游戏

参考代码：

var a,b:longint;begin repeat readln(a,b); if a>b then begin a:=a xor b; b:=a xor b; a:=a xor b; end; if a=trunc((b-a)*(sqrt(5)+1)/2) then writeln(0) else writeln(1); until seekeof;end.

(三) 尼姆博奕 (Nimm Game):

有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜.

这种情况最有意思，它与二进制有密切关系，我们用 (a,b,c) 表示某种局势，首先 (0,0,0) 显然是奇异局势，无论谁面对奇异局势，都必然失

败。第二种奇异局势是 (0,n,n), 只要与对手拿走一样多的物品，最后都将导致 (0,0,0). 仔细分析一下，(1,2,3) 也是奇异局势，无论对手如

何拿，接下来都可以变为 (0,n,n) 的情形.

计算机算法里面有一种叫做按位模 2 加，也叫做异或的运算，我们用符号 xor 表示这种运算。这种运算和一般加法不同的一点是 1+1=0. 先看

(1,2,3) 的按位模 2 加的结果：

1 = 二进制 01

Xor 2 = 二进制 10

Xor 3 = 二进制 11

———————

0 = 二进制 00

对于奇异局势 (0,n,n) 也一样，结果也是 0.

任何奇异局势 (a,b,c) 都有 a xor b xor c =0。该结论可以推广至若干堆，都是成立的。

如果我们面对的是一个非奇异局势 (a,b,c), 要如何变为奇异局势呢？假设 a < b< c, 我们只要将 c 变为 a xor b, 即可，因为有如下的运算

结果: a xor b xor (a xor b)=(a xor a) xor (b xor b)=0 xor 0=0. 要将 c 变为 a xor b, 只要从 c 中减去 c-(a xor b) 即可.

(四) Nim Staircase 博奕:

这个问题是尼姆博弈的拓展：游戏开始时有许多硬币任意分布在楼梯上，共 n 阶楼梯从地面由下向上编号为 0 到 n。游戏者在每次操作时

可以将楼梯 j (1<=j<=n) 上的任意多但至少一个硬币移动到楼梯 j-1 上。游戏者轮流操作，将最后一枚硬币移至地上（0 号）的人获胜。

算法：将奇数楼层的状态异或，和为 0 则先手必败，否则先手必胜。证明略。

例题：Poj1704

这道题可以把两个棋子中间间隔的空格子个数作为一堆石子，则原题转化为每次可以把左边的一堆石子移到相邻的右边的一堆中。也就

是阶梯尼姆博弈，注意对输入数据先排序，然后倒着往前数（a [n]-a [n-1]-1 为第一个），奇数个数到的就做一下 xor，其中最前面的看

做 a [1]-0-1，参考程序：

var t,n,b,i,j:longint; a:array [0..1000] of longint;begin readln (t); repeat dec (t); readln (n); for i:=1 to n do read (a [i]); qsort (1,n);// 快排略 j:=0; b:=0; for i:=n downto 1 do begin inc (j); if odd (j) then b:=b xor (a [i]-a [i-1]-1); end; if b=0 then writeln ('Bob will win') else writeln ('Georgia will win'); until t=0;end.

其他题目

【hdu-1846】Brave Game

【hdu-4764】Stone

https://www.cnblogs.com/zwfymqz/p/8460192.html
版权声明：本文为CSDN博主「yyl424525」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/yyl424525/article/details/56840182
版权声明：本文为CSDN博主「sun897949163」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/sun897949163/article/details/50609070
https://www.jianshu.com/p/0b84d77a3bfd