1.nim博弈

规则

通常的nim游戏的定义是这样子的：有若干堆石子，每堆石子的数量都是有限的，Player1与Player2轮流移动这些石子，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

策略

定义P-position代表后手必胜的局面，N-position代表先手必胜的局面，对于一般的nim游戏有如下的必胜策略：
对于一个Nim游戏的局面(a1,a2,…,an)，它是P-position当且仅当a1^a2^…^an=0，其中^表示异或(xor)运算，$a_i$代表第i堆石子的个数。

2.K-nim博弈

规则

在一般的nim博弈的基础上增加一条限制：
P1与P2每次只能拿不超过K个石子

策略

将每堆石子数对$(K+1)$取模后，就可转化为一般的nim游戏

3.K-L-nim博弈

规则

在一般的nim博弈的基础上增加一条限制：
先手P1每次不能拿走k个石子(但可拿走多于或者少于k个石子)，后手P2不能拿走l个石子(但可拿走多于或者少于l个石子)，如果轮到某个人时所有的石子堆都已经被拿空了，则判负。

策略

先要了解下SG(Sprague-Grundy)函数的定义：

首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
这一步应该是非常简单的，就是定义了新的运算为mex。
对于任意状态 x ， 定义 SG(x) = mex(F)，其中F 是 x 后继状态的SG函数值的集合（就是上述mex中的数值）。最后返回值（也就是SG(X)）为0为必败点，不为零必胜点。
进一步解释一下F，就是题意中给出的可以移动的次数。举个例子来说，一堆石子，每次只能拿1，3，5，7个，那么S数组就是1，3，5，7。

  • K与L相等的情况
    对于石子数为$x$的单堆，其SG函数值为:
    $$
    G(x)=\begin{cases}
    \lfloor \frac{x}{2K} \rfloor K+(x\% 2K), & 0<=(x \% 2K)<=K-1 \\
    \lfloor \frac{x} {2K} \rfloor K+(x \% 2K)-K,& K<=(x \% 2K)<=2K-1
    \end{cases}
    $$
    对于任何一个状态$$S=(x_1,x_2,x_3,…,x_n)$$可将其看成是n个单堆的Nim博弈的结合,分别求出这n个单堆的SG函数值，再做异或运算，若得到的值为0，则初始状态$S$为P状态，否则为N状态。

  • K与L不相等的情况
    假设所有的x均大于$min(K,L)$,否则就变成了一般的nim博弈

    • 若K>L,则$S$为N状态
    • 若K<L,如果在P1走完第一步以后，剩余状态是在普通的nim博弈里的P态，并且$max(x_1,x_2,…,x_n)<K$，那么P1有必胜的策略,否则P2有必胜的策略。

详细证明过程：https://image.hanspub.org/Html/2-2620391_20583.htm

4.bash博弈

规则

总共n个物品，P1与P2轮流取，每个人每次都可以取走1~m个物品，取走最后一个物品的人胜利。

策略

若$n\%(m+1)==0$则起始状态为P状态，否则为N状态

5.bash博弈增强版

规则

在一般bash博弈的基础上增加一条限制：
给定数集$S$,每次可取的石子数必须满足$x\in S$

策略

通过计算初始状态的SG函数值求解

文章顺序有点问题，Bash应该放在nim前面会好些，另外提供一些补充内容的博客
https://www.cnblogs.com/nanjoqin/p/10211576.html

最后，关于SG函数的理解，P状态和N状态更严谨的定义为：

  1. 无法进行任何移动的局面（也就是terminal position）是P-position
  2. 能移动到P局面的局面即为N局面
  3. P局面只能移动到N局面(所有移动都导致N局面的局面为P局面)
    所有ICG(公平组合游戏，局面对操作集无影响的游戏)的模型都可转化为一个DAG，一个局面即为DAG中的一个点，所以求出这个DAG所有点的SG函数值即可知道博弈中任意一个局面是P局面还是N局面，判断标准为SG(x)=0则局面x为P局面，否则为N局面。

SG函数模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//f[N]:可改变当前状态的方式，N为方式的种类，f[N]要在getSG之前先预处理
//SG[]:0~n的SG函数值
//S[]:为x后继状态的集合
int f[N],SG[MAXN],S[MAXN];
void  getSG(int n){
    int i,j;
    memset(SG,0,sizeof(SG));
    //因为SG[0]始终等于0，所以i从1开始
    for(i = 1; i <= n; i++){
        //每一次都要将上一状态 的 后继集合 重置
        memset(S,0,sizeof(S));
        for(j = 0; f[j] <= i && j <= N; j++)
            S[SG[i-f[j]]] = 1;  //将后继状态的SG函数值进行标记
        for(j = 0;; j++) if(!S[j]){   //查询当前后继状态SG值中最小的非零值
            SG[i] = j;
            break;
        }
    }
}