博弈论

ACM博弈-II不平等博弈

先修： nim博弈
本文介绍：ICG游戏的定义，常用术语，Nim 博弈的证明，SG函数的证明，应用

一. 参考文档

1. 论文Game Threory https://pan.baidu.com/s/11P_rF5ZO-FuTPiNtjxcBlw
2. 论文翻译 https://blog.csdn.net/strangedbly/article/details/51137432

二. 适用范围

适用于 Impartial Combinatorial Games
游戏的胜负仅仅取决于当前状态, 与谁在玩没关系，即如果A在某个状态必赢，那么B在这个状态也必赢

1. 举例子

1. 取石子博弈 : 只与当前的状态有关，谁在必胜态，谁就赢
2. 非ICG，象棋，棋盘上相同的状态（所有的棋子的摆放地点都相同），但是下象棋的人控制的棋子不一样
   在论文中提出了六条判定是ICG的准则

2. 判定是ICG

1. 两个人
2. 当前状态的下一个状态的个数是有限的
3. 对于每一个状态，两个人的能够做的操作的集合是相同的
4. 交替移动
5. 一个人不能移动，就判定为输
6. 游戏会在有限步内终止

三一些术语

1 状态

必胜态： 当前将要移动的人必胜的状态
必输态： 当前将要移动的人必输的状态
结束态： 即当前人不能移动，是必败态
它们有以下关系：
也称为 特性：

• 每一个必胜态的能够转移的状态里面必定有一个必输态
• 每一比必败态的能够转移的状态里面必定都是必胜态
• 每一个结束态都是必败态

2 游戏

1. 减法游戏
   现在有一堆石子，Alice和Bob玩游戏，轮流取石子，每次可以取走 $a_1,a_2,...a_n$a1​,a2​,...an​个石子，最后不能取的人输。
   做法: 从0 开始递推必败态和必胜态
   论文中还给出了其它有趣的游戏，可以自己去看

四 Nim 游戏

游戏描述：

有N堆石子 $a_0,a_1...a_n$a0​,a1​...an​。A B两个人轮流拿，A先拿。每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N及每堆石子的数量，问最后谁能赢得比赛。
例如：3堆石子，每堆1颗。A拿1颗，B拿1颗，此时还剩1堆，所以A可以拿到最后1颗石子

策略

所有石子的异或和为Nim_sum

1. 如果NIm_sum = 0 ，那么先手必输,即必败态
2. 如果Nim_sum != 0,那么先手必赢，即必胜态

证明

1. $(0,0,0,0,...)$(0,0,0,0,...) 是结束态，也是必败态， $Nimsum=0$Nimsum=0

2. 所有的比胜态的下面状态必定有一个是必输态
   即 Nim_sum != 0,令 $2^k\&lt;=Nimsum\&lt;2^{k+1}$2k<=Nimsum<2k+1，那么必定有一个堆在二进制表示的第k+1位为1，假设 $a_i$ai​,于是我们有 $a_i\oplus Nimsum\&lt;a_i$ai​⊕Nimsum<ai​ ,从中取出 $a_i-a_i\oplus Nimsum$ai​−ai​⊕Nimsum个石子,使得 $a_0\oplus a_1\oplus ...a_i^{\prime }...\oplus a_n=0$a0​⊕a1​⊕...ai′​...⊕an​=0

3. 所有的必败态(除了终止态)的下面所有状态都是必胜态,Nim_sum = 0,
   反证法：我们选择任意一个堆取任意石子剩下 $a_i^{\prime }$ai′​ 个石子， $a_1\oplus a_2...a_i^{\prime }...\oplus a_n=a_1\oplus a_2...a_i...\oplus a_n$a1​⊕a2​...ai′​...⊕an​=a1​⊕a2​...ai​...⊕an​，必有 $a_i=a_i^{\prime }$ai​=ai′​,不移动任何石子这种情况是不被允许的，Nim_sum = 0的下一个状态必定是Nim_sum != 0

五 SG函数和SG定理

1 The Sprague-Grundy Function.

1. 定义 $g\left(x\right)=min\{n\ge 0:n=g(y)y\in F(x\left)\right\}.\left(1\right)$g(x)=min{n≥0:n=g(y)y∈F(x)}.(1)
   其中g(x)表示x这个状态的SG函数值,F(x) 代表x所有的下一个状态的集合
2. 我们定义一个minimal excludant（mex）函数代表不再一个集合里面的最小非负整数，上面的公式可以改写为
   $g\left(x\right)=mex\left\{g\right(y):y\in F(x\left)\right\}.\left(2\right)$g(x)=mex{g(y):y∈F(x)}.(2)
3. 对于终止态，g(x) = 0,因为F(x) 为空, 其他都可以通过这个公式来求
   满足特性:
   (1)如果是终止态，那么 $g\left(x\right)=0;$g(x)=0;
   (2) 每一比必败态的能够转移的状态里面必定都是必胜态,即如果g(x) = 0,那么他所有的子状态的 $g\left(y\right)!=0$g(y)!=0,如果有g(y) = 0,那么g(x) 的值就不会为0了
   (3) 每一个必胜态的能够转移的状态里面必定有一个必输态,如果g(x) != 0,那么肯定有一个子状态 $g\left(y\right)=0$g(y)=0,如果没有g(y) = 0,那么g(x) 就不会为非0了
   SG函数值的意义，如果g(x) = 0，那么x是必败态，如果g(x) != 0,那么x是必胜态

2 The Sprague-Grundy Theorem

如果可以将游戏拆成n个不相关的子游戏，在每一步中你可以选择在一个子游戏中操作，那么有 $g(x_1,x_2...x_n)=g_1\left(x_1\right)\oplus g_2\left(x_2\right)\oplus ....\oplus g_n\left(x_n\right)$g(x1​,x2​...xn​)=g1​(x1​)⊕g2​(x2​)⊕....⊕gn​(xn​)
证明如下:
令 $x=(x_1,x_2...x_n)$x=(x1​,x2​...xn​)（向量表示状态）x的子状态 $x^{\prime }=(x_1,x_2,x_i^{\prime },...x_n)i\in \{1,..n\}$x′=(x1​,x2​,xi′​,...xn​)i∈{1,..n}
$b=g_1\left(x_1\right)\oplus g_2\left(x_2\right)\cdot \cdot \cdot \oplus g_n\left(x_n\right)$b=g1​(x1​)⊕g2​(x2​)⋅⋅⋅⊕gn​(xn​)
证明以下两条：
初始条件 :
有 $0=0\oplus 0\oplus \mathrm{0...}\oplus 0$0=0⊕0⊕0...⊕0，所有的子游戏都结束的时候游戏就结束了，此时为必败态,g(x) = 0

(1) 对于所有 非负整数a < b,必定有一个状态 $x^{\prime }使得g\left(x^{\prime }\right)=ai\in \{1,..n\}$x′使得g(x′)=ai∈{1,..n}
(2) 没有一个x的子状态 $x^{\prime }$x′使得 $g\left(x^{\prime }\right)=b$g(x′)=b

(1) : 令 $d=a\oplus b$d=a⊕b,令 $2^k\&lt;=d\&lt;2^{k+1}$2k<=d<2k+1，我们有a在第k+1位为0，b在第k+1位为1，那么必定有一个 $g_i\left(x_i\right)$gi​(xi​)在二进制表示的第k+1位为1， $g_i\left(x_i\right)\oplus d\&lt;g_i\left(x_i\right)$gi​(xi​)⊕d<gi​(xi​),所以必定有 $g_i\left(x_i^{\prime }\right)=d\oplus g_i\left(x_i\right)$gi​(xi′​)=d⊕gi​(xi​), $a=b\oplus d=g_1\left(x_1\right)\oplus g_2\left(x_2\right)\cdot \cdot \cdot \oplus g_n\left(x_n\right)\oplus d=g_1\left(x_1\right)\oplus g_2\left(x_2\right)\cdot \cdot \cdot \oplus g_i\left(x_i^{\prime }\right)...\oplus g_n\left(x_n\right)$a=b⊕d=g1​(x1​)⊕g2​(x2​)⋅⋅⋅⊕gn​(xn​)⊕d=g1​(x1​)⊕g2​(x2​)⋅⋅⋅⊕gi​(xi′​)...⊕gn​(xn​)
即存在 x’ 使得 g(x’） = a
(2): $b=g_1\left(x_1\right)\oplus g_2\left(x_2\right)...g_i\left(x_i\right)...\oplus g_n\left(x_n\right)$b=g1​(x1​)⊕g2​(x2​)...gi​(xi​)...⊕gn​(xn​) , $a=g_1\left(x_1\right)\oplus g_2\left(x_2\right)..g_i\left(x_i^{\prime }\right)\cdot \cdot \cdot \oplus g_n\left(x_n\right)$a=g1​(x1​)⊕g2​(x2​)..gi​(xi′​)⋅⋅⋅⊕gn​(xn​)
a = b,则必有 $g_i\left(x_i\right)=g_i\left(x_i^{\prime }\right)$gi​(xi​)=gi​(xi′​) ，即不做改动，这是不被允许的

于是问题得证

六 常见博弈

(1）Nim 博弈

题意：两个人玩取石子游戏，共有N堆石子，每个人每次可以从一堆石子里面任意多个石子，不能取的人输
题解: 求所有堆石子数的异或和，异或和为零先手必输，异或和不为零，先手必败
发散思维: HDU1850,题目同上，不过这次询问的是先手必胜的情况下有多少种选择？
解析： 本题告诉我们不能光记住公式，还要记住公式的推导过程，在Nim的证明中，我们选取在sumxor 最高位处有1的作证明一定存在a[i]^sumxor = a[i]< a[i]，然后取出a[i] - a[i]个石子,本题就是计算sumxor ^a[i] < a[i] 的个数

（2）反Nim 博弈

题意: 题目同上，最后一个取的人输
解析： 必胜态 1. 如果所有的石子堆的个数都为1，sumxor 为偶数
2. 如果有一个不为1，那么sumxor 不为 0

（3）Moore’s Nimk

题意：两个人玩取石子游戏，共有N堆石子，每个人每次可以从k堆石子里面任意多个石子，不能取的人输
题解: 把n堆石子的石子数用二进制表示，统计每个二进制位上1的个数，若每一位上1的个数mod(k+1)全部为0，则必败，否则必胜。

（4）威佐夫博弈

题意：两个人玩取石子游戏，共有2堆石子，每个人可以选择从一堆石子里面取石子，也可以选择从两堆石子里面取相同数量的石子
结论： 第k个必败态 (a,a+k) a = (1+sqrt(5))/2*k,怎么判断当前是不是必败态呢，做差求出k然后判断就行了
核心代码:

    int a,b;
   while(cin>>a>>b){
   	if(a > b)  swap(a,b);
   	int   c = floor((b-a)*((1.0+sqrt(5.0))/2.0));
   	if(a == c)  cout<<0<<endl;
   	else        cout<<1<<endl;
   }

（5） 阶梯博弈

题意: 共有n阶台阶，每个台阶上有a_i个石子，地面表示第0号阶梯。每次都可以将一个阶梯上的石子向其左侧移动任意个石子，没有可以移动的空间时（及所有石子都位于地面时）输。
结论： 必败态是全部的石子都在地面上，胜负只与奇数台阶上的石子数有关，是它们石子数的异或和，同Nim博弈一样，如果异或和不为零，先手必胜，否则先手必败
简单证明： 考虑奇数Nim_sum != 0,那么你一定可以找到一种方法，使得奇数台阶的异或和为零，必败态也是异或和为零。 如果Nim_sum == 0,无论你怎么移动奇数的棋子，都不可能使得Nim_sum 为零，如果你移动偶数台阶的棋子，你的对手可以将你移动的棋子再移到奇数台阶上，Nim_sum 依旧为零.
例题：HDU - 3389

七 例题

1. Euclid’s Game HDU - 1525
   • 如果A<B，交换A,B
   • 如果 A%B == 0,那么先手必胜
   • 如果 A >= 2B ，考虑下一个状态，如果 (A%B,B) 是必败态，就转移到这个状态，否则转移到 （A%B+B,B）
   • B< A< 2B,只能转移到(A-B,B) 取决于(A-B,B) 的状态
2. HDU - 1525
   找规律就行了
3. A Multiplication Game HDU - 1517
   利用SG函数打表找规律

const int maxn  = 100000;
int dp[maxn];
int main(void)
{
   // cout<<sqrt(52488)<<endl;
   // dp[0] = 0;
   // dp[1] = 0;
   // rep(i,2,maxn){
   //    set<int> se;
   //    for(int j = 2;j < 10&&j <= i; ++j)
   //      {
   //       // if(i == 10)
   //       //    cout<<j<<" "<<dp[i/j+(i%j == 0?0:1)]<<endl;
   //        se.insert(dp[i/j+((i%j == 0)?0:1)]);
   //      }
   //    int count = 0;
   //    while(se.count(count)) count++;
   //    dp[i] = count;
   // }
   // cout<<dp[0]<<" "<<dp[0]<<endl;
   // rep(i,0,maxn)
   //    // printf("%d %d\n",i+1,dp[i+1]);
   //    dp[i] == dp[i+1] ? 1:printf("%d %d\n",i,dp[i]);


   LL n;
   while(cin>>n){
      while(n >= 18) n = (n-1)/18+1;
      if(n < 2||n > 9) puts("Ollie wins.");
      else      puts("Stan wins.");
   }
   return 0;
}