整理了一些博弈论模型，但大部分还是咕咕咕了(●ˇ∀ˇ●)

博弈论

组合游戏

前言

组合游戏是指一种两个玩家的游戏，每个玩家都是聪明绝顶不存在随机操作，比如打牌不是，游戏的结果只有赢和输。

通常玩家会交替移动，直到游戏结束，即达到终止状态，不存在任何一种可行的移动方式的状态。

这种游戏的结果在一开始就已经被决定了，由游戏的集合，游戏的初始状态和玩家的先后手完全确定。

组合游戏的形式有两种分别是Impartial Combinatorial Games和Partizan Combinatorial Games，前者是指在游戏中两位玩家进行的移动是完全相同的，后者则不相同比如国际象棋（NGNL），主要还是讨论ICG。

定义

形式化的定义一个组合游戏：

1. 两个玩家组成的游戏
2. 游戏存在一个有限的状态集合
3. 两个玩家的操作方式是相同的，没有区别
4. 玩家交替进行
5. 当玩家移动到终止状态时，游戏结束

一般的话都是最后一个移动的玩家获胜，讨论起来还相对简单，不过也存在最后一个移动的玩家失败的游戏，更为复杂一些。

不过重要的是，无论游戏怎样进行，都会在有限步数内结束。

另外，两个玩家都是足够聪明的玩家，每一步都会走最优策略。

状态

由于游戏的结果在一开始就可以确定，所以存在先手必胜和后手必胜。

定义P-position为先手必胜，N-position 为后手必胜。

NIM 游戏

前置知识

位运算

正文

NIM游戏，属于组合游戏的一种，起源可以追溯到很久以前，其游戏内容为：

有$n$堆石子Alice和Bob轮流从中取至少一个至多不超过一堆石子，谁取走最后一堆石子，谁就胜利。

是否存在一种先手必胜的策略？

这种问题的解决方法，是设$a_i$为每堆石子的数量，$x=a_1 \oplus a_2 \oplus a_3 \oplus \cdots \oplus a_n$，若$x\ne 0$则先手必胜，否则后手必胜。

证明：

1. 没有后继状态的状态为必败状态（Terminal Position）

   例如将石子取完后$x=0 \oplus 0 \oplus \cdots \oplus 0 = 0$，此时为N-position（此时先手已经没有可以取的石子了）。

2. 对于$x\ne 0$ 的局面一定存在某种移动使得 $x=0$，即P-position一定可以转移到N-position

   假设$a_1 \oplus a_2 \oplus a_3 \oplus \cdots \oplus a_n \ne 0$设$x$为1的最高位为第$k$位，那么一定存在一个$a_i$的第$k$位为1，此时$x \oplus a_i=a_1 \oplus a_2 \oplus \cdots \oplus a_n$，$x\oplus a_i$一定小于$a_i$（因为$x$的第$k$位不为0，异或$a_i$后为0肯定小于$a_i$），我们移走$a_i-a_i \oplus x$个石子，此时第$i$堆还剩$a_i-(a_i-a_i\oplus x)=a_i \oplus x$个石子，此时$a_1 \oplus a_2 \oplus \cdots \oplus a_i \oplus x \oplus \cdots\oplus a_n=x\oplus x=0$，得证。

3. 对于$x =0$的局面一定不存在某种移动使得$x=0$，即N-position一定不可转移到N-position

   设取走第$i$堆的石子后$a_i$变为了$a_i'$，此时$a_1 \oplus a_2 \oplus \cdots\oplus a_i' \oplus\cdots \oplus a_n = 0 =a_1 \oplus a_2 \oplus \cdots \oplus a_i \oplus \cdots \oplus a_n$得$a_i = a_i'$不成立。

至于异或为什么能表示状态之间的转移主要还是因为：

• 终止状态时显然有$0 \oplus 0 \oplus \cdots \oplus 0 = 0$
• 取出第$i$堆的石子的操作其实等价于将这堆石子的数目异或上一个数变为$a_i'= a_i \oplus k$
• 每个状态之间的异或其实就体现在上述证明中的第2，3条引理，对某个状态的异或就是对整体结果的异或

现在我们将取石子的游戏转化成了异或的游戏，同时也满足对应的规则，异或和在$x=0$与$x \ne 0$的两个状态间不停的转换，就体现了P-position和N-position之间的转换。

Anti NIM

前置知识

NIM

正文

Anti NIM游戏，就是修改NIM游戏的胜利判定为拿走最后一堆石子的失败，会变得更复杂一点（但也不难）

引理：

先手必胜当且仅当：

1. 每堆的物品数都为1且NIM和为0
2. 有些堆的物品数大于1且NIM和不为0

证明：

1. 当所有堆的石子均为1时
   • 石子NIM和$x=0$，此时有偶数堆，先手必胜
   • $x \ne 0$时，此时有奇数堆，先手必败
2. 当有一堆石子数$>1$时，此时$x$显然$\ne 0$
   • 若有奇数堆石子，此时把$>1$的那堆石子取至1个石子，转化为1中的2，先手必胜
   • 若有偶数堆石子，此时把$>1$的那堆石子取完，同样转化为1中的2，先手必胜
3. 当有两堆及以上石子数$>1$时
   • 若$x=0$，又可以分为两种情况
     • 转化为至少两堆石子$>1$且$x!=0$,转化到3中的2
     • 转化为一堆石子$>1$，由2可知，此时先手必胜
   • 若$x\ne 0$，根据NIM游戏的证明，必定有一种方法转化为3中的1，此时先手总是能让后手取进行3中的1，后手只能给先手3中2直至必胜状态，故此时先手必胜

Staircase NIM

前言

Staircase NIM是NIM游戏的又一种变形，不过还是非常简单

正文

这次Alice和Bob又换了种玩法，

有$n$堆石子，每次移动可以将第$i$层上的至少一个石子移动到$i-1$层上，谁取完最后一堆石子谁就胜利。

求是否存在一种先手必胜的策略。

首先考虑只有偶数层存在石子也就是说，假设对方为先手，那么对方只能将若干个石子移动的奇数层，此时我们再讲其移动到偶数层，直到最后偶数层上都没有石子（都到第0层上了），此时后手必胜

然后考虑奇数层的石子，将奇数层移动到偶数层，其实可以直接当做把奇数层的石子直接拿走，并不会影响之前偶数层策略的影响，那么就将问题转化为了奇数层之间的NIM博弈，如果可以做到留给对方的只有偶数层石子，则对方必败

其他博弈论游戏

占个坑 😱

博弈问题

1. A Funny Game

首先Alice作为先手，

• 拿一个，环断为长度为奇数的链，此时Bob再拿一个把链的长度变为偶数，接下来Alice拿几个Bob拿相同数目的硬币，Bob必胜
• 拿两个，环断为长度为偶数的链，此时Bob再拿两个链的长度仍然为偶数，接下来采取和1相同的策略即可，Bob必胜

综上，当$n \le 2$时Alice必胜，反正Bob必胜。（好像叫做对称博弈）

2.谁能赢呢？

很简单，就像多米诺骨牌去覆盖棋盘，$n$为奇数时需要挖掉左上和右下才能完全覆盖，此时后手必胜，$n$为偶数时直接覆盖此时先手必胜。

3.取石子

首先如果不能合并，那么只要石子总数是偶数，Alice就必胜，所以也就是说，合并操作是用来转换状态的。

1. 考虑石子个数$>$1，此时设$m$为石子总数加上石子堆数-1，若$m$为奇数则先手必胜，否则后手必胜

​ 证明：

​ $m$为奇数时，不管后手做哪一个操作均可将$m$变回奇数，最后合并为一堆时先手必胜。

​ $m$为偶数时，

• 先手选择合并，$m$变为奇数，变成后手的必胜局面
• 先手选择取$> 2$石子，$m$变为奇数，变成后手的必胜局面
• 先手选择取$=2$石子，$m$变为奇数，此时后手将$=1$的石子堆合并（如果选择取石子，则堆数-1，石子数-1，$m$为奇数，先手必胜）

2. 考虑石子个数$=1$，使用记忆化搜索，$f[i][j]$为有$i$堆石子为1，$j$堆数量不为1的状态。

4.A New Stone Game

考虑两堆石子数量相同，这时肯定是后手必胜，只要后手和先手一直做相同的操作就可以必胜。

如果有的石子数量不相同的话，此时必定存在一种方案使得操作后石子数量相同

1. 若当前有奇数堆石子的数量不能两两配对，则将其中的一堆石子全部取走，分到其他堆石子，使其两两配对，有偶数堆
2. 若当前有偶数堆石子的数量不能两两配对，则将其中的一堆石子不全部取走，分到其他石子，仍为偶数堆

所以此时后手面对的是必败状态，先手必胜。

5.小约翰的游戏

Anti NIM游戏，时间复杂度$O(n)$

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,sum=0,res=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            res^=x;
            sum+=(x==1);
        }
        if(sum==n&&res==0)
            printf("John\n");
        else if(sum!=n&&res!=0)
            printf("John\n");
        else 
            printf("Brother\n");
    }
    return 0;
}

6.NIM游戏

判断异或和即可，时间复杂度$O(n)$

#include<bits/stdc++.h>
using namespace std;
int T;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        int n,ans=0;scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int x;scanf("%d",&x);ans^=x;
        }
        ans?printf("Yes\n"):printf("No\n");
    }
    return 0;
}

坑。。。