博弈

巴什博弈（Bash Game）

一堆n个物品，两人轮流取出（1~m）个，最终取完者胜出

分析

若n = m + 1,先手必败——结论①

->若n = k (m + 1)，第二个人有可以使物品最终变为(m + 1)的办法，先手必败*——结论②

->若n = k (m + 1) + r,先手拿走r个，由结论②得后手必败、先手必胜*——结论③

Code

bool Bash_Game(int n, int m)
{
    if(n % (m + 1) != 0)
        return 1;
    return 0;
}

若有n堆，每堆a[i]个物品，两人来取，如何判断？

先考虑取的最大数目无上限即可以把一堆全部取完的情形：

一堆，无论数目多少，先手必胜

两堆，从最简单的情况开始考虑：

1 、1时，后手必胜

1、n时，先手取走(n - 1)，变成上述情况，先手必胜

a 、b时(a >= 2 && b >= 2)

若先手取走其中一堆会输

若先手取完变成1、n也会输（最终谁取完后局面为1、n谁就输了）

所以要保证先手取完还是c、b或a、d

N堆，也是：最终谁取完后局面变为1、n谁就输了

尼姆博弈（Nimm Game）

如上述n堆物品，每堆a[i]个,两人轮流取（从其中一堆中取，数目不限），是否有先手必胜策略？

分析

如果把n堆抽象为n个非负整数,再将n个整数转化为二进制,然后对n个二进制数按位相加(不进位),若每一位相加都为偶数, 称这个状态为偶状态,否则称它为奇状态. （可以看到偶状态限制条件严苛）

可以证明:任何一个偶状态在其中一个数变小后一定成为奇状态,而一个奇状态一定可以通过改变一个数变成偶状态.

证明：

前一点很显然,因为一个数变小至少有一位发生改变,这一位就改变了原来的偶状态.

对于后一点,对于一个从高位到低位某一位和为奇的奇状态,必定有一个数的二进制表示在此位为1,对于后面的较低位和为奇的情况,只要把这个数对应位取反即可得到一个偶状态

对于n堆物品,只要判断它出是奇状态就可以断定先手有必赢策略

位运算（异或）代替求二进制判断奇状态：

如果有奇数个二进制数在第K位为1，那么在这一位上的和为奇（已可以表明这就是一个奇状态）

在位运算方面体现为：所有数字异或后得到的ans在第K位为1

这一条件可以放大为ans != 0，意味着ans至少有一位1，我们说那就是第K位。

Code

bool Nimm_Game(int n)
{
    int flag = 0;
    for(int i = 0; i < n; ++i)
        flag ^= a[i];
    if(flag)
        return 1;
    return 0;
}

但是有时会遇到n很大，a[i]为连续整数的特殊情况，这时有特殊算法

Strange code

//读入n，表示有从物品数分别1到n的n堆物品，假设n个数存在数组f[]中
int xor_n(int n)//从1到n的异或和
{
     int t = n & 3;
     if (t & 1) 
         return t / 2 ^ 1;
     return t / 2 ^ n;
}
int Nimm_Game(int n)//有必胜策略返回1
{
    int flag = 0;
    for(int i = 1; i <= n; i++)
        flag ^= xor_n(f[i]);
    if(flag) 
        return 1;
    return 0;
}

另一种解释

用(A,B,C)来表示某一特定局势，同时规定A<=B<=C。奇异局势表示先手必败。

显然(0,0,0)是奇异局势。

(0,n,n)是奇异局势，当先手拿走s个石子时，我们对应拿走s个石子，最终转化为(0,0,0)

(1,2,3)也是奇异局势，无论先手如何取，我们都可以转化为(0,n,n)的局势。

对于一个奇异局势(A,B,C),我们可以发现，A(XOR)B(XOR)C = 0。

下面是一条需要的前置技能：

设有数字a,b，a(XOR)b(XOR)(a(XOR)b) = (a(XOR)a)(XOR)(b(XOR)b) = 0

对于一个非奇异局势(A,B,C),我们只需要将C转化为(A(XOR)B)即可，而将C转化为(A(XOR)B)的操作为，拿走K = C-(A(XOR)B)个即可。

3可扩展到N

原文出处： https://blog.csdn.net/pengwill97/article/details/76796070

威佐夫博弈（Wythoff Game）

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

如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：

（0，0）、（1，2）、（3，5）、（4，7）、（6，10）.

可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk=ak+k.

面对奇异局势，先手必败

面对非奇异局势，必然存在使其变为奇异局势的方案，使后手必败，从而先手获胜

取石子游戏： http://poj.org/problem?id=1067

Code

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;


int main()
{
    int a, b, k, tem;
    while(cin >> a >> b)
    {
        if(a > b)
            a ^= b, b ^= a, a ^= b;
        k = b - a;
        tem = (int)((sqrt(5.0) + 1) / 2 * k);
        if(tem == a)
            cout << '0' << '\n';
        else
            cout << '1' << '\n';

     /* double tem = (sqrt(5.0) - 1.0) / 2.0;
        k = a * tem;
        if(a != k * (int)(tem + 1))
            ++k;
        if(a + k == b)
            cout << '0' << '\n';
        else
            cout << '1' << '\n'; */
    }
    return 0;
}

文章出处: https://www.cnblogs.com/ECJTUACM-873284962/p/6398385.html