数学联邦政治世界观
超小超大

策梅洛定理 (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),接着再看更方便。

相关小说

山海星信 连载中
山海星信
小时椿
【己完结】【已授权非商广播剧】【原创作品】  【简介】  彼此之间错过却也是年轻时的冲动,也造成了最终的悲剧...  【温馨提醒】   如果......
1.1万字8个月前
墨画是对cp 连载中
墨画是对cp
一格温柔
好不容易和暗恋的人来了个偶遇,结果却被莫名其妙卷进了什么游戏,苏画表示游戏你大爷的!在游戏中和暗恋的人刚刚相认,结果就来了个社死现场,苏画再......
1.3万字8个月前
百日之行(第二季因为第一季没了) 连载中
百日之行(第二季因为第一季没了)
枫吹叶
第二季
0.2万字8个月前
幻影忍者之疯狂的火焰 连载中
幻影忍者之疯狂的火焰
爱吃刀子的鱼
无限刀子文哦~简称就是奥利奥里面夹着刀片!劳凯!对,没错,就是劳凯!有时候是凯劳就是写着写着玩的诶,我就是喜欢看反派文,嘿嘿————————......
0.9万字8个月前
五神灵玉 连载中
五神灵玉
权控江山
【黑历史,作者已经否认这是本人写的】【已完结】泠愈是天地间唯一一个五杂血脉,异能预知,实力顶天,一朝与系统和平绑定,于亿万界开挂,肆意妄为…......
16.1万字8个月前
重生之冷艳妖皇要逆天 连载中
重生之冷艳妖皇要逆天
妖皇紫魅
(小可爱们如果想交流一下的话,可以加这个群来一起聊天哦!互动群:1065689411)她,是上天宠儿,亦是九幽使者。一朝陨落,重临世间,竟已......
10.6万字8个月前