用人工智能的方法解决Hangman游戏问题

Question

我将其命名为“AI之路”，因为我想制作一个应用程序，可以在没有人类交互的情况下玩猜单词游戏。

场景如下：

1. 一个可用的单词列表，其中包含数以万计的英语单词。 2. 应用程序将从列表中选择一定数量的单词，例如20个。 3. 应用程序针对每个单词玩猜单词游戏，直到赢得胜利或失败。限制是最大错误次数。显然，26次并没有意义，假设最多6次错误猜测。

我尝试了维基页面中提到的策略，但效果不佳。成功率大约为30％。

关于策略以及我应该挖掘哪个领域以找到一个相当好的策略的任何建议/评论都欢迎。

谢谢。

-Simon

PS：JavaScript实现看起来相当不错。( https://github.com/freizl/play-hangman-game )

- Simon

Answer 1

更新的想法

1. 下载一个词典并将其放入某个数据库或您选择的结构中
2. 在给定一个单词时，缩小你的猜测范围，只考虑与该单词长度相同的单词，并进行字母频率分布（您可以使用一个字典和/或列表集合进行快速分布分析和排序）
3. 从这个列表中选择最常见的字母
4. 如果找到该字母，则基于已知的字母和单词长度创建一个正则表达式模式，并从步骤2重复
5. 您应该能够快速缩小到符合您的模式搜索的单词

供后人参考:

查看这个维基页面。它包括单词第一个字母的频率表，可帮助您调整算法。

您还可以考虑这样一个事实：如果您在单词中发现一个元音或两个元音，则找到其他元音的可能性会显著降低，此时您应该尝试更常见的辅音。您列出的维基页面示例以E和T开头，然后连续尝试三个元音：A，O和I。前两个字母被错过了，但是一旦找到第三个字母，就应该转向通用辅音并跳过尝试更多元音，因为可能会更少。

任何有用的策略都肯定会使用字母和可能是单词的频率分布图，例如一些单词非常常见，而其他单词很少使用，因此在一组更常见的单词上执行字母频率分析可能会有所帮助......猜测某些单词可能比其他单词出现得更频繁，但这取决于您的单词选择算法，该算法可能不考虑“常见”的用法。

您还可以构建专门的字母频率表，甚至是即时生成的。例如，给定维基百科的hangman示例：在两个位置（第二个和第六个）的单词中找到了两个A。您知道该单词有七个字母，并且使用一个相当简单的正则表达式，您可以将与此模式匹配的单词从字典中隔离出来。

_ a _ _ _ a _

然后对符合该模式的单词集执行字母频率分析，并将该集用于下一次猜测。反复进行这个过程。我认为执行我提到的一些操作，尤其是最后一个，会大大增加你成功的几率。

- Paul Sasik

---

+1，但请注意您也可以删除包含您猜测错误字母的单词。一旦您知道a和b不出现，您可以在正则表达式中将“.”替换为“[^ab]”。 - Timothy Jones

感谢大家的评论。这些建议真的很有帮助，代码的正确性和效率都得到了极大的提升。 一旦我把它整理得比较好看，我会公开发布代码，以便任何感兴趣的人参考。 - Simon

这个解决方案中的AI部分是什么？我只是想知道这个解决方案是否只是过滤。我们不能使用任何机器学习算法吗？ - user77005

Answer 2

链接页面中的策略似乎是“按字母频率排序猜测顺序”和“先猜元音字母，然后按字母频率排序猜测顺序”。

关于Hangman的一些观察：

1）由于猜测不在单词中的字母会对我们造成损失，因此我们应该根据单词频率（包含字母X的单词的百分比）而非字母频率（所有单词中X出现的次数）来猜测字母。这应该可以最大化我们猜测错误的概率。

2）一旦我们正确地猜出了一些字母，我们就更了解正在尝试猜测的单词。

以下是两种应该打败字母频率策略的策略。我要假设我们有一个可能出现的单词的字典。

如果我们期望目标单词在字典中：

1）我们知道目标单词的长度n。删除在字典中不是长度为n的所有单词。

2）计算字典中所有字母的单词频率。

3）猜测我们还没有猜过的最常见字母。

4）如果我们猜对了，删除不与已揭示字母匹配的所有单词。

5）如果我们猜错了，删除包含错误猜测字母的所有单词。

6）回到步骤2

为了达到最大效果，不要计算步骤2中所有字母的单词频率，而是计算目标单词中仍为空白的位置上所有字母的单词频率。

如果我们不期望目标单词在字典中：

1）从字典中构建一个n-gram表（例如n=2）。如果您以前没有接触过n-gram，它们是单词内连续字母的组。例如，如果单词是"word"，则2-gram为“{^w, wo, or, rd, d$}”，其中"^"和"$"标记单词的开头和结尾。统计这些2-grams的单词频率。

2）首先按照与上述相同的单词频率来猜测单个字母。

3）一旦我们有了一些击中，我们就可以使用n-gram的单词频率表来确定要从我们的猜测中消除的字母，或者我们可能能够猜测的字母。有很多方法可以实现这一点：

例如，您可以使用2-gram来确定在"w_rd"中的空格不可能是"z"。或者，您可以确定“___e_”中的字符可能（例如）是“d”或“s”。

或者您可以使用n-gram生成可能字符的列表（尽管对于长单词来说这可能会很昂贵）。请记住，您始终可以划掉所有包含您已经猜测但不在目标单词中的字母的n-gram。

请记住，在每个步骤中，您都在尝试避免犯错，因为这能让我们保持生命。如果n-gram告诉您一个位置只有（比如）a、b或c是可能的，而您的单词频率表告诉您a出现在30%的单词中，但b和c只出现在10%的单词中，则猜测a。

为了最大化效益，您可以结合两种策略。

- Timothy Jones

Answer 3

讨论的策略适合人类实施。由于您正在编写AI，因此可以将计算能力投入其中以获得更好的结果。

将单词列表缩小到仅与您对目标单词拥有的信息相匹配的单词。 （起初，这只是单词长度。）对于每个字母A到Z，请注意至少包含其中一个字母的单词数（这与字母计数不同）。选择得分最高的字母。

您甚至可以在计算猜测时运行多个循环，但这可能对现代CPU来说过于复杂。

澄清：我是说您可以运行前瞻。如果我们在这个级别上选择“A”，那么下一个级别会出现什么选项？这是O（x ^ n）算法，显然您不能走得太远。

- Loren Pechtel

---

+1 虽然我认为每次猜测运行这个程序都没有问题，但在我的系统中，/etc/dictionaries-common/words 中的8字词是最常见的，并且仅有15,738个。 - Timothy Jones

运行前瞻的优势是什么？一旦你猜测完毕，难道不必重新计算新信息吗？我认为，在每次猜测后修剪可能单词列表，而不是计算整个状态空间，也可以做得很好。 - Timothy Jones

@TimothyJones：当然要修剪。这个想法是为了避免局部优化，而不是在整体上最好的。 - Loren Pechtel