博弈中的胜负状态
推理最佳策略下谁能获胜
博弈中的胜负状态 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
两位玩家，完美博弈
在组合博弈中，两位玩家轮流操作，双方都采取最优策略，无法操作的玩家输掉比赛。您的任务只是预测获胜者。🎯
每个局面都有一个标签
每个游戏局面都是一个状态。您的任务是将每个状态标记为当前行动玩家的胜局或败局。
什么是必胜状态
如果当前行动玩家至少有一种操作可以把对手带入必败状态，那么这个状态就是必胜状态。
什么是必败状态
当您采取的每一种操作都会把对手带入必胜状态时，这个状态就是必败状态。无论怎么做，您都无路可走。
基础情况
完全无法操作的局面就是基础情况。面对它的玩家已经输掉了比赛，因此应将其标记为败局。
从底部向上构建
从基础情况开始，逐步向外推导。每个新状态的标签只取决于它的操作所能到达的状态。
一个好操作就够了
要获胜，您只需要进行一个操作，把对手带入必败状态。找到任意一条逃生路线就足够了。
一个小例子
每次从一堆石子中取走 1 个或 2 个，最后取走石子的人获胜。当有0 个石子时，行动玩家输掉比赛，因此这是一个必败状态。
编写获胜判断
这个递归会尝试每一种操作，并对结果继续递归，从而为状态打上标签。⚙️
def win(n):
if n == 0:
return False
return any(not win(n - k) for k in (1, 2))使用记忆化保持快速
不同分支会重复遇到相同状态，因此请缓存每个结果。简单的记忆化缓存可以将指数级工作量变为线性时间。
from functools import lru_cache
@lru_cache(None)
def win(n):
return n != 0 and any(not win(n - k) for k in (1, 2))对称性是一条捷径
如果一个局面完全对称，第二位玩家通常可以模仿对手的操作并获胜。请留意这种镜像技巧。
快速检查
您面对一个状态。什么时候它对您来说是必败状态？
回顾
现在您可以标记状态：一个win有一种操作能让对手输，一个败局则没有。请从基础情况开始构建，并使用记忆化。🧠
常见问题解答
「博弈中的胜负状态」课时是免费的吗？
是的 — 「博弈中的胜负状态」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「博弈中的胜负状态」这节课中我会学到什么？
推理最佳策略下谁能获胜 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「博弈中的胜负状态」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 博弈中的胜负状态
- Nim 与 Grundy 数
- 折半搜索
- 快速调试：压力测试与分流排查