第 93 课·数学算法高级

博弈论基础

game-theorynimgrundysg

第93课 - 博弈论基础

学习目标

  • 理解公平组合游戏（Impartial Game）的定义和基本要素
  • 掌握经典Nim游戏的必胜策略
  • 学习Sprague-Grundy（SG）函数的概念和计算方法
  • 能够运用SG定理解决组合游戏问题

核心概念

什么是博弈论？

想象两个聪明的小朋友在玩游戏，他们都想赢。博弈论就是研究这种“对抗性”决策问题的数学理论。在算法竞赛中，我们主要关注公平组合游戏，这类游戏有两个特点：

  1. 两人轮流行动，游戏状态对双方公开透明
  2. 有限步结束，不存在无限循环
  3. 完全公平：双方拥有的可行操作完全相同

Nim游戏：最简单的博弈模型

考虑这样一个游戏：有两堆石头，分别有3个和1个。两人轮流取石头，每次可以从任意一堆中取走任意多个（至少1个），最后取走所有石头的人获胜。

关键问题：给定初始状态，先手是否有必胜策略？

必胜策略的奥秘：异或运算

Nim游戏的必胜条件非常巧妙：

  • 将每堆石子的数量用二进制表示
  • 计算所有堆石子数量的异或和
  • 如果异或和不为0，先手必胜；如果为0，先手必败

为什么异或能解决问题？因为异或运算反映了二进制位的奇偶性。当异或和为0时，任何移动都会破坏这种平衡，使对手恢复优势。

SG函数：博弈论的通用武器

对于更复杂的游戏，我们需要更强大的工具——SG函数（Sprague-Grundy函数）。

SG函数的核心思想：

  1. 每个游戏状态对应一个SG值
  2. 终止状态的SG值为0
  3. 非终止状态的SG值 = 它的所有后继状态的SG值中，未出现的最小非负整数

这个定义看起来抽象，让我们用具体例子理解。

代码示例

例1：Nim游戏判断

def nim_game_winner(piles):
    """
    判断Nim游戏的胜者
    :param piles: 各堆石子的数量列表
    :return: 先手必胜返回True，必败返回False
    """
    xor_sum = 0
    for pile in piles:
        xor_sum ^= pile  # 计算异或和
    
    # 异或和不为0，先手必胜
    return xor_sum != 0

# 测试Nim游戏
piles = [3, 1]  # 两堆石子：3个和1个
if nim_game_winner(piles):
    print("先手必胜")
else:
    print("先手必败")

# 解释：3的二进制是11，1的二进制是01，异或结果是10（2），不为0
# 所以先手必胜

例2：计算SG函数

def sg_function(state, trans_table, graph):
    """
    计算状态的SG值
    :param state: 当前状态
    :param trans_table: 记忆化存储表（字典）
    :param graph: 状态转移图（邻接表）
    :return: 该状态的SG值
    """
    # 如果已经计算过，直接返回
    if state in trans_table:
        return trans_table[state]
    
    # 获取所有后继状态
    next_states = graph.get(state, [])
    
    # 如果后继状态为空（终止状态），SG值为0
    if not next_states:
        trans_table[state] = 0
        return 0
    
    # 计算所有后继状态的SG值
    sg_values = set()
    for next_state in next_states:
        sg_values.add(sg_function(next_state, trans_table, graph))
    
    # 找到未出现的最小非负整数（mex）
    mex = 0
    while mex in sg_values:
        mex += 1
    
    trans_table[state] = mex
    return mex

# 示例：简单的取石子游戏
# 规则：一堆n个石子，每次可以取1-3个，取最后一个的获胜
def stone_game_sg(n):
    """
    计算有n个石子时的SG值
    """
    # 构建状态转移图
    graph = {}
    for i in range(n + 1):
        if i == 0:
            graph[i] = []  # 终止状态，没有后继
        else:
            # 可以取1-3个石子
            graph[i] = [max(0, i - 1), max(0, i - 2), max(0, i - 3)]
    
    # 使用记忆化计算SG值
    trans_table = {}
    return sg_function(n, trans_table, graph)

# 测试
for i in range(10):
    print(f"石子数为{i}时的SG值: {stone_game_sg(i)}")

实践练习

练习1：基础Nim游戏

题目描述： 有3堆石子，数量分别为[3, 5, 7]。两人轮流取石子，每次可以从任意一堆中取任意多个。请问先手是否有必胜策略？

要求：

  1. 写出计算过程
  2. 如果先手必胜，给出第一步的取法

预期输出：

异或和计算：3(011) ^ 5(101) = 110(6), 6(110) ^ 7(111) = 001(1)
异或和不为0，先手必胜
先手可以从7个石子的堆中取6个，使状态变为[3,5,1]

练习2：组合游戏

题目描述： 现在有两个独立的取石子游戏：

  • 游戏A：一堆3个石子，每次取1-2个
  • 游戏B：一堆4个石子，每次取1-3个

两人轮流操作，每次可以选择其中一个游戏进行操作，最后无法操作的人输。请问先手是否有必胜策略？

提示： 组合游戏的SG值等于各子游戏SG值的异或和。

预期输出：

游戏A的SG序列：SG(0)=0, SG(1)=1, SG(2)=2, SG(3)=1
游戏B的SG序列：SG(0)=0, SG(1)=1, SG(2)=2, SG(3)=3, SG(4)=0
当前状态：SG(A)=1, SG(B)=0
总SG值：1 ^ 0 = 1 ≠ 0，先手必胜

练习3：自定义游戏

题目描述： 设计一个游戏：有编号1-n的石子堆，第i堆有i个石子。两人轮流操作，每次可以选择一个数字k，然后从所有石子数≥k的堆中各取k个石子。

例如：状态为[1,2,3,4]，选择k=2后变成[1,0,1,2]（注意0堆也要保留位置）。

请计算n=5时的初始SG值。

要求：

  1. 设计算法计算SG值
  2. 分析时间复杂度

常见错误

  1. 忽略游戏规则细节

    • 错误：认为所有取石子游戏都适用Nim的异或规则
    • 纠正：Nim游戏适用于每次可以从任意堆取任意多个的情况，限制取法时需要重新计算SG值

  2. SG函数递归计算错误

    • 错误：忘记处理终止状态，导致无限递归
    • 纠正：明确边界条件，终止状态SG值为0

  3. 组合游戏处理不当

    • 错误：直接对游戏状态求和
    • 纠正：组合游戏的SG值是各子游戏SG值的异或和，不是数值和

  4. 状态表示不清晰

    • 错误：无法正确描述游戏状态
    • 纠正：使用元组、列表等数据结构明确表示状态

小结

本课我们学习了博弈论的基础知识：

  1. 公平组合游戏是两人轮流、有限步、完全公平的对抗游戏
  2. Nim游戏的必胜策略基于二进制异或：异或和不为0则先手必胜
  3. SG函数是解决博弈问题的通用工具，每个状态对应一个SG值
  4. Sprague-Grundy定理：组合游戏的SG值等于各子游戏SG值的异或和

理解这些概念后，你可以解决大多数算法竞赛中的博弈问题。下一课我们将学习计算几何基础，探索如何在平面上高效处理几何问题。

练习编辑器

rust
Loading...

继续学习

完成本课后，建议继续学习下一课「计算几何基础」 以巩固所学知识。