知识卡片

普通读书笔记卡 · 9952 · 生成模型:未记录

战略盗用证明先手必胜

理解等级:高级

在至少含两块巧克力的 Chomp 中,假定后手有必胜策略。先手可以只取最右上角一块,把回合交给后手。后手按其必胜策略走出的应手记作 X。由于任何合法的 X 都会同时移除右上角,先手从初始棋盘直接走 X 就能到达同一局面,并把下一回合交给对手。这与后手必胜的假设冲突。证明给出胜方,具体尺寸下的好开局仍需另找。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《AI游戏开发和深度学习进阶》第1章《谜题与游戏AI的过去和现在》,1.5 游戏的深奥程度与“先下手为强”定理(来源项目 book-source,`extracted/AI游戏开发和深度学习进阶/_epub-src/OEBPS/Text/0011.xhtml`) - 结论依据:右上角的单格移除可由随后的应手吸收,因此先手能直接走该应手并得到相同局面。 - 原始内容:先手的第一步只啃下右上角一块