noone___'s blog
0%

博弈论

发表于 更新于 分类于
博弈论及其变形

博弈论游戏及其的变形

请熟背以下结论（因为没看懂推导）

巴什博弈

规则

  • 只有一堆 $n$ 个物品，两个人轮流取
  • 每次至少取一个，最多取 $m$ 个。
  • 最后取光者得胜

结论

$n \mod (m+1)$ 为 $0$ 先手必败否则必胜

威佐夫博弈

规则

  • 有两堆各若干个物品
  • 两个人轮流从某一堆取至少一个或同时从两堆中取同样多的物品
  • 最后取光者得胜

结论

先手必败态的两堆石子之差依次递增，且每个自然数仅出现一次

如果局势为 $(a,b)$，记 $k=(a−b)$，

若 $a=\frac{1+\sqrt{5}}{2}*k$ （这里是等于符号）

则为必胜局势

尼姆博弈

规 则

  • $n$ 堆石子
  • 两人轮流在任意一堆中取任意石子，不能不取，最多取完，
  • 取到最后一颗石子者胜

结论

$n$ 堆石子数量异或和为 $0$ 则先手必败,否则必胜

anti-SG与SJ（贾志豪）定理

规则

  • 桌子上有 $n$ 堆石子，游戏者轮流取石子。

  • 每次只能从一堆中取出任意数目的石子，但不能不取。

  • 取走最后一个石子者败。

结论

先手必胜当且仅当：

  1. 所有堆的石子数都为 $1$ 且游戏的 SG 值为 $0$；

  2. 有些堆的石子数大于 $1$ 且游戏的 SG 值不为 $0$。

1
2
3
4
5
6
7
8
9
scanf("%d",&n);
while(n--){
        scanf("%d",&tmp);
        if(tmp>=2) flag=1;
        ans^=tmp;
    }
if((ans&&flag) || (!ans&&!flag))
    puts("John");
else puts("Brother");

例题

P4279 [SHOI2008]小约翰的游戏

UVA1566 John(双倍经验)

multi-SG

规则

  • 有 $n$ 堆石子
  • 可以从任意一堆石子中拿任意石子(不能不拿)
  • 或者把一堆数量不少于 $2$ 石子分为两堆不为空的石子。

结论

$SG\left(x\right) =
\begin{cases}
x-1 & ( x \mod 4=0)
\\ x & ( x \mod 4=1 \lor 2)
\\ x+1 & ( x \mod 4=3)
\end{cases}$

注：$1 \lor 2$ -> $1$ || $2$

对这个结论我有绝佳的证明，但我要去玩DDLC了

Update:更好看且对齐的Latex

例题

P3185 [HNOI2007]分裂游戏 (关系并不大的样子)

P3235 [HNOI2014]江南乐 (未做qwq) (现在做过了qwq)

阶梯SG

规则

  • 有若干级阶梯，每级阶梯上有一个单个游戏
  • 每次可以对一个阶梯操作并将操作中失去的东西丢到下一级阶梯上。

应用范围

对于单个游戏状态，若操作集合可逆（即上一级丢给这级的东西在这级可以再丢掉），则可以应用。

结论

令最低级阶梯为第 $0$ 级，对奇数级阶梯上的游戏 SG 值取异或和，为 $0$ 先手必败，否则先手必胜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
rei sg=0/*本行sg值*/,tot=0/*连续石头的个数*/;
memset(st,0,sizeof st);

scanf("%d",&m);
rei C=20-m+1;//空格个数
for(rei i=1;i<=m;++i) scanf("%d",&x),st[x]=true;
    for(rei i=1;i<=20;++i){
        if(!st[i]){//石头不再连续
            if((--C)&1) sg^=tot;//奇数行
            tot=0;
        }
        else
            ++tot;
}
ans^=sg;

例题

P2575 高手过招

P3480 [POI2009]KAM-Pebbles 需要一些转化技巧

k-SG

规则

  • 有 $n$ 堆石子
  • 每次可以从不超过 $k$ 堆中按规定规则各取一些石子
  • 不能操作者败。

结论

将每堆石子的 SG 值设为 $s_i$ 。

将所有 $s_i$ 二进制第 $j$ 位上的数相加得到 $r_1,r_2,\dots,r_J$（ $J$ 为所有 $s_i$ 二进制最高位的位数）

如果 $\forall i \in [1,J]$ 有 $r_i \equiv 0\pmod{k+1}$ ，那么先手必败；否则先手必胜。

1
2
3
4
5
6
for(rei i=0;i<=16;++i)
    for(rei j=0;j<=n-k;++j)//能使用的最多石子
        for(rei x=0; (1ll<<i)*x*(d+1) <= n-k /*所取的石子不多于题目限制*/&&/*所取的石子不多于总堆数 -> 每堆每次只能减1*/ x*(d+1) <= k/2; ++x)
        //从k/2个堆中选出x*(d+1)个，使其石子数二进制在i位为1
        //贡献的方案数为C[k/2][x*(d+1)]
            dp[i+1][ j+ (1ll<<i)*x*(d+1) ] = (dp[i+1][ j+ (1ll<<i)*x*(d+1) ] + 1ll*dp[i][j]*C[k/2][x*(d+1)]%mod )%mod;

例题

P2490 [SDOI2011]黑白棋

翻棋子游戏

规则

  • 在一些棋子中，有的正面朝上，有的反面朝上
  • 每次操作可以翻其中一颗正面朝上的棋子，会带动一些其他棋子的组合翻面。

结论

局面的 SG 值为局面中每个正面朝上的棋子单一存在时的 SG 值的异或和。

具体问题具体分析吧qwq

将 每颗棋子翻面后可能影响的棋子组成的游戏 作为一个后继状态，
对每颗棋子求 SG 值，然后求所有正面朝上的棋子 SG 值的异或和，为 $0$ 先手必败，否则先手必胜

例题

P3179 [HAOI2015]数组游戏 （需要数论芝士，未做qwq）

P4077 [SDOI2016]硬币游戏

斐波那契博弈

规则

  • 两人互相取一堆石子，取完者胜

  • 第一次不能取完,至少取 $1$ 颗

  • 从第二次开始,每个人取的石子数至少为1,至多为对手刚取的石子数的 $2$ 倍。

结论

当 $n$ 为 $\text{fibonacci}$ 数时，先手必败

证明

  • 先考虑 $n$ 为斐波那契数 $f_i$

    • 当 $i=2,n=2$ 显然有 先手必败

    • 设当 $i<=k$ 时结论成立

      当 $i=k+1 , f_i=f_k+f_{k-1}$ ,一定可以将这堆石子看成两堆：$k-1,k$，因为 $2\times f_{k-1}>f_k$ ,若 $\geq f_{k-1}$ 则后手可以直接取完 $f_k$ ； 若先手第一次取得石子 $<f_{k-1}$，则后手一定最后取，考虑后手最多取石子 $x$ 个：

      那么先手应取尽可能多的石子，来使后手取更多的石子，再在后手取完 $堆k-1$ 后，能使先手取完 $堆k$

      那么让先手取 $y\geq \frac{f_{k-1}}{3}$，此时后手可以直接取完 $堆k-1$，$\therefore x=f_{k-1}-y\leq \frac{2}{3}\times f_{k-1}$

      易知 $\frac{2}{3}\times f_{k-1}<\frac{1}{2}\times f_k$ ,即，后手取完 $堆k-1$ 后，先手不能一次取完 $堆k$，则 $i=k+1$ 时，结论仍成立

  • 再考虑 $n$ 不为斐波那契数

    • 齐肯多夫定理：

      任何正整数可以表示为若干个\不连续**的 $\text{fibonacci}$ 数之和 \（优先选取最大的）**

    由于对每次取石子的最少数量没有限制，所以可以将 $n$ 按照以上定理拆成多组，每组是一个斐波那契数，并把该拿的一堆石子转化为拿多组石子

    由于所取的数不连续，所以有 $f_{i}>2\times f_{i-1}$

​ 令先手先取完 $i$ 最小的 $f_i$ ,此时后手不能取完 $f_{i+1} 这一堆$，相当于面临子游戏，且为必败态(有 $f_{i+1}$ 个，且后手先取)，则先手必胜

​ 以此类推，先手必胜