15 博弈论入门 ★★☆☆☆

博弈论研究的是：在一个游戏中，进行游戏的多位玩家如何选择最优策略。本笔记整理博弈论的基本概念、分类，以及两类最经典的公平组合游戏——Bash 博弈和 Nim 游戏。

Tips：部分内容由 AI 生成，如发现问题请在评论区留言，保证AI贡献严格小于人类贡献。

一、概念

博弈论主要研究：在一个游戏中，进行游戏的多位玩家如何选择最优策略。

二、博弈论分类

1. 对称博弈 / 非对称博弈

• • 对称博弈：不同参与者在做出相同行为时获得的收益相同，收益与执行者的身份无关。
• • 否则称为非对称博弈。

2. 零和博弈 / 非零和博弈

• • 零和博弈：无论各方采取何种行为，所有参与者的收益总和始终为零，即一方的收益必然是另一方的损失。
• • 非零和博弈：允许多方共赢或共输。

3. 同时博弈 / 序贯博弈

• • 同时博弈：所有参与者在不知道他人选择的前提下同时决策，例如剪刀石头布。
• • 序贯博弈：参与者依次行动，后行动者至少能观察到先行动者的部分行为。

4. 完美信息博弈 / 不完美信息博弈

• • 完美信息博弈：参与者决策时，完全了解此前所有事件的发生情况，如象棋、围棋。
• • 不完美信息博弈：否则。如麻将、扑克——玩家无法获知他人的手牌。

5. 完全信息博弈 / 不完全信息博弈

• • 完全信息博弈：所有参与者对博弈结构本身有完全了解，且这些信息为公共的。
• • 不完全信息博弈：某些博弈要素对参与者未知，比如对方可以选择的决策集。

三、组合博弈论

特点：两个玩家轮流行动，双方都完全了解游戏的局面。所以组合博弈是完全信息博弈 + 序贯博弈，且没有随机因素。

公平组合游戏：

• • 是一种组合博弈；
• • 一个状态（局面）无法多次抵达（局面图无环）；
• • 博弈在一个玩家无法行动时结束；
• • 是对称博弈。

四、简单博弈题

• • P11072 Alice and Bob
• • P12951 [GCJ Farewell Round #2] Collecting Pancakes
• • P5804 [SEERC 2019] Absolute Game

五、常见博弈

① Bash 博弈

有一堆  个石子，两个绝世聪明之人轮流取石子，每次取的石子数不少于  颗、不多于  颗，谁先取完谁赢。

结论：若 ，后手必胜；否则先手必胜。

证明：

• • 若 ：先手先取  颗，使剩余为  的正整数倍。之后无论后手取 （）颗，先手都取  颗，始终保持剩余为  的倍数，最终先手取完获胜。
• • 若 ：后手套用同样策略，后手必胜。

例题：HDU4764

变种：

• • P10187 [USACO24FEB] Palindrome Game B：与 Bash 类似，只是每次取的石子数还必须是回文数（不含前导零）。易证非零个位数先手必胜、 时后手必胜，类推可得： 时后手必胜，否则先手必胜。
• • P8901 [USACO22DEC] Circular Barn S

② Nim 游戏

有  堆石子，第  堆有  个。两个绝世聪明之人轮流取，每次任选一堆，取走任意正整数颗（至少  颗，无上限），谁先取完谁赢。

结论：当

时先手必败，否则先手必胜（ 为按位异或）。

模板题：P2197 【模板】Nim 游戏（具体证明见对应题解专栏）。

在线模拟：https://numberduel.mathmindpuzzles.com/zh/games/nim/

六、结语

以上是博弈论入门的入门内容。更多游戏变体与 SG 函数 等，会在后续笔记中继续讲解。