发布时间：2024-08-16

博弈论

巴什博弈

两个顶尖聪明的人在玩游戏，有一堆n个石子，每次每个人能取[1,m]个石子，不能拿的人输，请问先手与后手谁必败？

结论：n能整除m+1时后手必败

Nim博弈

两个顶尖聪明的人在玩游戏，有n堆石子，第i堆有ai个，每人每次能从一堆石子中取任意多个石子但不能不取，不能拿的人输，请问先手与后手谁必胜？

结论：所有值异或起来为0先手必败，否则必胜

Nim-k游戏

n堆石子，每次从不超过k堆中取任意多个石子，最后不能取的人失败。

结论：把n堆石子的石子数用二进制表示，统计每个二进制位上1的个数，若每一位上1的个数mod(k+1)全部为0，则必败，否则必胜。

每一位最多改k次，然后第二个人该剩下k+1-x次即可

阶梯nim博弈

两个绝顶聪明的人在玩游戏，有n堆石子，每次每人可以取走第i堆(i>1)任意数量的石子并将它们放到第i-1堆，或者直接取走第一堆的任意数量石子，不能操作的人输，请问先手能否必胜？

对于这一类问题我们将堆的编号分奇偶考虑，如果只有奇数编号那些堆石子，这就是一个尼姆博弈。现在加入了偶数编号的堆，同样不影响答案，因为如果有人将偶数编号第i堆的石子移到第i-1堆，那么另一个人可以将上一个人操作的那些石子从第i-1堆再移到第i-2堆，这样奇数编号堆的局势没变，两人的先后手关系也没变，相当于将偶数堆编号的石子往前移了两次。而移动奇数堆到偶数堆就相当于拿走了石子。

那么为什么选择将奇数堆看做尼姆博弈而不是偶数堆呢？

因为虽然偶数堆做尼姆博弈也是相当于拿走石子，但最后石子会堆在第一堆，我们无法判断哪个人会在什么时候清空第一堆的石子

anti-nim(反nim游戏)

反nim游戏。正常的nim游戏是取走最后一颗的人获胜，而反nim游戏是取走最后一颗的人输。

一个状态为必胜态，当且仅当：

1）所有堆的石子个数为1，且NIM_sum=0

2）至少有一堆的石子个数大于1，且 NIM_sum≠0

void solve(){
    int n;
    cin>>n;
    int ans=0;
    bool g=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x>1)g=1;
        ans^=x;
    }
    if((g&&ans)||(!g&&!ans))cout<<"John\n";//必胜
    else cout<<"Brother\n";
}

威佐夫博弈

有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利

定义后手必胜为奇异局势

$k=y-x,第k个奇异局势为(\frac{1+ \sqrt 5}{2}k, \frac{3 + \sqrt 5}{2}k)$

拓展威佐夫博弈

按照上面在棋盘上移动棋子的方式，每次向左下移动可以看作是向左移动 $dx$ ,向下移动 $dy$，要求 $|dx-dy|<1$。那么如果将这个要求扩展到 $|dx-dy|< d$ 呢？我们同样可以得出第 $k$ 个奇异局势 $(x,y)$ 为前 $0-k-1$个奇异局势中没有出现过的最小自然数，$y=x+d-k$ 。根据Betty定理同样能得出第 $k$ 个奇异局势为 $( \frac {2-d+ \sqrt {d^2+4}}{2}k ,\frac{2+d+ \sqrt {d^2+4}}{2}k )$

给你两堆石子，每次可以单独拿一堆中的任意值，或者两堆都拿，但是两堆拿的值需满足 $|x-y|<=k$

本题就是拓展威佐夫博弈，d取k+1

void solve(){
    int a,b,K;
    cin>>a>>b>>K;
    int d=K+1;
    if(a<b)swap(a,b);
    int k=(a-b)/d;
    int x=(2+d+sqrt(d*d+4))/2*k,y=(2-d+sqrt(d*d+4))/2*k;
    if(x==a&&y==b)cout<<"0\n";
    else cout<<"1\n";
}

斐波那契博弈

两个顶尖聪明的人在玩游戏，有一堆石子，先手第一次可以拿任意多个但不能全拿走也不能不拿，之后每个人最少拿一个，最多拿前一个人两倍那么多个，谁取到最后一个谁就能获胜，请问先手后手谁必胜？

结论：当石子数为斐波那契数时先手必败，反之先手必胜。