当前位置: 首页 > news >正文

SG 函数

模型介绍

SG 函数是组合博弈论中的核心工具,用于分析公平组合博弈(Impartial Games)。它提供了一个统一的框架,将各种博弈问题转化为 Nim 游戏的形式。

基本概念:

  • 公平组合博弈:两个玩家、完全信息、无随机因素、有限步结束;
  • 每个游戏状态都有一个 SG 值;
  • 终局状态的 SG 值为 \(0\)
  • 其他状态的 SG 值由其后续状态的 SG 值决定。

历史背景

SG 函数由 R.P. Sprague(\(1935\))和 P.M. Grundy(\(1939\))独立发现,因此得名 Sprague-Grundy 函数。他们的工作建立了组合博弈论的数学基础,证明了任何公平组合博弈都等价于某个 Nim 堆。

核心定义与证明

SG 函数定义

对于一个游戏状态x,其SG函数值定义为:

\[SG(x)=mex\{SG(y)\} \]

其中 mex(minimum excludant)表示最小的不属于该集合的非负整数。

Sprague-Grundy 定理

  • 定理:任何公平组合博弈都等价于一个 Nim 堆,其大小为该博弈的 SG 值。
  • 证明思路:
  1. 基础情况:终止状态的 SG 值为 \(0\),等价于大小为 \(0\) 的 Nim 堆;
  2. 归纳假设:假设所有后续状态都等价于 Nim 堆;
  3. 关键观察:从状态 \(x\) 可以移动到 SG 值为 \(0,1,...,SG(x)-1\) 的任何状态;但不能移动到 SG 值为 \(SG(x)\) 的状态;这与大小为 \(SG(x)\) 的 Nim 堆的行为完全一致;
  4. 组合博弈:多个独立游戏的组合的 SG 值等于各游戏 SG 值的异或和。

详细证明

  1. 引理 \(1\)\(SG(x)=0\) 当且仅当 \(x\) 是必败态,证明:
  • 如果 \(SG(x)=0\),则没有 \(SG=0\) 的后继状态,即所有移动都到必胜态;
  • 如果 \(SG(x)\neq0\),则存在移动到 \(SG=0\) 状态的移动。

定理证明:

考虑游戏 G,其 SG 值为 \(g\)。我们证明 G 等价于大小为 \(g\) 的 Nim 堆。

  1. 从状态G可以移动到任何 SG 值小于 \(g\) 的状态(由 \(mex\) 定义);
  2. 从大小为 \(g\) 的 Nim 堆可以移动到任何小于 \(g\) 的大小;
  3. 两者具有完全相同的移动可能性。

因此,\(G\cong Nim(g)\),对于组合游戏 \(G_1+G_2+\cdots+G_n\)

\[SG(G_1+G_2+\cdots+G_n)=SG(G_1)\oplus SG(G_2)\oplus\cdots\oplus SG(G_n) \]

代码实现

基础 SG 函数计算

#include <bits/stdc++.h>
#define int long longusing namespace std;// 计算mex函数
int mex(const set<int>& values) {int result = 0;while (values.find(result) != values.end()) {result++;}return result;
}// 通用的SG函数计算框架
class SGFunction {private:vector<int> sg_values;vector<vector<int>> moves;  // moves[i] 表示从状态i可以移动到的状态public:SGFunction(int max_state, const vector<vector<int>>& move_rules): sg_values(max_state + 1, -1), moves(move_rules) {}// 计算状态state的SG值int calculateSG(int state) {if (sg_values[state] != -1) {return sg_values[state];}if (isTerminal(state)) {return sg_values[state] = 0;}set<int> successor_sg;for (int next_state : getMoves(state)) {successor_sg.insert(calculateSG(next_state));}return sg_values[state] = mex(successor_sg);}// 判断是否为终止状态(需要根据具体游戏实现)bool isTerminal(int state) {// 基础实现:状态0为终止状态return state == 0;}// 获取从state可以移动到的状态(需要根据具体游戏实现)vector<int> getMoves(int state) {if (state < moves.size()) {return moves[state];}return {};}// 判断组合游戏是否先手必胜bool isWinningPosition(const vector<int>& states) {int xor_sum = 0;for (int state : states) {xor_sum ^= calculateSG(state);}return xor_sum != 0;}
};

具体游戏示例:取石子游戏

// 取石子游戏的SG函数实现
class TakeStonesGame {private:vector<int> sg;vector<int> allowed_moves;public:TakeStonesGame(int max_stones, const vector<int>& moves): sg(max_stones + 1, -1), allowed_moves(moves) {sort(allowed_moves.begin(), allowed_moves.end());}int calculateSG(int stones) {if (sg[stones] != -1) return sg[stones];if (stones == 0) return sg[stones] = 0;set<int> successor_sg;for (int take : allowed_moves) {if (take <= stones) {successor_sg.insert(calculateSG(stones - take));}}return sg[stones] = mex(successor_sg);}void analyzeGame(int max_stones) {cout << "SG值分析 (允许取: ";for (int move : allowed_moves) cout << move << " ";cout << ")" << endl;for (int i = 0; i <= max_stones; i++) {cout << "SG(" << i << ") = " << calculateSG(i) << endl;}cout << endl;// 分析周期模式findPeriod();}private:void findPeriod() {cout << "寻找周期模式..." << endl;int start = 10;  // 从第10个状态开始寻找周期int period = 0;for (int p = 1; p <= 20; p++) {bool is_periodic = true;for (int i = start; i < start + p && i + p < sg.size(); i++) {if (sg[i] != sg[i + p]) {is_periodic = false;break;}}if (is_periodic) {period = p;break;}}if (period > 0) {cout << "发现周期: " << period << endl;} else {cout << "未发现明显周期" << endl;}}
};

变种题目与解法

变种 1:多堆取石子游戏

  • 问题:有 \(n\) 堆石子,每堆 \(a_i\) 个,每次可以从一堆中取 \(f(k)\) 个(\(f\) 是给定的函数);
  • 解法:计算每堆的 SG 值,然后求异或和。
class MultiPileGame {private:vector<int> sg;function<int(int)> move_function;public:MultiPileGame(int max_stones, function<int(int)> func): sg(max_stones + 1, -1), move_function(func) {}int calculateSG(int stones) {if (sg[stones] != -1) return sg[stones];if (stones == 0) return sg[stones] = 0;set<int> moves;int k = 1;while (true) {int take = move_function(k);if (take > stones) break;moves.insert(calculateSG(stones - take));k++;}return sg[stones] = mex(moves);}bool canWin(const vector<int>& piles) {int xor_sum = 0;for (int pile : piles) {xor_sum ^= calculateSG(pile);}return xor_sum != 0;}
};

变种 2:图游戏

  • 问题:在图上移动棋子,每次沿边移动,无法移动者输;
  • 解法:使用记忆化搜索计算每个节点的 SG 值。
class GraphGame {private:vector<vector<int>> graph;vector<int> sg_values;public:GraphGame(int n, const vector<vector<int>>& adj_list): graph(adj_list), sg_values(n, -1) {}int calculateSG(int node) {if (sg_values[node] != -1) return sg_values[node];set<int> successor_sg;for (int neighbor : graph[node]) {successor_sg.insert(calculateSG(neighbor));}return sg_values[node] = mex(successor_sg);}// 在多个棋子的情况下判断胜负bool canWin(const vector<int>& positions) {int xor_sum = 0;for (int pos : positions) {xor_sum ^= calculateSG(pos);}return xor_sum != 0;}
};

变种 3:减法游戏

  • 问题:每次只能取特定数量的石子;
  • 解法:预计算 SG 值表。
class SubtractionGame {private:vector<int> sg;vector<int> allowed_moves;public:SubtractionGame(int max_n, const vector<int>& moves): sg(max_n + 1, -1), allowed_moves(moves) {}int calculateSG(int n) {if (sg[n] != -1) return sg[n];if (n == 0) return sg[n] = 0;set<int> values;for (int move : allowed_moves) {if (move <= n) {values.insert(calculateSG(n - move));}}return sg[n] = mex(values);}void printSGTable(int up_to) {cout << "n\tSG(n)" << endl;for (int i = 0; i <= up_to; i++) {cout << i << "\t" << calculateSG(i) << endl;}}
};

变种 4:翻硬币游戏

  • 问题:一排硬币,每次翻转连续的 \(k\) 个硬币,最后无法操作者输;
  • 解法:将游戏分解为子游戏。
class CoinFlipGame {private:vector<int> sg;int flip_length;public:CoinFlipGame(int max_coins, int k) : sg(max_coins + 1, -1), flip_length(k) {}int calculateSG(int n) {if (sg[n] != -1) return sg[n];if (n < flip_length) return sg[n] = 0;set<int> values;for (int i = 0; i <= n - flip_length; i++) {// 翻转操作将游戏分成两个独立的子游戏values.insert(calculateSG(i) ^ calculateSG(n - flip_length - i));}return sg[n] = mex(values);}
};

总结

SG 函数的重要性:

  1. 统一框架:将各种公平组合博弈统一到 Nim 游戏
  2. 组合性质:多个独立游戏的组合的 SG 值简单异或即可
  3. 算法效率:通过记忆化搜索高效计算复杂博弈
  4. 理论深度:连接了博弈论、组合数学和计算机科学
http://www.hskmm.com/?act=detail&tid=35883

相关文章:

  • 2025 年铝包木阳光房生产厂家最新推荐榜:口碑至上的实力品牌甄选及选购指南
  • Oracle统计信息相关
  • 2025年栏杆护栏厂家权威推荐榜:不锈钢栏杆、桥梁防撞护栏、河道景观护栏,专业制造与工程应用深度解析
  • Consul 与 Prometheus 集成实战:服务自动发现与监控配置指南(含 ThinkPHP8 示例)
  • 2025年TYPE-C母座厂家权威推荐榜:防水/板上/沉板/立插/卧式/侧贴/贴片式/插件式全系列,5A大电流高速TID认证接口一站式供应
  • 题解:P1196 [NOI2002] 银河英雄传说
  • Oracle下查询数据库SQL ID
  • 进程管理专题(一)
  • 使用SemaphoreSlim控制并发数
  • 杂题简述
  • css网格布局
  • 2025 年粘合剂厂家最新推荐排行榜:聚焦企业助力工业选品冷压球团/除尘灰/萤石粉/型煤/煤球粘合剂厂家推荐
  • 2025年流量控制阀厂家推荐排行榜,液压流量控制阀,气动流量控制阀,高压流量控制阀,精密流量控制阀批发公司推荐
  • 楼里网站开发完成,产品进入交代期
  • 比特币挖矿盈利能力9月下降超7%
  • 2025年医药冷链运输厂家权威推荐榜:药品/临床样本/CAR-T/蛋白/诊断试剂/生物制品/血液/细胞/芯片全程温控,冷藏车/冷藏箱/保温箱/干冰/液氮及国际冷链进出口专业服务
  • 2025 装修公司推荐排行榜单:江苏/浙江/制药厂/厂房/实验室/办公室/店面/净化室装修公司推荐,实测老客复购率与专业能力
  • 零代码改造 + 全链路追踪!Spring AI 最新可观测性详细解读
  • xupt 3g移动开发实验室二面
  • 2025年服饰厂家权威推荐榜:棒球帽,卫衣,羽绒服源头厂家精选,潮流设计与舒适品质口碑之选
  • 2025年10月北京昌平回龙观酒店推荐:对比评测榜助您锁定高性价比会议与度假之选
  • 2025年10月北京昌平回龙观酒店推荐榜:五家对比评测与实用选择指南
  • 2025 年最新华侨生联考培训机构口碑推荐榜:聚焦优质教学服务,助力考生高效备考,附详细选择指南
  • 洛谷题单指南-进阶数论-CF632D Longest Subsequence
  • 2025 年最新推荐锯床实力厂家排行榜:龙门 / 数控 / 金属带锯床等多类型设备权威甄选优质企业角度/金属带/双立柱/小型/大型锯床厂家推荐
  • 2025织带厂家权威推荐:东莞永沣专业定制防水织带与飞织鞋面
  • 2025发电机厂家实力推荐:三澳新能源科技专业制造,高效稳定动力解决方案
  • 2025年织带类厂家权威推荐榜:防水织带、鞋垫、编织包/针织包/飞织包包、松紧带、鞋带、织带、飞织鞋面源头企业精选
  • 2025年10月护眼台灯品牌评测推荐:十强榜单对比与理性选购指南
  • UV紫外相机在工业视觉检测中的应用 - 实践