algorithm - 解决文字游戏 Ghost(如 xkcd 上所见)- 拼写字母而不造字

Question

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

引用 Randall Munroe

To play Ghost, you alternate saying letters. The first person to either (a) spell a word, or (b) create a string that cannot be the start of a word, loses. So you alternate building a word, and you have to always be working toward a word, but you can’t be the one to end it. Sample games, with players one and two alternating letters:

G-A-M-E — Player 1 loses by spelling “Game”

A-B-S-O-R-B — Player 2 loses by spelling “ABSORB”

B-Z-”Challenge” — Player 1, seeing “Z”, says “Challenge.” meaning “I think you’re not building toward a word. Name a word that starts with ‘BZ’ and prove you’re not just making stuff up.” Player 2 can’t, and loses. If he could, he’d win.

Munroe 然后吹嘘说他在一次飞行中解决了这个游戏(针对特定的字典)。他

• 断言先手总能赢
• 展示第一位玩家可以用来保证获胜的简短婴儿床单
• 展示一张简短的婴儿床单，如果第一个玩家犯错，第二个玩家可以用来获胜

例如，如果第一个玩家以“L”开局，第二个玩家可以用另一个“L”回复，迫使第一个玩家在“LLAMA”输掉。

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

---

还有一个 harder variant其中字母可以添加到单词片段之前。

Answer 1

求解字典--

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

叶节点是完整的单词(您可以丢弃初始子集也是完整单词的单词)。

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

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

如果单个角色节点是玩家 1 的目标，则玩家 1 总能赢得比赛。