用AI方式解决Hangman问题

Question

我把它命名为"AI方式",因为我正在考虑让应用程序在没有人类交互的情况下玩刽子手游戏.

场景是这样的:

1. 一个可用的单词列表,其中包含数十万个英文单词.
2. 应用程序将从列表中选择一定数量的单词,例如20.
3. 应用程序对每个单词使用Hangman,直到WON或FAILURE.这里的限制是最大错误的错误猜测.26显然没有意义,让我们说6最大错误猜测.

我尝试了在wiki页面上提到的策略,但它不能很好地工作.基本成功率约为30%.

关于战略的任何建议/评论以及我应该挖掘哪些领域才能找到一个公平的好策略？

非常感谢.

-Simon

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

Answer 1

更新的想法

1. 下载单词词典并将其放入您选择的某个数据库或结构中
2. 当出现一个单词时,将您的猜测缩小到相同长度的单词并执行字母频率分布(您可以使用字典和/或列表集合进行快速分布分析和排序)
3. 从此列表中选择最常见的字母
4. 如果找到该字母,则根据已知字母和字长创建正则表达式,并从步骤2开始重复
5. 您应该能够快速缩小模式搜索产生的单个单词的范围

后人:

看看这个维基页面.它包括一个字母的第一个字母的频率表,可以帮助您调整算法.

您还可以考虑这样一个事实:如果您发现一个或两个元音,找到其他元音的可能性将显着下降,然后您应该尝试更常见的辅音.你列出的wiki页面的例子以E然后是T开头,然后连续尝试三个元音:A,O和I.前两个字母都被遗漏了,但是一旦找到第三个字母,两次然后过程应该切换到公共辅音和跳过尝试更多的元音,因为可能会更少.

任何有用的策略肯定会在字母和可能的单词上使用频率分布图,例如某些单词非常常见而其他单词很少使用,因此在一组更常见的单词上执行字母频率分布可能会有所帮助...猜测某些单词可能看起来更多经常比其他,但这取决于您的单词选择算法,可能不考虑"常见"用法.

您还可以构建专门的字母频率表,甚至可以即时构建.例如,考虑到维基百科^ h 一 NGM 一个 N实施例:你找到字母的单词的两次在两个位置第2和第6位.你知道这个单词有七个字母,并且有一个相当简单的注册表,你可以从字典中找出符合这种模式的单词:

_ a _ _ _ a _

然后对匹配此模式的那组单词执行字母频率,并使用该集合进行下一次猜测.冲洗并重复.我认为做一些我提到过的事情,尤其是最后一件事,真的会增加你成功的几率.

Answer 2

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

关于刽​​子手的一些观察：

1) 由于猜测单词中不存在的字母会伤害我们，因此我们应该根据单词频率（包含字母 X 的单词的百分比）而不是字母频率（X 在所有单词中出现的次数）来猜测字母。这应该可以最大限度地提高我们猜出错误字母的机会。

2）一旦我们正确猜出了一些字母，我们就对我们要猜的单词有了更多的了解。

这里有两个应该击败字母频率策略的策略。我假设我们有一本可能出现的单词词典。

如果我们期望这个词出现在我们的字典中：

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

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

3) 猜出我们还没有猜到的最常见的字母。

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

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

6) 转到步骤2

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

如果我们不希望这个词出现在我们的字典中：

n-grams1) 从字典中，为某个 n 值（比如 2）建立一个表。如果您以前没有遇到过 n 元语法，它们是单词内的连续字母组。例如，如果单词是"word"，则 2-gram 是{^w,wo,or,rd,d$}，其中^和$标记单词的开头和结尾。计算这 2-gram 的词频。

2）首先按词频猜测单个字母，如上所述

3) 一旦我们获得了一些命中，我们就可以使用 n-gram 的词频表来确定要从我们的猜测中消除的字母，或者我们可能能够猜到的字母。有很多方法可以实现这一目标：

例如，您可以使用 2-grams 来确定 中的空白w_rd可能不是z。或者，您可以确定单词末尾的字符___e_可能（例如）是dor s。

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

请记住，在每一步中，您都尽量不要做出错误的猜测，因为这使我们能够生存。如果 n-gram 告诉您一个位置很可能只是（例如）a、b 或 c，并且您的词频表告诉您 a 出现在 30% 的单词中，但 b 和 c 只出现在 10% 中，然后猜a。

为了获得最大收益，您可以结合使用这两种策略。