博弈论学习笔记

博弈论

SG函数

定义

• SG函数是在组合游戏上的函数，用 \(SG(X)\) 表示状态 \(X\) 的函数值。

公式

• 设状态 \(X\) 的所有后继状态为 \(A_1,A_2,\dots,A_k\) ，则：\(SG(X) = mex \left\{SG(A_1),SG(A_2),\dots,SG(A_k) \right\}\)。
• 若有多个相互独立的组合游戏 \(B_1,B_2,\dots,B_k\) ，则总的 \(SG\) 值为：$ SG(B_1) \oplus SG(B_2) \oplus \dots\oplus SG(B_k)$。
• 当 \(SG(X) = 0\) 时，先手必败，反之先手必胜。