（五）简单博弈论

公平组合游戏ICG

若一个游戏满足：由两名玩家交替行动；

在游戏进程的任意时刻；
可以执行的合法行动与轮到哪名玩家无关；
不能行动的玩家判负；

则称该游戏为一个公平组合游戏。 NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

Nim游戏

给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。 NIM博弈不存在平局，只有先手必胜和先手必败两种情况。

必胜状态，先手进行某一个操作，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。
必败状态，先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态。即先手走不到任何一个必败状态。

结论：假设n堆物品，数目分别为a1,a2,a3…an，如果a1⊕a2⊕a3.......⊕an != 0，则先手必胜；否则为0，先手必败（证明AcWing 891. Nim游戏 - AcWing）

如果先手面对的局面是a1⊕a2⊕…⊕an≠0，那么先手总可以通过拿走某一堆若干个石子，将局面变成a1⊕a2⊕…⊕an=0。如此重复，最后一定是后手面临最终没有石子可拿的状态。先手必胜。
如果先手面对的局面是a1⊕a2⊕…⊕an=0，那么无论先手怎么拿，都会将局面变成a1⊕a2⊕…⊕an≠0，那么后手总可以通过拿走某一堆若干个石子，将局面变成a1⊕a2⊕…⊕an=0。如此重复，最后一定是先手面临最终没有石子可拿的状态。先手必败。

AcWing891. Nim游戏

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    int res=0;
    while(n--){
        int a;
        cin>>a;
        res^=a;
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}

AcWing892. 台阶-Nim游戏

实现思路：

此时我们需要将奇数台阶看做一个经典的Nim游戏，如果先手时奇数台阶上的值的异或值为0，则先手必败，反之必胜

证明：

先手时，如果奇数台阶异或非0，根据经典Nim游戏，先手总有一种方式使奇数台阶异或为0，于是先手留了奇数台阶异或为0的状态给后手
于是轮到后手：
- ①当后手移动偶数台阶上的石子时，先手只需将对手移动的石子继续移到下一个台阶，这样奇数台阶的石子相当于没变，于是留给后手的又是奇数台阶异或为0的状态
- ②当后手移动奇数台阶上的石子时，留给先手的奇数台阶异或非0，根据经典Nim游戏，先手总能找出一种方案使奇数台阶异或为0

因此无论后手如何移动，先手总能通过操作把奇数异或为0的情况留给后手，当奇数台阶全为0时，只留下偶数台阶上有石子。（核心就是：先手总是把奇数台阶异或为0的状态留给对面，即总是将必败态交给对面）

因为偶数台阶上的石子要想移动到地面，必然需要经过偶数次移动，又因为奇数台阶全0的情况是留给后手的，因此先手总是可以将石先移动到地面，当将最后一个（堆）石子移动到地面时，后手无法操作，即后手失败。

故先手时奇数台阶上的值的异或值为非0，则先手必胜，反之必败！

#include <iostream>
using namespace std;
int main(){
    int res=0;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(i%2) res^=x;//选择奇数台阶进行异或
    }
    if(res) puts("Yes");//异或非0 必胜
    else puts("No");
}

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即： mex(S) = min{x}, x属于自然数，且x不属于S。eg：mex({1,2,3})=0，mex({0,1,2})=3

SG函数

在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, …, yk，定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果，即： SG(x) = mex({SG(y1), SG(y2), …, SG(yk)}) 特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(起点)。且图的终点（即不含出边的点）的SG函数值为0.

定理：

有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值不为0。
有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。

有向图游戏的和

设G1，G2,····,Gm是m个有向图游戏.定义有向图游戏G,他的行动规则是任选某个有向图游戏Gi,并在Gi上行动一步.G被称为有向图游戏G1,G2,·····,Gm的和. 有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数的异或和,即:SG(G)=SG(G1)⊕SG(G2)⊕··⊕ SG(Gm)

AcWing 893.集合-Nim游戏

若有一堆的数量为10，取法为2，5，则他的状态图如下所示，就是每次选择取法不同，出现不一样的分支

得到其SG函数的值，即SG(10)=1。同理计算其他石子堆的的SG值，将所有堆SG值异或，若不为0，则先手必胜，若为0则先手必败。（更具体解释AcWing 893. 集合-Nim游戏 - AcWing）

实现思路：

设置取法数组s[]，所有石子堆共享操作
设置一个数组f，f[x]记录图中某点x的SG值，初始为-1表示x还未计算。注意只要x的SG确定了那么就不会再改变，因为针对同一个数x，无论在哪个石子堆，他就只能执行相同的操作，因为所有石子堆共享取法集合。比如x=5，取法{2,5}，那么在任何石子堆，x的出边只能为0或3，固定的；
这里使用一个哈希表S存储当前点出边点的SG值，以此确定当前点的SG值，可实现自动排序，和判断某个值是否出以此来完成mex操作（选出最小且没有出现的自然数）。哈希表S必须定义为局部变量，每次递归都会使用新的哈希表，所以一个图其他不与当前点相连的点的存在不会影响当前点SG的计算

为什么哈希S不能开全局，只能作为局部变量？

对于集合-Nim，注意到0这个值可以被映射多次（如上图），这意味着有多个可能的值xi作为叶子节点（末尾节点），满足f[xi] = 0。而如果将S作为全局变量，则其中只能有一个值x’映射到0，由mex函数知其他的值都将映射到大于0的值（即f[x’] = 0，f[xi/x’] > 0，xi/x’代表集合x排除掉x’所剩值组成的集合），因而不能将S作为全局变量，防止不同点的相互影响。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
const int N=110,M=10010;
int n,m;
int f[M],s[N];//f存储出现的某点的SG值，s存储取法数
 
//求各点的SG值
int sg(int x){
    if(f[x]!=-1) return f[x];//表示点x的SG值已经计算过 直接返回即可
    
    unordered_set<int> S;//哈希表 存储x能到的点的SG值，以此确定x的值 每次递归都是新的
    for(int i=0;i<m;i++){
        int op=s[i];//取一个操作数
        if(x>=op) S.insert(sg(x-op));//一条分支路径 直到终点
    }
    
    //mex操作 确定x的SG值
    for(int i=0;;i++)
        if(!S.count(i)) return f[x]=i;//选出最小的没有出现的自然数,赋给x的SG值
    
}
 
int mian(){
    cin>>m;
    for(int i=0;i<m;i++) cin>>s[i];
    memset(f,-1,sizeof f);//初始化为-1 表示还未计算
    cin>>n;
    int res=0;
    while(n--){
        int x;
        cin>>x;
        res^=sg(x);//各个堆的SG值异或，每个堆的SG=起点的SG值
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}

AcWing894. 拆分-Nim游戏

实现思路：首先可以看出必然会有解（有限的），因为每次放入的两堆规模各自都会比原规模小，各堆石子每次操作后呈递减趋势，最后必然会趋于0，比如一堆石子个数是1，取走以后，只会再放入两堆个数为0的石子。

相比于集合-Nim，这里的每一堆可以变成小于原来那堆的任意大小的两堆

即a[i]可以拆分成(b[i], b[j]),为了避免重复规定b[i]>= b[j],即: a[i]>b[i]>= b[j]

相当于一个局面拆分成了两个局面，由SG函数理论，多个独立局面的SG值，等于这些局面SC值的异或和。

因此需要存储的状态就是sg(b[2])^sg(b[])(与集合-Nim的唯一区别)

PS:因为这题中原堆拆分成的两个较小堆小于原堆即可，因此任意一个较小堆的拆分情况会被完全包含在较大堆中，因此S可以开全局。当然也可以在函数中定义。

#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
const int N=110;
 
int n;
int f[N];
unordered_set<int> S; //开成全局变量
 
//求sg的值
int sg(int x){
    if(f[x]!=-1) return f[x];//表示已经求过了 不需要再求
    
    //将一堆石子拆分为两堆更小的石子i j
    for(int i=0;i<x;i++)
        for(int j=0;j<=i;i++)//规定j不大于i，避免重复计算
            S.insert(sg(i)^sg(j));//由SG的函数理论，多个独立局面的SG值等于这些局面SG值的异或
    //mex操作 得到不存在的最小数
    for(int i=0;;i++)
        if(!S.count(i)) return f[x]=i;
}
 
int main()
{
    memset(f , -1 , sizeof f);
 
    cin >> n;
    int res = 0;
    while(n--)
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }
 
    if(res) puts("Yes");
    else puts("No");
    return 0;
}

DP问题，通常从2方面来思考：状态表示和状态计算

状态表示

从2方面考虑

集合（某一个状态表示的是哪一种集合）
属性（这个状态存的是集合的什么属性）

一般属性有三种：集合的最大值，集合的最小值，集合中的元素个数

状态计算

状态转移方程，即集合的划分。比如对 f(i, j)，考虑如何将其划分成若干个更小的子集合，而这些更小的子集合，又能划分为更更小的子集合。

集合的划分有2个原则：

不重：即不重复，某个元素不能既属于子集合A，又属于子集合B
不漏：即不漏掉任一元素，某个元素不能不属于任何一个子集合。

通常需要满足不漏原则，而不重不一定需要满足。

动态规划的时间复杂度=状态数量*转移的计算量

编程笔记

探索

（五）简单博弈论