首页 > knuth > 对于Mastermind的Donald Knuth算法 - 我们能做得更好吗?

对于Mastermind的Donald Knuth算法 - 我们能做得更好吗? (Donald Knuth algorithm for Mastermind - can we do better?)

2019-02-27 knuth

问题

我为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算法,同时保持最坏的情况?到目前为止,我在网上找不到它的任何迹象。

谢谢!

阿龙

解决方法

据我所知,到目前为止还没有关于这种影响的已发表的工作。我前段时间做过这个观察,不能总是从“一步前瞻”设置中选择(规范的)第一次试验,从而获得更好的结果。我观察了不同的结果,不是从1122开始,而是用例如5544.也可以尝试随机选择,而不是先使用规范。是的,我同意你的观点,这是一个有趣的观点 - 但非常非常特别。

问题

I implemented Donald Knuth 1977 algorithm for Mastermind https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf

I was able to reproduce his results - 5 guess to win in the worst case and 4.476 on average.

And then I tried something different. I ran Knuth's algorithm repeatedly and shuffled the entire list of combinations randomly each time before starting. I was able to land on a strategy with 5 guesses to win in the worst case (like Knuth) but with 4.451 guesses to win on average. Better than Knuth.

Are there any previous work trying to outperform Knuth algorithm on average , while maintaining the worst case ? I could not find any indication of it on the web so far.

Thanks!

Alon

解决方法

As far as I know, up till now there is no published work about this effect yet. I have made this observation some time ago, one can get better results by not always choosing the (canonically) first trial out of the "one-step-lookahead-set". I observed the different results by not starting with 1122 but with e.g. with 5544. One can also try to choose randomly and not use the canonically first. Yes, I agree with you, that is an interesting point - but a very, very special one.

相似信息