回合制博弈

策梅洛定理(Zermelo's theorem)

In game theory, Zermelo's theorem is a theorem about finite two-person games of perfect information (opens new window) in which the players move alternately and in which chance does not affect the decision making process. It says that if the game cannot end in a draw, then one of the two players must have a winning strategy (i.e. force a win). An alternate statement is that for a game meeting all of these conditions except the condition that a draw is not possible, then either the first-player can force a win, or the second-player can force a win, or both players can force a draw

如果满足以下条件

1. 两人(A、B)博弈，交替执子（回合制）

2. 有限回合

3. 信息完备

4. 不受随机性影响

那么，要么玩家A有必胜策略，要么玩家B有必胜策略，要么A、B都有必定平局的策略

如果满足

5. 没有平局

那么，任意一方有必胜策略。

Nim(SG函数)

假设有$n$个石子，$A、B$在游戏时轮流取走$k\in S=\{p_1,p_2,\dots,p_n\}$个石子，无法取得石子者败（Nim）。

定义$f(u)=mex\{f(v)\mid e(u,v)\in E\}$，其中$e(u,v)$代表从$u$状态可以转移到$v$状态，$mex(V)$代表不属于集合$V$的最小非负整数。

那么$f(x)=0$的为必败状态，$f(x)\ne 0$的为必胜状态。

---

容易注意到，$SG$函数$f(x)$中只考虑了$[0, f(x)-1]$的状态，那么那些$[f(x)+1,+\infty]$中的可行状态呢？

假设当前状态$SG$值为$val_0$，先手玩家将其转移为$val_1\quad(val_1>val_0)$。那么根据$SG$函数的定义，后手玩家总可以转移到一个新状态，使得$val_2=val_0$，在有限步数的情况下，必胜/必败情况不变（多堆石子时也是如此）

---

若有多堆石子$x_1,x_2,\dots,x_n$，可以视为多个游戏，其中每个游戏分别的$SG$函数$f(x_i)=r_i$，那么整局游戏的$SG$函数则为$r_1\oplus r_2\dots\oplus r_n$

简要证明如下：

1. 假设当前的状态为$St=r_1\oplus r_2\dots\oplus r_n=0$，玩家必须改变某一$r_i(i\in[1,n])$，则必然使得下一状态$St'=r'_1\oplus r'_2\dots\oplus r'_n\ne 0$（反证法可证）。

2. 假设当前状态$St\ne 0$，下面将证明必定存在一操作使得下一状态$St'=0$

   1. 记$St$的二进制最高位位置为$p$
   2. 在$r_i$中找到任意一个二进制第$p$位为1的值，记为$r_s$
   3. 将$r_s$第$p$位置0，低$p$位与$St$相同，其余位不变，得到$r'_s<r_s$
   4. 新的状态$St'=r_1\oplus r_2\dots r_{s-1}\oplus r_{s+1}\dots\oplus r_n\oplus r'_s=0$

这就说明了，最优策略下，$St=0$的状态必将走向$St\ne0$的状态，$St\ne0$的状态必将走向$St=0$的状态。

NimK

有$n$堆石子，每堆有$x_i$个。玩家每次可以选择不超过$k$堆石子，并从选中的堆中取出任意数量($\ge1$)的石子；无法取得石子者败。Nim可以看作是NimK的特例($k=1$)。

设每堆的$SG$函数分别为$r_1,r_2,\dots,r_n$，将$r_i$的二进制表示按位相加（但不进位，每位分别对2取余）后对$(k+1)$取余得到$St$。先手必胜的$St\ne0$。

证明如下：

1. 如果$St=0$，由于选择的堆数不超过$k$，根据$St$的定义，$St'\ne0$

2. 如果$St\ne0$，下面将证明必定存在一种操作使得下一状态$St'=0$

   初始时，所有$r_i$均未被标记，记$cnt_0[i],cnt_1[i]$分别为二进制第$i$位为$0/1$且被标记的数之个数

   1. 记$St$的二进制最高位位置为$p$
   2. 找到任意一个二进制第$p$位为1且未被标记的值$r_s$
   3. 将$r_i$的第$p$位置0，$[1,p-1]$位则根据该位的值，更新$cnt_0/cnt_1$，其余位忽略
   4. 更新后，若$St'\ne0$，记$St'_i\ne0$（第$i$位非零）。如果$St'_i+cnt_0[i]\ge(k+1)$或$St'_i-cnt_1[i]\le0$(当$cnt_0[i]+cnt_1[i]=k$时，两者至少有一个成立)，则可以通过修改已经标记的$r$，使得$St'_i=0$，置$St_i'=0$
   5. 如果经过步骤$4$后$St'\ne0$，则回到步骤$1$

   最终，$St'=0$且选取的堆数$\le k$

NimK例题 POJ 2315

AC代码

#include <iostream>
#include <cstring>
#include <cmath>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)

using namespace std;

const double PI = acos(-1);
int n, m, l, r;
int sg[50], bit_cnt[33];

void table(){ // 打表函数
    const int len = 50;
    int table_sg[len];
    bool appear[len];
    for(int k=1; k < 10; k++){
        cerr << "\n----------\n";
        table_sg[0] = 0;
        for(int i=1; i<len; i++){
            memset(appear, 0, sizeof appear);
            for(int j=i-1; j>=0 && i-j<=k; j--)
                appear[table_sg[j]] = true;
            for(int j=0; j<len; j++) if(!appear[j]){
                table_sg[i] = j;
                break;
            }
        }
        for(int i=1; i<len; i++) cerr << table_sg[i] << " ";
    }
}

string solve(){
    memset(bit_cnt, 0, sizeof bit_cnt);
    double cir = 2 * PI * r; // 
    int max_k = l / cir;
    for(int i=1; i<=n; i++) {
        cin >> sg[i];
        sg[i] = ((int)ceil(sg[i] / cir)) % (max_k + 1); // 打表得出SG函数规律
        // 由于Pi是无理数(不能写作两整数之比)，因此可以把ceil换成+1
    }
    for(int i=1; i<=n; i++){
        for(int j=0; j<31; j++){
            if(sg[i] & (1<<j)) bit_cnt[j]++;
        }
    }
    for(int j=0; j<31; j++){
        if(bit_cnt[j] % (m + 1) != 0) return "Alice";
    }
    return "Bob";
}

signed main(){
    Android;
    while(cin >> n >> m >> l >> r) cout << solve() << '\n';
}

Anti-Nim

有$n$堆石子，每堆分别有$x_1,x_2,\dots,x_n$个，每次只能从一堆中取出任意数目的石子，取走最后一个石子者败。

显然对于单个堆，$SG(i)=x_i$，对于整局游戏，$SG=x1\oplus x_2\dots\oplus x_n$

先手必胜当且仅当：

1. 所有$x_i$都为$1$，且整局的$SG=0$
2. 存在$x_i\ne1$，且整局的$SG\ne0$

注意：我们规定，$SG=0$的局面不一定为必败局面

证明见 贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》

其他博弈模型

除了上述模型以外，还有许多博弈模型，如

• Every-SG
• 威佐夫博弈(Wythoff's game)
• Fibonacci Nim
• Staircase Nim
• 非回合制博弈

等等

参考

wiki-Zermelo's theorem (game theory) (opens new window)

10170 Sprague-Grundy定理是怎么想出来的 (opens new window)