数学-博弈论

· · 算法·理论

一、博弈论简介

博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。

详细介绍

显然，要求存在必胜策略时才有胜利，对于分一个数，一个奇数必定分成偶数和奇数，偶数分成奇数和奇数、偶数和偶数，这是显而易见。

那么我们可以从最简单的局面考虑。
当初始数为 1 时，先手必输，或说无必胜策略；
当初始数为 2 时，先手必赢，因为后手面临 1；
当初始数为 3 时，先手没有必胜策略，因为后手必将面临选 1 或者选 2，可以使先手输；
当初始数为 4 时，先手可以使得后手面临 1,3 或者 2,2 的选择，显然，使后手面临 1,3 可以保证先手赢，因为后手无必胜策略；
当初始数为 5 时，后手可能面临 1,4 或 2,3，其中无论哪种无法保证先手赢，先手无必胜策略
……

正所谓“一生二，二生三，三生万物”，显然，这里的规律十分明显，即奇数先手有必胜策略，偶数会输。

二、简单博弈

显然，小涵要选最大的武将组合，必须要得到两个武将，但是，当小涵选择其中一个时，计算机必选另一个，因为这个组合全局最大，即没有任何其他组合可以超过这个组合，所以计算机必选另一个，小涵无法得到全局组合的最大默契值。同样，计算机也没办法得到全局组合的最大默契值。
那么假设此时小涵选了武将 a，计算机选了武将 b，b 显然是含 a 的组合中默契值最大的组合的另一半，小涵若选全局第二小的武将组合的其中一个武将，假设这第二小的组合的任意武将都不是 a，那么计算机仍有办法使得小涵无法得到这个组合的默契值，道理是一样的。
所以在当前情况下，假设第一个选 a 是最优的，小涵至多得到含 a 的组合的次大值，显然，在上面的另一种假设中（即第二小组合的武将存在其一是 a）,也在这种情况之内，设这含 a 的组合的次大值的另一半是 c，此时计算机再选与 a 和 c 组合中最大的组合的另一半，设为 d。
当 a,c 的组合默契值大于 b,d 的组合默契值，当然小涵胜，因为前提保证先选 a 最优；当 a,c 的组合默契值小于 b,d 的组合默契值，与先选 a 最优矛盾，或者说，小涵完全可以先选 b，不管 b,d 是否是任意组合中的最大还是次大，小涵都可以使计算机得不到 b,d 组合，此时 小涵可以得到 a,b（b,d 最大）或者 b,d（b,d 次大）组合。
于是乎小涵总有办法薄纱计算机。

综上，枚举先选的 a ,再求含 a 组合的次大默契值，选择这些最大默契值中的最大值，即为答案，同时必定是小涵胜。

三、公平组合游戏 ICG

(Impartial Combinatorial Games)

若一个游戏满足：

则称该游戏为一个公平组合游戏。

四、有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边经行移动，每次可以移动一步，无法移动者判负，该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏，具体方法是：把每个局面看成图中的一个节点，并且从每个向沿着合法行动能够达到的局面连有向边。

五、NIM游戏

1.简介

Nim游戏是博弈论中最经典的模型（之一），它又有着十分简单的规则和无比优美的结论,Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（简称ICG）。

通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

2.求解

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

注意，任何可以胜利的策略都是最优策略。

定义两个概念：

当玩家总是选择最优策略时，

先手必胜状态：假如先手操作可以走到一个后手的一个必败状态，则先手必胜。

先手必败状态：假如先手无论如何操作都走不到对手的必败状态，即所有合法的路径到达的状态都是对方的必胜状态，则先手必败。

（这两个定义基本无用是不是可以不看？打死！）

正向探索

模拟一下，倘若先手先从2号石堆拿走一个，此时两堆石子都只有两个石子，然后陷入死局，先手胜。

为什么陷入死局呢？ 因为无论后手如何拿、拿几个 ，先手总有方法必胜。

例如，后手从1号石堆里拿走一个，那么先手从2号石堆里拿走一个，后手再从任意石堆拿走一个，先手只需要拿走最后一个，后手判负。

再例如，后手从任意一堆里拿走两个石子，即使得该石堆为空，先手只需要从剩下的石堆里拿走两个石子，后手判负。

我们得出结论：2 3 的 NIM 游戏先手必胜（在总是最优策略的情况下）。

可以看到，从最开始，先手就面临一个必胜状态，因为先手可以走到后手的必败状态。

然而我们发现了一个极其重要的“死局”:当玩家面临 (a) (a) 的石堆局面时，玩家必输。这时，我们可以想到，假若先手可以使局面到达“死局”,则后手必输，即先手必赢。

现在，我们将这样的死局命名为“兑取”。

\color{#F1AA00}\mathsf{正文开始}\\\scriptsize

复习一下，当玩家面临 (a) (a) 的石堆局面时，玩家必输，这时局面为兑取。

那么，兑取局面可不可以叠加？即，

不妨设 a\leq b 。

显然，此时可以把 (a+b) 当做 (a) (b) 的石堆，只要玩家（先手）取的石子数 k 满足 k\leq a 且 k\leq b ，那么后手总是可以构成兑取局面，先手必输。

下图虽未例出所有情况，但都类似。

那么，先手取的石子 k 要是 a<k 且 b<k ，结果如何？

显然，先手是想夺得胜利的，所以一种方法就是给后手造成“兑取”局面，那么先手会从 (a+b) 中拿走 2a 个石子，构成 (a) (b-a) (b) 的局面，显然此时我们回到了起点，因为 (a) (b-a) (b) 也是一种兑取叠加态，即 (a) (a+(b-a)) (b-a) 。

然后呢？，在得到兑取叠加态后，取k(k\leq a,k\leq b-a) 个石子当然好说，但是仍取 k(k>a,k>b-a) 个石子呢？

不慌，让我们暂停一下：

我们发现，在 (a) (a+b) (b) 的兑取叠加态局面中，可以使得局面再转化为新的兑取叠加态，即 (a) (a+(b-a)) (b-a) 来胜利，那么双方都想胜利，兑取叠加态会延续下去，直到……什么时候？直到有一项为 0 时，此时必定是一个 (0) (0+x) x 的局面，即兑取局面。在取石子的过程中，每一堆石子都会轮流被取，所以必定出现一个 0 。

反向研究

若a1⊕（异或）a2⊕a3⊕...⊕an=0 则先手必输，即为先手的必败状态，先手走不到任何一个必败状态；
若a1⊕（异或）a2⊕a3⊕...⊕an！=0 则先手必赢，即为先手的必胜状态，先手可以走到某一个必败状态。

证明：
已知:
    1、任何数和 0做异或运算，结果仍然是原来的数
    2、任何数和其自身做异或运算，结果是 0

在操作过程中，如果 a1⊕a2⊕…⊕an=x≠0。
那么玩家必然可以通过拿走某一堆若干个石子 将异或结果变为0。

证明：
    不妨设x的二进制表示中最高一位1在第k位，
那么在a1,a2,…,an中，必然有一个数ai，它的第k为时1，且ai⊕x<ai，
那么从第i堆石子中拿走ai−ai⊕x个石子，
第i堆石子还剩ai−(ai−ai⊕x)=ai⊕x，此时a1⊕a2⊕…⊕ai⊕x⊕…⊕an=x⊕x=0。

在操作过程中，如果 a1⊕a2⊕…⊕an=0a1⊕a2⊕…⊕an=0，那么无论玩家怎么拿，必然会导致最终异或结果不为0。

反证法：
    假设玩家从第i堆石子拿走若干个，结果仍是0。
不妨设还剩下a′个，因为不能不拿，所以0≤a′<ai，且a1⊕a2⊕…⊕a′⊕…⊕an=0。
那么(a1⊕a2⊕…⊕ai⊕…an)⊕(a1⊕a2⊕…⊕a′⊕…⊕an)=ai⊕a′=0，则 ai=a′，
与假设0≤a′<ai0≤a′<ai矛盾。

综上：
    a1⊕a2⊕a3⊕...⊕an=0先手必输；a1⊕a2⊕a3⊕...⊕an≠0 先手必赢

六、Mex 运算

设一个非负整数集合 S ,则 Mex(S) 表示不属于 S 的最小自然数，即：

Mex(S)=min(x) ，x 属于自然数且不属于 S 。

七、SG 函数

1.SG 函数定义

SG 函数一般用来表示有向图游戏的局面（当然，因为任何一个公平组合游戏可以转化为有向图游戏，所以 SG 函数也可表示公平组合游戏的局面） ，一般的，把终点的 SG 值设为 0 ，

SG(终点)=0

对于任意节点 x ，若其可到达的局面为 \{y_1,y_2,y_3……y_k\} ，则

SG(x)=Mex(\{y_1,y_2,y_3……y_k\})

2.SG 函数解决变种 Nim 游戏

给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。 现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子， 每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。 问如果两人都采用最优策略，先手是否必胜。

对于单独的一堆来讲，可以用例举的方式来求出一堆的 SG 值（根据 SG 函数定义求），由 SG 函数的定义可知，当且仅当 SG 值为 0 时，先手必胜，非 0 必输。

在求出一堆的 SG 值时，可以用记忆化搜索。 

#include<bits/stdc++.h>
using namespace std;
const int M=110,N=1e4+10;
int s[M],f[N];//s[]表示走的步数，f[]表示 SG 函数
int k,n;

int sg(int a)
{
    if(f[a]!=-1) return f[a];//记忆化

    unordered_set<int>all;//集合
    for(int i=0;i<k;i++)
    {
        if(a>=s[i]) all.insert(sg(a-s[i]));//找y_i
    }
    for(int i=0;;i++)//Mex
    {
        if(!all.count(i)) return f[a]=i;
    }
}

int main()
{
    memset(f,-1,sizeof(f));//init

    cin>>k;//拿走石子的允许个数
    for(int i=0;i<k;i++)
    {
        cin>>s[i];
    }

    cin>>n;//n堆石子
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int a;
        cin>>a;
        ans^=sg(a);//Nim判断
    }
    if(ans) cout<<"Yes";
    else cout<<"No";
    return 0;
}