博弈论

Posted on 2020-07-02 Edited on 2022-09-19 In 学后感

今天学了博弈论

必胜态与必败态

必败态：

我的后继状态全是必胜态

无论我如何选择我的对手都将会面临必胜态，我显然必输

我没有后继状态

默认谁不能拿谁输，我已经不能拿了，我显然输了

必胜态：

我的后继状态有一个是必败态，我就为必胜态

因为大家都是绝顶聪明的，我肯定会选择使我的后继状态变为必败态（我的对手将要面临的状态）

通过必胜态与必败态，我们可以画出：

博弈树

博弈树——和dfs树的一样数据量大

以巴什博弈为例子，

四大博弈

巴什博弈

每一次只可以取一个或者两个，规定取走最后一个的人是胜者

变种：每一次最少取1个最多取m个，两个人轮流取规定谁取走最后一个就是人生赢家

\(n\%(m+1) \neq 0\;?\;先手胜:后手胜\)

再变种，谁取到最后一个谁输

\((n-1)\%(m+1) == 0\;?\;后手胜\;：\;先手胜\)

Nim游戏

n堆石子，每次可以在一堆里面取出一个或至多\(a[i]\)个

结论：\(a_1\;xor\;a_2\;xor\;a_3......xor\;a_n\;==\;0?后手胜：先手胜\)

威佐夫博弈

每次每个人可以从任意一堆石子中取任意多的石子，或者从两堆石子中取同样多的石子，不能取得人输

结论：当且仅当\((x,y)(x<y),(y-x)\times\dfrac {\sqrt 5 +1} {2} = x\)，先手必败

斐波那契博弈

有一堆个数为n的石子，A，B轮流取石子，满足：

(1)先手不能在第一次把所有的石子取完；

(2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间 (包含1和对手刚取的石子数的2倍)

同之前的不同点就是:取的规则动态化，约定取走最后一个石子的就是赢家

结论：当且仅当n是斐波那契数字先手必败

威佐夫博弈与斐波那契博弈没有变种，要么都是裸的

SG函数

定义一个DAG，一个入度为零的点为起点，起点上有一个棋子，先/后手沿有向边，轮流移动，无法移动的人死

显然把博弈论弄到图论上了

mex运算

最小的，不属于集合内的元素

sg函数

我们考虑对于当前的节点x，其有k条出边，每天出边的重点为\(y_i\)

对于\(sg[x]\)，其值为\(y_{1...k}\)所有取值的mex

若对于x这个状态，\(sg[x]\)为零，意味着x状态是必败的，否则就是必胜的

可以这么理解：

\(sg[x]\)为零，意味着

要么自己没有初边，自己没有后继状态，显然必败
要么自己的初边\(sg[y_i]\)全部非零，自己的后继状态全部都是必胜，自己显然就是必败

\(sg[x]\)非零，意味着

自己的初边\(sg[y_i]\)一定有零，就是自己的后继状态一定有一个是必败，自己显然是必胜

显然，\(sg[x]\)是必胜的，只要其有值即可，为什么不直接变成1，反而要找mex呢？

因为有sg定理：

\(SG_{tot}=SG(1)\ \ xor \ \ SG(2)\ \ xor \ \ SG(3)\ \ xor \ \ SG(4)\ \ xor \ \ ......\ \ xor \ \ SG(n)\)

也就是游戏的sg值，为子游戏的sg值的异或和

考虑时间戳优化

hdu1848：

Code

SG[0] = 0;
f[0] = 1,f[1] = 1 ;
for(i = 2; i <= 20; ++ i) f[i] = f[i - 1] + f[i - 2];
for(i = 1; i <= 1000; ++ i) {
   ++ tot;
   for(j = 1; j <= 20; ++ j) if(i >= f[j]) vis[SG[i - f[j]]] = tot; 
   for(j = 0; ;++j) if(vis[j] != tot) {SG[i] = j; break;}
}
while(1) {
   cin >> x >> y >> z;
   if(!x && !y && !z) break; 
   res = SG[x] ^ SG[y] ^ SG[z];
   res ? puts("Fibo") : puts("Nacci");
}

关于Anti-Nim，有结论：

每一堆石子只有一个时且异或和为0
存在至少一堆石子多于一个时且异或和不为0

给出click一个板子题目的代码

Code

cin >> k;
while (k --> 0)
{
   res = 0, ans = 0, pd = 0;
   cin >> n;
   for (i = 1; i <= n; ++ i)
   {
      cin >> a[i];
      if (a[i] == 1) ++ res;
      ans ^= a[i];
   }
   if ((res == n && ! ans) || (res != n && ans)) pd = 1;
   pd ? puts("John") : puts("Brother");
}

关于Multi-Nim

Multi-SG游戏规定在符合拓扑原则的前提下一个单一游戏的后继可以是多个单一游戏
Multi-SG游戏其他规则同一般SG

对于一个状态来讲

不同的划分方法会有多个不同的后继，而在一个后继当中会有多个独立的游戏

该后继状态SG值即为后继状态中独立游戏的异或和，该状态的SG值即为后继状态的mex

这里有个click一个板子题目

Code

while (T --)
{
   cin >> n;
   for (i = 1; i <= n; ++ i) cin >> a[i], sg[i] = 0;
   for (i = n - 1; i; -- i)
   {
      memset(vis, 0, sizeof vis);
      for (j = i + 1; j <= n; ++ j) for (k = j; k <= n; ++ k) vis[sg[j] ^ sg[k]] = 1;
      for (j = 0; ; ++ j) if (! vis[j]) {sg[i] = j; break;}
   }
   res = 0;
   for (i = 1; i <= n; ++ i) if (a[i] & 1) res ^= sg[i];
   if (! res) puts("-1 -1 -1\n0");
   else
   {
      nx = 0, ny = 0, nz = 0, ans = 0;
      for (i = 1; i <= n; ++ i)
      for (j = i+1; j <= n; ++ j)
      for (k = j; k <= n; ++ k)
      if ((res ^ sg[i] ^ sg[j] ^ sg[k]) == 0)
      {
         ++ ans;
         if (nx && ny && nz) continue;
         nx = i, ny = j, nz = k;
      }
      printf ("%d %d %d\n%d\n", nx-1, ny-1, nz-1, ans);
   }
}

至此，博弈论的相关知识叙述完毕，代码不难，难在思想的转换

\(End...\)