5

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

引用兰德尔·门罗

玩幽灵，你交替说字母。第一个（a）拼写一个单词，或（b）创建一个不能作为单词开头的字符串的人输了。因此，您交替构建一个单词，并且您必须始终朝着一个单词努力，但您不能成为结束它的人。示例游戏，玩家一和两个交替字母：

GAME - 玩家 1 因拼写“Game”而输了</p>

ABSORB — 玩家 2 因拼写“ABSORB”而输了</p>

BZ-“挑战”——玩家 1，看到“Z”，说“挑战”。意思是“我认为你没有建立一个词。说出一个以‘BZ’开头的词，证明你不只是在编造东西。” 玩家 2 不能，并且输了。如果他能，他会赢。

然后，门罗吹嘘说他在一次飞行中解决了这个游戏（针对特定的字典）。他

  • 断言第一个玩家总是可以获胜
  • 展示第一个玩家可以用来保证获胜的短床单
  • 展示一张短床单，如果第一个玩家犯错，第二个玩家可以用它来获胜

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

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

还有一个更难的变体，可以在单词片段之前添加字母。

4

3 回答 3

4

解字典——

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

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

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

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

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

于 2012-07-05T16:31:49.843 回答
1

从字典中的所有单词构建一棵树（trie）。

我们将逐步将树中的所有节点标记为玩家 1 或 2 的获胜者。

  • 在叶子中你已经知道游戏的结果，所以简单地标记它们
  • 一旦一个叶子的所有子节点都被填满，我们就知道结果：如果正在进行下一步的玩家至少有一个获胜子叶子，那么所讨论的父叶子就是他的赢家，否则就是另一个玩家。
  • 通过在这两个步骤之后对树进行后序遍历，我们可以填充所有树，并在每个节点处确定每个玩家的获胜步骤是什么。

检查根节点（用空词），看看谁有获胜策略（假设另一个玩家玩得很完美）。

于 2012-07-05T16:32:24.197 回答
0

解决了！一年前我做了第一部分，但今天我想如何修剪成一个简洁的获胜策略

https://github.com/hickford/ghost

于 2012-07-05T22:39:43.277 回答