一.公平组合游戏ICG：
定义为:
1.有两名玩家交替行动
2.在游戏进行的任意时刻，可以执行的合法行动与轮到哪位玩家无关
3.不能行动的玩家判负
二.mex运算
定义为:
\(mex(S) = min\{x\} (x \in N, x \notin S)\)
即为不属于集合\(S\)的最小非负整数。
三.有向图游戏
定义：给定一个有向无环图，规定一个起点，两名玩家轮流选择一条边前进，无法移动者判为负。
将一个公平组合游戏的某一状态视为一个节点，它向所有一步能到达的状态节点连一条有向边，即可将任一ICG游戏转换为有向图游戏。
四.SG函数
定义:对于有向图游戏中某一结点\(u\),设\(v_1, v_2, ..., v_k\)为其后继节点,\(u\)节点的sg函数值定义为:
\(sg(u) = mex(\{sg(v_1), sg(v_2), ..., sg(v_k)\})\)
观察可以发现,对于所有无法前进的状态,其sg函数值为0,此时当前玩家必败.
1.若某一结点sg函数值大于0,则其后继节点中存在sg为0的节点,先手可以选择此节点,使后手一直面临sg为0的节点,最终无法移动而失败,因此先手必胜.
2.若某一结点sg函数值为0,则其后继节点中不存在sg为0的节点,先手不论选择哪一个节点,都会使后手面临sg大于0的必胜状态,因此先手必败.
五.“组合型”组合博弈
定义为:
1.一个游戏可以被拆分成几个独立的部分, 每个部分可以是ICG游戏,也可以是一个组合型组合博弈.
2.各部分之间状态相互独立.
3.所有子游戏达到终止状态后整个游戏中止.
4.每轮玩家只能在一个子游戏上操作.
最经典的nim游戏就是一个“组合型”组合博弈.
六.“组合型”组合博弈的SG函数
设一个“组合型”组合博弈\(X\)游戏由k个子游戏构成,分别为:\(X_1, X_2, ..., X_k\),则:
\(sg(x) = sg(X_1) \ xor \ sg(X_2) \ xor \ ... \ xor \ sg(X_k)\)
标签：组合型,定义,定理,博弈论,玩家,sg,节点,游戏 From： https://www.cnblogs.com/mcggvc/p/17566763.html