【算法】经典博弈论问题①——巴什博弈 python

前言

博弈类问题大致分为：
公平组合游戏、非公平组合游戏（绝大多数的棋类游戏）和 反常游戏

巴什博弈(Bash Game)

一共有n颗石子，两个人轮流拿，每次可以拿1~m颗石子
最先取光石子的一方为胜（没有石子可以拿的人为败），根据n、m返回谁赢

分析：

我们从最简单的情景开始分析
当石子有 1−m 个时，先手必胜（一次拿完）
当石子有m+1个时，先手无论拿几个，后手都可以拿完，先手必败
不难发现：面临 m+1个石子的人一定失败。
这样的话，最优策略一定是：通过拿走石子，使得对方拿石子时还有 m+1个剩余

推广至一般情况：
【1】当n不可被m+1整除时，先手必胜
为什么？ n %（m+1）= r，先手拿走 r ，后手即面临 m+1的整数倍颗石子，必败
【2】同理，当n可被m+1整除时，先手必败

测试链接 hduoj1846

示例code：

c = int(input())
for _ in range(c):
    n, m = map(int, input().split())
    if n % (m + 1) == 0:
        print("second")
    else:
        print("first")

小试牛刀

hduoj2188

题解：

# 和前面几乎一样的code
c = int(input())
for _ in range(c):
    n, m = map(int, input().split())
    if n % (m + 1) != 0:
        print("Grass")
    else:
        print("Rabbit")

PN分析

实战检验

Roy&October之取石子

题目背景

Roy 和 October 两人在玩一个取石子的游戏。

题目描述

游戏规则是这样的：共有 $n$ 个石子，两人每次都只能取 $p^k$ 个（ $p$ 为质数，$k$ 为自然数，且 $p^k$ 小于等于当前剩余石子数），谁取走最后一个石子，谁就赢了。

现在 October 先取，问她有没有必胜策略。

若她有必胜策略，输出一行 October wins!；否则输出一行 Roy wins!。

输入格式

第一行一个正整数 $T$，表示测试点组数。

第 $2$ 行$\sim$ 第 $T+1$ 行，一行一个正整数 $n$，表示石子个数。

输出格式

$T$ 行，每行分别为 October wins! 或 Roy wins!。

样例输入

3
4
9
14

样例输出

October wins!
October wins!
October wins!

提示

对于 $30\%$ 的数据，$1\le n\le 30$；

对于 $60\%$ 的数据，$1\le n\le 10^6$；

对于 $100\%$ 的数据，$1\le n\le 5\times 10^7$, $1\le T\le 10^5$。

（改编题）

思路：

每次可以拿质数的自然数次方颗石子
对于6的倍数，一定不是质数的某一自然数次方
1,2,3,4,5都可以一次取到，
当n=6时，第一个人无论怎么取，后手赢
推至一般情况：
当n不是6的倍数，先手赢
当n是6的倍数，后手赢

题解代码：

t = int(input())
for _ in range(t):
    n = int(input())
    if n % 6 == 0:
        print("Roy wins!")
    else:
        print("October wins!")

总结

巴什博弈是一个相对简单的问题，但它引入了重要的概念，比如P态和N态的概念，对理解更复杂的组合博弈非常有用。
此外，如何通过数学公式快速得出结论也是解决此类问题的关键技巧之一。

如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢