知识卡片
战略盗用证明先手必胜
在至少含两块巧克力的 Chomp 中,假定后手有必胜策略。先手可以只取最右上角一块,把回合交给后手。后手按其必胜策略走出的应手记作 X。由于任何合法的 X 都会同时移除右上角,先手从初始棋盘直接走 X 就能到达同一局面,并把下一回合交给对手。这与后手必胜的假设冲突。证明给出胜方,具体尺寸下的好开局仍需另找。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
先手的第一步只啃下右上角一块
参考来源
- 位置:《AI游戏开发和深度学习进阶》第1章《谜题与游戏AI的过去和现在》,1.5 游戏的深奥程度与“先下手为强”定理(来源项目 book-source,`extracted/AI游戏开发和深度学习进阶/_epub-src/OEBPS/Text/0011.xhtml`)
- 结论依据:右上角的单格移除可由随后的应手吸收,因此先手能直接走该应手并得到相同局面。
- 原始内容:先手的第一步只啃下右上角一块