巴什博弈

1。问题背景

在我们日常生活中，博弈问题很常见，这不，最近就发现一个有趣的博弈问题。

桌子上有一堆石头。你和朋友开始轮流取石头，你作为先手先取。每一回合，轮到的人可以取 1 - 3 块石头。我们约定取到最后一块石头的人就是获胜者。假设你们每一步都是最优解，即每一步都是为自己可以获胜而取特定块回头。假设这堆石头有 23 块，问最后谁可以获胜？

2。分析归纳

这个问题乍一看有点懵，不知道怎么去分析。我们先可以使用数学归纳法，从特殊个例向通用规律靠拢。

1. n=1 时，肯定是先手者获胜
2. n=4 时，肯定是后手者获胜，因为先手的人最多可以取 3 块石头，后手者接下来可以一次性取完所有
3. n=8 时，可重复步骤 2，肯定是，后手者获胜，因为无论先手者取 n (1≤n≤3) 块，后手者都可以取 4 - n 块，从而可以确保后手者取到最后一块石头
4. n=16 时，可以重复步骤 3，同样是后手者获胜

通过以上规律，我们不难发现，如果堆石头的总数 n 可以被 4 整除，则一定是后手者取胜，相反，就是先手者获胜。至此这个问题我们算是解决了。

3。通用规律

但是如果同样的游戏，游戏规则从可以取 1 - 3 块石头变为 1-20 块石头，我们怎么去推断最后的获胜者是谁呢？

其实这类问题属于博弈论的一部分，我们可以把它称作**巴什博弈**。在先取完者胜的巴什博弈中，我们规定可取的总个数为 n，每次最多可以取的个数是 m。若 n 可被 m+1 整除，则后手方必胜，否则先手方必胜。(游戏的前提是游戏双方每次都是取最优解)

4。题目示例

掌握了巴什博弈的规律。接下来我们可以看一道简单的题目 👉 Leetcode 链接-292

你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头。你们轮流进行自己的回合，你作为先手。每一回合，轮到的人拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false。

4.1 主要思路

根据巴什博弈规律：在先取完者胜的巴什博弈中，若 n 可被 m+1 整除，则后手方必胜，否则先手方必胜

4.2 游戏过程

原始先手只需要确保每次都选择 x % 4 个石子 (x 为当前石子数量)，就可以确保交由自己的局面一直满足 x % 4 != 0，交由对方的局面一直满足 x % 4 == 0，直到最后回合的到来。

4.3 题目解法

function canWinNim(n: number): boolean {
    return (n % 4) !== 0
};

总结

简单总结一下，本文我们主要介绍了**巴什博弈**问题的背景，通过数学归纳法，从特殊规律到一般规律：在先取完者胜的巴什博弈中，我们规定可取的总个数为 n，每次最多可以取的个数是 m。若 n 可被 m+1 整除，则后手方必胜，否则先手方必胜。最后我们应用该规律解决了一道简单的 👉 Leetcode 链接-292 题目。当然，博弈论下有很多涉及系统性的问题，感兴趣的朋友可以自己探索。

结尾处，我们推荐一部好看的电影美丽心灵，它和博弈论中的经典问题纳什均衡相关。