博弈论【CSP考点之一】
2024-10-02 13:40:27
发布于：浙江
5阅读
0回复
0点赞
① 尼姆（Nim）博弈
尼姆博弈是一类经典的组合博弈问题，玩家轮流从若干堆物品中取走任意数量的物品。游戏的目标是迫使对方无法继续行动（也就是使对方面对空堆）。基本的规则如下：
- 游戏开始时，有若干堆物品，每堆物品的数量不一定相同。
- 两位玩家轮流操作，每次操作时，玩家可以从任意一堆中取走任意数量的物品，但必须至少取走一个。
- 最后无法进行操作的玩家（面对空堆的玩家）输掉游戏。
尼姆博弈的关键是 异或运算。通过对每一堆物品的数量进行二进制表示，并对每一堆的数量进行异或操作，称为“Nim-sum”。具体分析如下：
- 若当前局面下所有堆物品的数量异或和（即 Nim-sum）为0，则该局面是一个“必败局面”，即当前玩家必输。
- 若 Nim-sum 不为 0，则该局面是一个“必胜局面”，即当前玩家有策略可以使对方进入必败局面。
因此，尼姆博弈的胜负关键在于如何根据当前的 Nim-sum 做出最优的决策。
② SG 函数（Sprague-Grundy 函数）
SG 函数是博弈论中对组合游戏进行分析的重要工具，特别是在广义的尼姆博弈中。SG 函数用于评估某个局面的胜负性质。其定义如下：
- 对于某个局面，SG 函数（Grundy 数）值为该局面的最小不在其子局面的 SG 函数值中的非负整数，简称 mex（minimum excludant）。
- 若 SG 值为 0，则当前局面是必败局面（即先手必输）；若 SG 值不为 0，则当前局面是必胜局面（即先手有必胜策略）。
具体的计算规则是：
- 对于没有合法操作的局面，SG 值为 0。
- 对于有多个操作的局面，计算每个合法操作后局面的 SG 值，并取这些值的 mex。
SG 函数的核心在于归纳地评估局面的性质，并通过动态规划的方式递归计算复杂博弈的 SG 函数值。
尼姆博弈的一个重要结论是，对于任意一堆物品，其 SG 函数值等于该堆物品的数量。而对于更复杂的组合博弈，可以通过分析每个局面和子局面的 SG 值来判断胜负。
这里空空如也
有帮助，赞一个