SG函数详解（Python实现博弈论中的经典算法）

什么是SG函数？

SG函数是用于分析无偏博弈（Impartial Games）的一种数学工具。所谓无偏博弈，是指两个玩家面对完全相同的可行动作集合，且游戏信息完全公开（如Nim游戏、取石子游戏等）。

SG函数的核心思想是：将一个复杂的游戏分解为若干个独立的子游戏，每个子游戏都有一个“状态值”（即SG值），整个游戏的胜负可以通过这些SG值的异或（XOR）结果来判断。

关键概念：mex 运算

mex（Minimum Excludant）表示“最小非负整数不在集合中”。例如：

• mex({0, 1, 2}) = 3
• mex({1, 2}) = 0
• mex({0, 2, 3}) = 1

SG函数的定义如下：

对于一个游戏状态 x，其SG值为：

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

也就是说，当前状态的SG值等于所有可达下一状态SG值集合的mex。

Python实现SG函数

下面我们以经典的“取石子游戏”为例：每次可以从一堆石子中取1、2或3颗，最后无法取的人输。我们来计算每个石子数量对应的SG值。

def mex(s):    """计算集合s的mex值"""    m = 0    while m in s:        m += 1    return mdef compute_sg(n, moves=[1, 2, 3]):    """    计算从0到n的SG值    moves: 每次可以取的石子数量列表    """    sg = [0] * (n + 1)  # sg[0] = 0，没有石子时为终止状态        for i in range(1, n + 1):        reachable = set()        for move in moves:            if i >= move:                reachable.add(sg[i - move])        sg[i] = mex(reachable)        return sg# 示例：计算前10个状态的SG值sg_values = compute_sg(10)print("石子数: SG值")for i, val in enumerate(sg_values):    print(f"{i:2d}     : {val}")

运行上述代码，你会得到如下输出：

石子数: SG值 0     : 0 1     : 1 2     : 2 3     : 3 4     : 0 5     : 1 6     : 2 7     : 3 8     : 0 9     : 110     : 2

可以看到，SG值呈现周期性变化（0,1,2,3循环）。这是因为每次可取1~3颗，所以每4个状态就重复一次。

如何判断胜负？

在多堆石子游戏中（比如Nim变种），总游戏的SG值等于各堆SG值的异或和（XOR）：

def is_winning_position(piles, moves=[1, 2, 3]):    """判断当前石子堆是否为必胜态"""    max_pile = max(piles)    sg = compute_sg(max_pile, moves)    xor_sum = 0    for pile in piles:        xor_sum ^= sg[pile]    return xor_sum != 0  # 异或和不为0，则先手必胜# 测试print(is_winning_position([4, 5, 6]))  # 输出 True 或 False

如果异或和为0，说明当前是必败态；否则是必胜态。

总结

通过本教程，你已经掌握了SG函数的基本原理、mex运算、以及如何用Python实现SG函数算法来解决公平博弈问题。无论你是准备算法竞赛，还是学习博弈论，这个工具都非常实用。

记住：SG函数适用于所有满足以下条件的游戏：

• 两人轮流操作
• 信息完全公开
• 操作规则对双方相同（无偏）
• 游戏必然在有限步内结束

希望这篇算法教程能帮助你打开博弈论的大门！动手试试修改moves参数，看看不同规则下SG值的变化吧！