解决游戏Ghost(在xkcd上看到) - 拼写字母而不说一句话

Question

如何解决游戏幽灵这个词？Ghost是一款双人文字游戏.玩家轮流将字母添加到不断增长的单词片段中.

引用Randall Munroe

要玩Ghost,你可以替代说信.(a)拼写单词,或(b)创建一个不能成为单词开头的字符串的第一个人输了.所以你要替代建立一个单词,你必须始终努力学习一个单词,但你不能成为一个单词.示例游戏,玩家一个和两个交替的字母:

游戏 - 玩家1拼写失败"游戏"

ABSORB - 玩家2拼写失败"ABSORB"

BZ-"挑战" - 玩家1,看到"Z",说"挑战."意思是"我认为你不是建立一个单词.命名一个以'BZ'开头的单词并证明你不只是制造东西."玩家2不能,并且输了.如果可以的话,他会赢.

然后Munroe指责他在一次飞行中解决了游戏(针对特定字典).他

• 断言第一个玩家总能获胜
• 展示了一张简短的婴儿床单,第一个玩家可以使用它来保证胜利
• 如果第一个玩家出错,第二个玩家可以用来赢得一张简短的婴儿床单

例如,如果第一个玩家以"L"打开,则第二个玩家可以用另一个"L"回复,迫使第一个玩家输入"LLAMA".

Munroe没有分享他的算法或他的代码:(他是如何解决Ghost的？

---

还有一个更难的变体,其中字母可以添加到单词片段之前.

Answer 1

为了解决字典问题——

您创建一个树结构，其中根节点不是字母，每个子节点是将单词中的下一个字母添加到树中的结果。

叶节点是完整的单词（您可以丢弃具有也是完整单词的初始子集的单词）。

当您构建完整的树并拥有所有叶节点时，具有奇数个字母的叶节点是玩家 2 的目标，具有偶数个字母的节点是玩家 1 的目标。

你上升了一个层次；如果给定节点下面的所有节点都是玩家 x 的目标，则该节点也成为玩家 x 的目标；或者，如果给定节点下方的任何节点是玩家 x 的目标，并且该节点将在玩家 x 的回合中被击中，则该节点将成为玩家 x 的目标。

如果单个角色节点是玩家 1 的目标，则玩家 1 始终可以赢得游戏。