我实施了Donald Knuth 1977算法https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-master.p./knuth-master-master-master-master-mastermind.pdf
我能够复制他的结果-5猜测在最坏的情况下赢得胜利，平均为4.476。
然后我尝试了一些不同的事情。我反复运行了Knuth的算法，并在开始之前每次都随机列出整个组合列表。在最坏的情况下（如诺斯），我能够以5个猜测获胜的策略，但平均有4.451的猜测。比Knuth更好。
在维持最坏情况的同时，是否有任何以前试图超越诺斯算法的工作？到目前为止，我在网络上找不到任何迹象。
谢谢！
alon
在论文中，诺斯描述了如何选择策略：
表1是通过在每个阶段选择一个测试模式来最小化剩余可能性的最大数量，对代码者的所有可能响应。如果可以通过"有效"模式（使"四个黑色命中"成为可能的模式）来实现此最小值，则应使用有效的模式。在这种情况下，选择了数字顺序的第一个此类测试模式。幸运的是，此过程证明了五动作的胜利。
因此，在某种程度上是一种贪婪的策略（试图在每个步骤而不是总体上取得最大的进步），此外，还有一个临时的打决策。这意味着它不必在期望值上是最佳的，而诺斯确实说了：
表1中的策略从"预期的动作数"的角度并不是最佳的，但它可能非常接近。一条可以改进的行[...]
因此，在发表论文时已经已经意识到它不是最佳的，甚至没有明确的例子。
当本文在他的收藏中重新出版选择Fun and Games （2010年）的论文时，他在6页的论文中添加了5页附录。在此附录中，他首先在第一段中提及随机化，并讨论了最大程度地减少预期移动次数的问题。他提到了一些论文：
分析所有动作的总和。他的原始算法给出了5801（平均5801/1296≈4.47608），次要改进给出了5800（≈4.4753）。
罗伯特·W·欧文（Robert W.>
e。Neuwirth，"策划的一些策略"，Zeitschrift毛皮操作研究26（1982），B257-B278 [达到5658⇒≈4.3657]
Kenji Koyama和Tony W. Lai，"最佳策略"，《休闲数学杂志》 25（1993），251-256 [成就5626⇒≈4.34104938]
其中的最后一个是最好的，因为它是通过详尽的深度搜索发现的。（请注意，所有这些论文在预期的动作数量中都可以稍微更好。）
您可以通过假设代码制造商是对手的，并且在1296可能的代码字中的随机选择不一致，但是根据任何分布，对于CodeBreaker而言，它最困难。最后，他提到了汤姆·内斯特（Tom Nestor）完成的许多工作，这最终解决了许多这样的问题。
您可能会很开心地尝试跟进或复制这些结果（例如编写详尽的搜索程序）。享受！
到目前为止，还没有关于此效果的已发表工作。我不久前就进行了这一观察，可以通过"一步景观"中的（典型）第一次试验来获得更好的结果。我观察到不同的结果，不是从1122开始，而是从例如。使用5544.也可以尝试随机选择，而不是先使用规范。是的，我同意你的看法，这是一个有趣的观点 - 但是一个非常非常特别的。