algorithm - 改进的刽子手游戏，最优算法

Question

计算机现在随机选择其中一个单词，程序应尽可能少地尝试猜出该单词。

计算机在提示后给出以下提示

1. 开始于
2. 以
结尾
3. 包含
4. 不包括

让我们以单词 house 为例:如果我们猜测“h”，那么我们得到的答案是搜索到的以“h”开头的单词。如果我们猜测“ous”，我们得到的答案是搜索到的单词包含“ous”usw。如果我们猜测“房子”，那么我们会得到一个答案，即我们找到了正确的词。

这个问题有最优策略吗？天真的方法是简单地尝试每个词。当然，那是非常糟糕的。我认为更好的方法。作为第一个提示，选择最常见的字母等。但我认为你可以更有效地做到这一点

Answer 1

是的，有一个最优策略。但是，该策略取决于解决给定单词列表的游戏树。单词列表是有限的；您在每个节点都有一组有限的选择；每个猜测都可以配置为保证结果添加大量信息，从而使您更接近解决方案。因此，博弈树是有限的。

为给定的词典(单词列表)构建游戏树。如果您想要有保证的最佳 攻击，您需要解决博弈树，涉及minimax 和修剪。如果您想在更短的时间内找到非常好的攻击，请从决策树的 ML(机器学习)区域绘制。

这是否足以让您朝着解决方案的方向前进？