ACM博弈-I 平等博弈 SG函数的证明

博弈论

ACM博弈-II不平等博弈

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

一. 参考文档

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

二. 适用范围

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

1. 举例子

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

2. 判定是ICG

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

三一些术语

1 状态

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

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

2 游戏

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

四 Nim 游戏

游戏描述：

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

策略

所有石子的异或和为Nim_sum

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

证明

$(0, 0, 0, 0, . . .)$ 是结束态，也是必败态， $N i m s u m = 0$
所有的比胜态的下面状态必定有一个是必输态
即 Nim_sum != 0,令 $2^{k} < = N i m s u m < 2^{k + 1}$ ，那么必定有一个堆在二进制表示的第k+1位为1，假设 $a_{i}$ ,于是我们有 $a_{i} \oplus N i m s u m < a_{i}$ ,从中取出 $a_{i} - a_{i} \oplus N i m s u m$ 个石子,使得 $a_{0} \oplus a_{1} \oplus . . . a_{i}^{'} . . . \oplus a_{n} = 0$
所有的必败态(除了终止态)的下面所有状态都是必胜态,Nim_sum = 0,
反证法：我们选择任意一个堆取任意石子剩下 $a_{i}^{'}$ 个石子， $a_{1} \oplus a_{2} . . . a_{i}^{'} . . . \oplus a_{n} = a_{1} \oplus a_{2} . . . a_{i} . . . \oplus a_{n}$ ，必有 $a_{i} = a_{i}^{'}$ ,不移动任何石子这种情况是不被允许的，Nim_sum = 0的下一个状态必定是Nim_sum != 0

五 SG函数和SG定理

1 The Sprague-Grundy Function.

定义 $g (x) = m i n {n \geq 0 : n = g (y) y \in F (x)} . (1)$
其中g(x)表示x这个状态的SG函数值,F(x) 代表x所有的下一个状态的集合
我们定义一个minimal excludant（mex）函数代表不再一个集合里面的最小非负整数，上面的公式可以改写为
$g (x) = m e x {g (y) : y \in F (x)} . (2)$
对于终止态，g(x) = 0,因为F(x) 为空, 其他都可以通过这个公式来求
满足特性:
(1)如果是终止态，那么 $g (x) = 0;$
(2) 每一比必败态的能够转移的状态里面必定都是必胜态,即如果g(x) = 0,那么他所有的子状态的 $g (y)! = 0$ ,如果有g(y) = 0,那么g(x) 的值就不会为0了
(3) 每一个必胜态的能够转移的状态里面必定有一个必输态,如果g(x) != 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} (x_{1}) \oplus g_{2} (x_{2}) \oplus . . . . \oplus g_{n} (x_{n})$
证明如下:
令 $x = (x_{1}, x_{2} . . . x_{n})$ （向量表示状态）x的子状态 $x^{'} = (x_{1}, x_{2}, x_{i}^{'}, . . . x_{n}) i \in {1, . . n}$
$b = g_{1} (x_{1}) \oplus g_{2} (x_{2}) \cdot \cdot \cdot \oplus g_{n} (x_{n})$
证明以下两条：
初始条件 :
有 $0 = 0 \oplus 0 \oplus 0... \oplus 0$ ，所有的子游戏都结束的时候游戏就结束了，此时为必败态,g(x) = 0

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

(1) : 令 $d = a \oplus b$ ,令 $2^{k} < = d < 2^{k + 1}$ ，我们有a在第k+1位为0，b在第k+1位为1，那么必定有一个 $g_{i} (x_{i})$ 在二进制表示的第k+1位为1， $g_{i} (x_{i}) \oplus d < g_{i} (x_{i})$ ,所以必定有 $g_{i} (x_{i}^{'}) = d \oplus g_{i} (x_{i})$ , $a = b \oplus d = g_{1} (x_{1}) \oplus g_{2} (x_{2}) \cdot \cdot \cdot \oplus g_{n} (x_{n}) \oplus d = g_{1} (x_{1}) \oplus g_{2} (x_{2}) \cdot \cdot \cdot \oplus g_{i} (x_{i}^{'}) . . . \oplus g_{n} (x_{n})$
即存在 x’ 使得 g(x’） = a
(2): $b = g_{1} (x_{1}) \oplus g_{2} (x_{2}) . . . g_{i} (x_{i}) . . . \oplus g_{n} (x_{n})$ , $a = g_{1} (x_{1}) \oplus g_{2} (x_{2}) . . g_{i} (x_{i}^{'}) \cdot \cdot \cdot \oplus g_{n} (x_{n})$
a = b,则必有 $g_{i} (x_{i}) = g_{i} (x_{i}^{'})$ ，即不做改动，这是不被允许的

于是问题得证

六常见博弈

(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

七例题

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) 的状态
HDU - 1525
找规律就行了
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;
}