博弈论（基础）

一些用处不多的姿势：

perfect information:双方做决策时知道当前局面处于什么状态以及可能向什么状态转移。（如围棋你知道当前局面以及可以知道对手下一步可以走的位置）

complete information;博弈双方知道各自的目的。（如狼人杀显然不是，你不知道对方的身份以及对方取得成功的条件）

impartial game(平等博弈);在同一状态下，可能的决策集合与决策人无关。(围棋不是平等博弈，黑棋和白棋要做的决策不同)

小练习（均可打表找规律）：

练习一

POJ #2505 A multiplication game

如果当前数为(n,n/9]先手必胜，因为先手只要乘9一定大于等于n。

如果当前数为(n/9,n/18]先手必败，因为先手无论乘什么，后手乘9一定大于等于n。

如果当前数为(n/18,n/163]先手必胜，因为先手总能将数控制到(n/9,n/18]先手必败态，所以先手必胜。

观察可知n除到小于18，若a在2到9则先手必胜，否则后手必胜。

口胡证明：2到9时先手只要将数乘到大于等于18，接下来后手无论怎样乘最后一定乘9小于目标乘18大于目标。

#include <bits/stdc++.h>
using namespace std;
double n;
int main()
{
    while(scanf("%llf",&n)!=-1)
    {
        while(n>18)n/=18;
        if(n>9)printf("Ollie wins.\n");
        else printf("Stan wins.\n");
    }    
    return 0;
}

练习二

有两堆石子分别 n, m 个, 双人博弈, 每次操作是清空其中一堆石子并将另一堆石子 分成非空的两堆新的石子. 无法操作者输, 问最后谁会获胜. 例: (1, 1) 是先手必败, (2, 1) 是先手必胜.

只要有一个偶数，先手必胜，否则后手必胜。

考虑有一个偶数，只要去掉另一个数，将偶数分成两个奇数，后手只能去掉一个奇数，将另一个奇数分成一奇一偶。因为偶数最小为2（不可能出现0），所以先手一定可以做操作，后手最后会遇到1,1的情况输掉比赛。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    if(n%2!=0&&m%2!=0)printf("后手必胜\n");
    else printf("先手必胜\n");
    return 0;
}

练习三

有一块 n × m 的网格, 双人博弈, 每次操作是选中其中一个未被删除的格子 (x0, y0), 将所有 x ≥ x0 且 y ≥ y0 的格子 (x, y) 删除. 删除 (1, 1) 的人输, 问最后谁会获胜.

打表发现几乎全是先手必胜。

因为对于先手来说有一点可以改变先后手即(n,m)，如果先手选(n,m)后，后手有必胜策略选（x,y）则先手可以在第一步选(x,y)而不是(n,m)。

所以只有当只有一个网格时先手必败，否则先手必胜。

练习四

有一堆石子共 n 个, 双人博弈, 每次从石子堆中取出 1 ∼ m 个石子. 无法操作者输, 问最后谁会获胜.

小学数学题，只要看n%(m+1)，如果为0则先手必胜，否则后手必胜。

只要先手取走n%(m+1)个，则一定剩m+1的倍数，后手取x个，先手取m+1-x个即可。先手一定取到最后一个数，先手必胜。

SG函数：

任意一个平等博弈可以抽象出一个模型，一张有限无环图，其中一个节点上有一个棋子. 从 Alice 开始游戏, Alice 和 Bob 轮 流将这个棋子沿着一条有向出边移动, 无法移动者判负. 问最后谁会获胜。

定义一个SG函数：其函数值为其指向的节点的函数值的mex（没有出现的最小整数值），同时一个点没有出边定义为0。

显然，如果SG函数的值为0（以下的分析不考虑没有出边的情况），意味着没有办法转移到一个先手必败的情况，同时它出边的SG函数一定不为0，则它的出边一定可以转移到一个先手必败的状态，所以此时先手必败，否则先手必胜。

SG定理：

对一个由多个平行进行的组合游戏构成的博弈, 其整体的 SG 函数值为各个子游戏的函数值的异或和.

证明：不会，先放着。

NIM游戏:

练习四的进阶版，从一堆石子变成n堆石子。

考虑每一堆石子互不影响，满足平行进行的条件，SG函数直接用，对于初始情况算每一堆的SG函数的异或和，若为0，先手必败，反之，先手必胜。

nim的重要性是，SG函数几乎等价于一个NIM游戏,why?SG函数与NIM不同在SG可以向SG函数大的情况转移，但如果先手向大的转移，后手一定可以转回来，又因为，游戏无环一定在有限次数中结束。向SG大的转移绝大时间是无意义的，先手的最优策略一定是向SG小的情况转移。

NIM游戏（SG函数）的变种：

POJ #2425.A Chess Game

有一个 n 个点的有向无环图, 其上有 m 个棋子. Alice 和 Bob 在其上博弈, 每次可以 将其中一枚棋子沿出边移动一次, 允许棋子重叠. Alice 先开始, 不能移动则输掉游 戏, 问最后谁会获胜.

n ≤ 103 , m ≤ 10.

与普通情况完全相同。

 hdu 3032 nim or not nim

现在有 n 堆石子, 第 i 堆有 ai 个. 双人博弈, 每次从一个当前非空的石子堆当中取 至少一个, 或者选取一个石子堆分成两个非空的石子堆. 无法操作者输, 问最后谁会 获胜.

考虑只有一堆，用SG函数解决n堆。

当一堆有x个，可以操作一同最开始的SG，或操作二分成俩堆。sg(x)=mex{sg(i), sg(i) xor sg(x−i)},打表找出规律，SG(4k) = 4k − 1, SG(4k + 1) = 4k + 1, SG(4k + 2) = 4k + 2, SG(4k + 3) = 4k + 4.

#include <bits/stdc++.h>
using namespace std;
inline int SG(int x)
{
    if(!(x%4)) return x-1;
    else if(x%4==3) return x+1;
    return x;
}
int t,n,res; 
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n),res=0;
        while(n--) 
        {
            int x;scanf("%d",&x);
            res^=SG(x);
        }
        puts(res?"Alice":"Bob");
    }
    return 0;
}