algorithm - 树上的游戏，砍树枝

Question

我们有一片生根的树林。两名玩家根据以下规则交替移动：一个移动是切割顶点及其所有子节点。最后一步（没有顶点）的玩家获胜。

我们如何计算游戏中位置的 Grundy 函数？

假设我们有一棵树，我们需要说当前位置是赢还是输？

Answer 1

这是哈肯布什的游戏。我强烈推荐这篇文章，它非常清晰地涵盖了 Grundy 数字，并在最后彻底讨论了 hackenbush。