博弈论

必败点和必胜点

• 必败点

SG 函数

先定理 $mex$ 运算，一个集合中，最小的不属于这个集合的非负整数，例如：$mex\{0,1,2,4\}=3$

int mex(auto v) {  // v可以是vector、set等容器
    unordered_set<int> S;
    for (auto e : v) S.insert(e);
    for (int i = 0;; ++i)
        if (S.find(i) == S.end()) return i;
}

对于任意状态 $x$ ，定义 $SG(x)=mex(S)$ 其中 $S$ 是 $x$ 后继状态的 SG 函数值的集合

终止必然是空集，所以 SG 函数的终止状态为 $SG(x)=0$ 当且仅当 $x$ 为必败点时