我为 Mastermind 实现了 Donald Knuth 1977 算法https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf
我能够重现他的结果——在最坏的情况下 5 次猜测获胜，平均为 4.476。
然后我尝试了一些不同的东西。我反复运行 Knuth 的算法，并在每次开始前随机打乱整个组合列表。在最坏的情况下（如 Knuth），我能够采用 5 次猜测获胜的策略，但平均有 4.451 次猜测获胜。比高德纳好。
是否有任何先前的工作试图平均优于 Knuth 算法，同时保持最坏的情况？到目前为止，我在网上找不到任何迹象。
谢谢！
阿隆
在论文中，Knuth 描述了如何选择该策略：
表 1 是通过在每个阶段选择一个测试模式来找到的，该模式在编码制作者的所有可能响应中最小化剩余可能性的最大数量。如果这个最小值可以通过“有效”模式（一种使“四个黑色命中”成为可能的模式）实现，则应使用有效模式。在此条件下，选择了按数字顺序排列的第一个这样的测试模式。幸运的是，这个程序可以保证在五步中获胜。
所以它在某种程度上是一个贪婪的策略（试图在每一步而不是整体上取得最大的进步），而且还有一个临时的平局策略。这意味着它不需要在期望值上是最优的，而且 Knuth 确实是这样说的：
从“预期移动次数”的角度来看，表 1 中的策略并不是最优的，但可能非常接近。可以改进的一条线 [...]
因此，在论文发表时，Knuth 已经意识到它不是最优的，甚至有一个明确的例子。
当这篇论文在他的娱乐和游戏精选论文集(2010) 中重新发表时，他在 6 页的论文中添加了一个 5 页的附录。在本附录中，他首先在第一段中提到了随机化，并讨论了最小化预期移动次数的问题。他将其分析为对所有 1296 个可能的代码字进行的所有移动的总和，他提到了几篇论文：
他的原始算法给出了 5801（平均 5801/1296 ≈ 4.47608），小幅改进给出了 5800（≈ 4.4753）。
Robert W. Irving，“Towards an optimization 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 所做的很多工作，这些工作最终解决了许多此类问题。
尝试跟进或重现这些结果可能会很有趣（例如，编写详尽的搜索程序）。享受！
据我所知，到目前为止，还没有关于这种效果的发表作品。我前段时间已经进行了这个观察，可以通过不总是从“一步向前看”中选择（规范的）第一次试验来获得更好的结果。我观察了不同的结果，不是从 1122 开始，而是从 5544 开始。人们也可以尝试随机选择，而不是首先使用规范。是的，我同意你的看法，这是一个有趣的观点——但非常非常特别。