策梅洛定理 (2-2)

2. 如果某一个倒数第二的节点对应着玩家2行动的回合，并且它连着的某个末端节点标记为2，那么我们也把该节点标记为2.

3. 如果某一个倒数第二的节点对应着玩家1行动的回合，但是它连着的所有末端节点都标记为2，那么我们把它标记为2

4. 类似地，如果某一个倒数第二的节点对应着玩家2行动的回合，但是它连着的所有末端节点都标记为1，那么我们把它标记为1

如此类推。抽象一般地来说，我们根据规则为末端节点标记后，一步步往回开始标记，每步都根据已有的节点标记来决定要标什么，直到标记上原点为止。也就是说，如果我们准备标记玩家i 行动回合的一个节点 p ，而该节点紧连着一个已经标了 i 的节点，那么我们给 p 标上 i （意味着在 p 的局面时 i 占优） ；而如果 p 所有紧接的节点都标的是 i 的对手，那么我们就给 p 标上 i 的对手（意味着在 p 的局面时 i 的对手占优）.

这个标记法能够一路标记到原点，也就是游戏初始状态。此时原点根据递归规则标记的是谁，那么这局游戏就是谁有必胜策略（证明：如果初始状态是玩家1行动，并且标注是1，那么根据递归定义玩家1有办法一直将游戏局面保持在标注1的局面上直到终局；而如果是玩家1行动并且标注是2，这就意味着无论玩家1如何行动，接下来玩家2都有办法一直将局面保持在标注2的局面上直到终局。 如果初始状态是玩家2行动的话思路类似）。

这样的算法能够帮助我们在有穷游戏中判定先手还是后手必胜，只不过它很慢就是了，需要遍历完整个game tree。

参考

1. 严格来说策梅洛本人只考虑了国际象棋，但是现在说到策梅洛定理说的都是finite games

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。