博弈论
公平组合游戏
定义
-
两名玩家交替行动
-
游戏会在有限步数内结束
-
游戏结果只有输赢，没有平局
-
游戏的发展是确定性的，不存在概率因素
概率因素：掷色子
-
游戏的局面、规则、可选行动对两名玩家来说是完全相同的
游戏的局面、规则、可选行动不同：棋类游戏
性质：游戏的状态确定了，两名玩家的胜负就已经确定了！
注：大多棋类游戏其实也有该性质
PN（必胜必败）分析
- 在公平游戏组合中，我们把一个游戏局面称作一个状态
- 状态可以花式表示，可以通过一个数字、一个数对、一些字母等等来表示
- 必胜态：一个状态，存在策略使对方无论如何操作都是必输
- 必败态：一个状态，使当前方无论己方如何操作都无法取胜（即，一定会输）
- 后继状态：若状态 \(S_1\) 通过某玩家的恰一步操作后可以变为状态 \(S_2\) ，则称状态 \(S_2\) 是状态 \(S_1\) 的后继状态
定理
- 若某种状态的后继状态都是必胜态，则该状态是必败态
- 若某种状态的后继状态都是必败态，则该状态是必胜态
- 若某种状态的后继状态有必胜态也有必败态，则该状态是必胜态
方法
- 通过最终的获胜条件
- 反方向地找出所有以其为后继状态的状态
- 并判断其最终的胜负
有向图游戏
定义
- 给定一个有向无环图
- 初始有一枚棋子放在某个节点上
- 双方轮流移动棋子，每次移动一步
- 没法行动的算输
SG函数
前置知识：
运算 \(MEX(S)\)
- 运算对象：非负整数集合 \(S\)
- 运算结果：未出现在集合中的最小非负整数
e.g:\(MEX(\{1,2,4,6\})=0\),\(MEX(\{0,1,2\})=3\)
- 定义有相同游戏中某个节点 \(v\) 的 \(SG\) 函数值：即 \(MEX(v的后继节点的SG的集合)\)
- 因此，出度为 \(0\) 的节点的 \(MEX值=MEX(\phi)=0\)
总结
有向图与公平组合游戏
- 公平组合游戏都可以抽象为有向图游戏
- 图中节点代表游戏状态
- 有向边代表一个状态是另一个状态的后继状态
- 当当前状态的 \(SG\) 函数为 \(0\) 时必败
- 当 \(SG\) 函数不为 \(0\) 时必胜
有向图游戏的和
定义
-
有一个游戏
-
给出 \(n\) 个有向图游戏 \(G_1,G_2...,G_n\)
-
两名玩家轮流行动，不可以跳过回合，玩家可以选择一个有向图游戏，按照有向图游戏的规则走一步
-
最后，无法做出行动的玩家失败
即，在 \(n\) 个有向图游戏中都走不了
-
这个游戏就叫做这 \(n\) 个有向图游戏的和游戏，这 \(n\) 个游戏叫做该游戏的子游戏
事实上，有向图游戏也是有向图游戏的和游戏（ \(n=1\) ）
分析
- 最终状态（每个子游戏的棋子都在一出度为 \(0\) 的点上）的异或和为 \(0\) ，是必败态
- 异或和为 \(0\) 的状态进一步操作后一点得到一个异或和不为 \(0\) 的状态
- 异或和不为 \(0\) 的状态总可以找到一种方案，使得一步操作后得到的异或和为 \(0\) 的状态
- 该和游戏不会无限进行下去，会在有限步内结束
结论
- 有向图游戏的和的 \(SG\) 函数为各子游戏 \(SG\) 函数的异或和
- \(SG(G_1+G_2...+G_n)=SG(G_1)\) ^ \(SG(G_2)\) ^ \(...\) ^ \(SG(G_n)\)
- 其含义不变，依然是为 \(0\) 必败，非 \(0\) 必胜
补充
- 将第 \(i\) 个游戏的 \(SG\) 值变为 \(x\) 后， 和游戏的 \(SG\) 值变为了 \(SG(G_1)\) ^ \(SG(G_2)\) ^ \(...\) ^ \(SG(G_n)\) ^ \(SG(G_i)\) ^ \(x\)
- 异或和为 \(0\) 的状态一步操作后一定得到一个异或和不为 \(0\) 的状态
- 异或和不为 \(0\) 的状态，总可以找到一种方案，使得一步操作后得到的异或和为 \(0\) 的状态