在树的比赛,削减分支

Question

我们有一片生树的森林.两个玩家根据以下规则进行交替移动:一个动作是切割顶点及其所有子节点.进行最后一次移动(没有顶点)的玩家获胜.

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

假设我们有树木,我们需要说明目前的位置是赢还是输？

Answer 1

这是Hackenbush游戏。我强烈推荐这篇文章，该文章非常清楚地介绍了Grundy数，并在最后彻底讨论了hackenbush。