Mastermind 的 Donald Knuth 算法——我们能做得更好吗？
Donald Knuth algorithm for Mastermind - can we do better?
我为 Mastermind 实现了 Donald Knuth 1977 算法 https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf
我能够重现他的结果 - 在最坏的情况下 5 次猜测获胜，平均 4.476 次。
然后我尝试了一些不同的东西。我重复 运行 Knuth 的算法，并在开始之前每次 运行domly 洗牌整个组合列表。在最坏的情况下（比如 Knuth），我能够采用 5 次猜测获胜的策略，但平均有 4.451 次猜测获胜。比 Knuth 好。
是否有任何以前的工作试图平均优于 Knuth 算法，同时保持最坏情况？到目前为止，我在网上找不到任何关于它的迹象。
谢谢！
阿隆
据我所知，目前还没有关于这个效果的发表作品。我前段时间做过这个观察，通过不总是从 "one-step-lookahead-set" 中选择（规范的）第一次试验可以获得更好的结果。我观察到不同的结果不是从 1122 开始而是以例如使用 5544。也可以尝试随机选择而不是先使用规范。是的，我同意你的看法，这是一个有趣的观点 - 但非常非常特别。
在论文中，Knuth 描述了如何选择策略：
Table 1 was found by choosing at every stage a test pattern that minimizes the maximum number of remaining possibilities, over all conceivable responses by the codemaker. If this minimum can be achieved by a “valid” pattern (a pattern that makes “four black hits” possible), a valid one should be used. Subject to this condition, the first such test pattern in numeric order was selected. Fortunately this procedure turns out to guarantee a win in five moves.
所以这在某种程度上是一种贪婪策略（试图在每一步都取得最大进展，而不是整体），而且还有一种临时的打破平局的策略。这意味着它在期望值上不一定是最优的，事实上 Knuth 就是这么说的：
The strategy in Table 1 isn’t optimal from the “expected number of moves” standpoint, but it is probably very close. One line that can be improved [...]
所以在论文发表时，高德纳已经意识到它不是最优的，甚至有一个明确的例子。
当这篇论文在他的文集 Selected Papers on Fun and Games（2010 年）中重新发表时，他在 6 页的论文中添加了 5 页的附录。在本附录中，他首先在第一段提到了随机化，并讨论了最小化预期移动次数的问题。将其分析为对所有 1296 个可能的代码字所做的所有移动的总和，他提到了几篇论文：
他的原算法给出了5801（5801/1296的平均值≈4.47608），小幅改进给出了5800（≈4.4753）
Robert W. Irving，“Towards an optimum Mastermind strategy,” Journal of Recreational Mathematics 11 (1978), 81-87 [同时保持在“最多 5”之内达到 5664 ⇒ ≈ 4.37 ]
E. Neuwirth，“Mastermind 的一些策略”，Zeitschrift fur Operations Research 26 (1982)，B257-B278 [达到 5658 ⇒ ≈ 4.3657]
Kenji Koyama 和 Tony W. Lai，“最佳策划策略”，《休闲数学杂志》25 (1993)，251-256 [达到 5626 ⇒ ≈ 4.34104938]
最后一个可能是最好的，因为它是通过详尽的深度优先搜索找到的。 （请注意，所有这些论文在预期的步数上都可以做得更好，如果你允许他们有时采取 6 步......我给出了带有“最多 5”约束的数字，因为这就是这里的问题所要求的.)
您可以通过假设代码制作者是对抗性的并且不会在 1296 个可能的代码字中随机均匀地选择，但是根据任何分布将使代码破解者最难，您可以使这个更通用（更难）。最后他提到了 Tom Nestor 所做的大量工作，最终解决了许多此类问题。
尝试跟进或重现这些结果可能会很有趣（例如编写详尽的搜索程序）。享受吧！
我为 Mastermind 实现了 Donald Knuth 1977 算法 https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf
我能够重现他的结果 - 在最坏的情况下 5 次猜测获胜，平均 4.476 次。
然后我尝试了一些不同的东西。我重复 运行 Knuth 的算法，并在开始之前每次 运行domly 洗牌整个组合列表。在最坏的情况下（比如 Knuth），我能够采用 5 次猜测获胜的策略，但平均有 4.451 次猜测获胜。比 Knuth 好。
是否有任何以前的工作试图平均优于 Knuth 算法，同时保持最坏情况？到目前为止，我在网上找不到任何关于它的迹象。
谢谢！
阿隆
据我所知，目前还没有关于这个效果的发表作品。我前段时间做过这个观察，通过不总是从 "one-step-lookahead-set" 中选择（规范的）第一次试验可以获得更好的结果。我观察到不同的结果不是从 1122 开始而是以例如使用 5544。也可以尝试随机选择而不是先使用规范。是的，我同意你的看法，这是一个有趣的观点 - 但非常非常特别。
在论文中，Knuth 描述了如何选择策略：
Table 1 was found by choosing at every stage a test pattern that minimizes the maximum number of remaining possibilities, over all conceivable responses by the codemaker. If this minimum can be achieved by a “valid” pattern (a pattern that makes “four black hits” possible), a valid one should be used. Subject to this condition, the first such test pattern in numeric order was selected. Fortunately this procedure turns out to guarantee a win in five moves.
所以这在某种程度上是一种贪婪策略（试图在每一步都取得最大进展，而不是整体），而且还有一种临时的打破平局的策略。这意味着它在期望值上不一定是最优的，事实上 Knuth 就是这么说的：
The strategy in Table 1 isn’t optimal from the “expected number of moves” standpoint, but it is probably very close. One line that can be improved [...]
所以在论文发表时，高德纳已经意识到它不是最优的，甚至有一个明确的例子。
当这篇论文在他的文集 Selected Papers on Fun and Games（2010 年）中重新发表时，他在 6 页的论文中添加了 5 页的附录。在本附录中，他首先在第一段提到了随机化，并讨论了最小化预期移动次数的问题。将其分析为对所有 1296 个可能的代码字所做的所有移动的总和，他提到了几篇论文：
他的原算法给出了5801（5801/1296的平均值≈4.47608），小幅改进给出了5800（≈4.4753）
Robert W. Irving，“Towards an optimum Mastermind strategy,” Journal of Recreational Mathematics 11 (1978), 81-87 [同时保持在“最多 5”之内达到 5664 ⇒ ≈ 4.37 ]
E. Neuwirth，“Mastermind 的一些策略”，Zeitschrift fur Operations Research 26 (1982)，B257-B278 [达到 5658 ⇒ ≈ 4.3657]
Kenji Koyama 和 Tony W. Lai，“最佳策划策略”，《休闲数学杂志》25 (1993)，251-256 [达到 5626 ⇒ ≈ 4.34104938]
最后一个可能是最好的，因为它是通过详尽的深度优先搜索找到的。 （请注意，所有这些论文在预期的步数上都可以做得更好，如果你允许他们有时采取 6 步......我给出了带有“最多 5”约束的数字，因为这就是这里的问题所要求的.)
您可以通过假设代码制作者是对抗性的并且不会在 1296 个可能的代码字中随机均匀地选择，但是根据任何分布将使代码破解者最难，您可以使这个更通用（更难）。最后他提到了 Tom Nestor 所做的大量工作，最终解决了许多此类问题。
尝试跟进或重现这些结果可能会很有趣（例如编写详尽的搜索程序）。享受吧！