博弈论

概念讲解

Nim 游戏

n 堆石子，两人轮流取，每次从一堆中取任意个，取完者胜。

结论

先手必败 当且仅当 a1⊕a2⊕⋯⊕an=0a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0

SG 函数

定义

SG(x)=mexSG(y)∣y 是 x 的后继状态SG(x) = \text{mex}{SG(y) | y \text{ 是 } x \text{ 的后继状态}}

mex：最小的不属于集合的非负整数。

Sprague-Grundy 定理

多个独立游戏的 SG 值的异或和 = 合并游戏的 SG 值。

考点分析

初赛考查方式

  1. 选择题： Nim 游戏
  2. 编程题： 博弈问题

常见考点

  • Nim 游戏结论
  • SG 函数
  • 异或性质

例题精讲

例题 1：Nim 游戏

题目： 三堆石子 {3, 5, 7}，先手是否必胜？

解答：

3⊕5⊕7=1≠03 \oplus 5 \oplus 7 = 1 \neq 0，先手必胜。

练习题

  1. Nim 游戏先手必败的条件？
查看答案

Nim 游戏先手必败的条件：所有堆石子数的异或和为 0

a1⊕a2⊕⋯⊕an=0a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0

如果异或和不为 0，先手必胜。

  1. SG 函数的定义？
查看答案

SG 函数的定义：

SG(x)=mexSG(y)∣y 是 x 的后继状态SG(x) = \text{mex}{SG(y) | y \text{ 是 } x \text{ 的后继状态}}

其中 mex\text{mex} 表示最小的不属于集合的非负整数。

例如：mex0,1,3=2\text{mex}{0, 1, 3} = 2

  1. Sprague-Grundy 定理的内容？
查看答案

Sprague-Grundy 定理：

多个独立游戏的 SG 值的异或和 = 合并游戏的 SG 值

SG(G1⊕G2⊕⋯⊕Gn)=SG(G1)⊕SG(G2)⊕⋯⊕SG(Gn)SG(G_1 \oplus G_2 \oplus \cdots \oplus G_n) = SG(G_1) \oplus SG(G_2) \oplus \cdots \oplus SG(G_n)

易错点

⚠️ 注意：

  1. 异或和为 0 先手必败
  2. SG 函数用 mex 计算
  3. 多游戏合并用异或
  4. 博弈论是高级内容