组合博弈

组合博弈

• 问题引入:

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

这其实是一个典型的组合博弈类问题，看似公平的游戏其实内藏乾坤，如若某一方知道其中的奥秘，将立于不败之地。下面将给出组合博弈类问题的具体定义：

• 组合游戏定义：

  1、有且仅有两个玩家 2、游戏双方轮流操作 3、游戏操作状态是个有限的集合（比如：取石子游戏，石子是有限的，棋盘中的棋盘大小的有限的） 4、游戏必须在有限次内结束 5、当一方无法操作时，游戏结束。

• 几个比较著名的博弈：

  1. 巴什博奕（Bash Game）：有一堆n个物品，两人轮流从堆中取物品，每次取 x 个 （ 1 ≤ x ≤ m）。最后取光者为胜。
  2. 威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
  3. 尼姆博奕（ Nimm Game）：有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

• 算法

  首先提升一下巴什博奕，每次只能取n个物品n∈[1,2,3]，原本后取者必胜的游戏增加了难度，请读者思考一下该如何做才能必胜呢？

  • 概念引入：

    必胜点N / 必败点P / 终结点

    i.所有的终结点都是必败点

    ii.从任何必胜点操作，至少有一种方法进入必胜点

    iii.不论如何操作，从必败点都只能进入必胜点

  • 举例：一共12个物品，每个人只能拿1、2、3个。

    0	1	2	3	4	5	6	7	8	9	10	11	12
    P	N	N	N	P	N	N	N	P	N	N	N	P

    列出上表可见，始终让对手保持再必败点一定能赢得该游戏。如果一共十二个物品，先拿必败。💢

  • 再回看Nim游戏，对于每个状态我们定义（x1，x2，x3）例如三堆里还剩（3，7，9）判断此时位于什么状态时，将三个状态的十进制数转化为二进制数，再进行按位异或运算，即：当且仅当（x1⊕x2⊕x3=0）时，当前处于必败点。

  • 如果我们面对的是一个非必败态(a,b,c)，要如何变为必败态呢？假设 a < b < c，我们只要将 c 变为a⊕b，即可。因为有如下的运算结果：

    a⊕b=c，c⊕c=0；

    所以将对c做 c-(a⊕b) 处理就可以使结果转化为必败状态。

• SG函数（Sprague-Grundy） 一种通用解法 ❤

  sg(x)=mex{ sg(y) | y是x的后继 }

  mex｛｝是定义在整数集合上的操作。它的自变量是任意整数集合，函数值是不属于该集合的最小自然数。 例如mex{ 1 3 5 } = 0；mex{ 0 1 2 }= 3；

  • 举例：

    有1堆n个的石子，每次只能取{ 1, 3, 4 }个石子，先取完石子者胜利，那么各个数的SG值为多少？

    0	1	2	3	4	5	6	7	8
    0	1	0	1	2	3	2	0	1

  • 解释

    当状态等于0时，没有后继 sg = 0

    当状态等于1时，拿走1个石子之后，状态变为0，即后继为sg(0)，所以 sg = mex{sg(0)} = 1；

    当状态等于2时，拿走1个石子之后，状态变为1，即后继为sg(1)，所以 sg = mex{sg(1)} = 0；

    当状态等于5时，拿走1、2、3个石子之后，状态变为4、3、2，即后继为sg(4)、sg(3)、sg(2)，所以 sg = mex{sg(4)、sg(3)、sg(2)} = 3；

  样例代码：记忆化DFS实现SG函数

  #include<bit/stdc++.h>
  using namespace std;
  int k,a[100],f[10001];
  
  int sg(int p)
  {
      int i,t;
      bool g[101]={0};
      if(f[p]!=-1)return f[p];
      for(i=0;i<k;i++)
      {
          t=p-a[i];
          if(t<0)break;
          if(f[t]==-1) f[t]=sg(t);
          g[f[t]]=1;
      }
      for(i=0;;i++)
      {
          if(!g[i])
          {
              f[p]=i;
              return f[p];
          }
      }
  }