Donald算法大师

Question

我正在开发一个实现Donald算法的主谋游戏。前五个步骤是明确的。我必须为每个可能的答案创建一组排列，使用1122作为我的第一猜测，比较从集合到1122的每一个可能的答案，然后删除不返回与当前猜测相同的反馈的任何可能的答案。现在的问题在于确定下一个猜测以及我应该如何实现第6步。

主谋-五猜-算法Donal Knuth的五猜算法解决游戏大师。 1977年，Donald证明了密码破解器可以在五步或更短的时间内解决模式，使用一种算法逐步减少可能的模式数。 该算法的工作原理如下：

1. 创建由1296个可能的代码组成的集合S (1111,1112 . 6665,6666)。
2. 从最初的猜测1122开始(Knuth给出的例子表明，其他的第一次猜测，如1123,1234，不会在每一段代码的五次尝试中获胜)。
3. 玩猜测，以得到一个彩色和白色钉的反应。
4. 如果响应是四色的，游戏就赢了，算法就终止了。
5. 否则，从S中删除任何代码，如果当前的猜测是代码，则不会给出相同的响应。

例如，如果你目前的猜测是1122，你就得到了BW的回应；

如果代码为1111，您将得到两个黑色挂钩(BB)，猜测值为1122，这与一个黑钉和一个白钉子(BW)不一样。因此，从潜在解决方案列表中删除1111。

F(1122, 1112 ) =血BW≠BW→从S移除1112

F(1122, 1113 ) = BB≠BW→从S中删除1113

F(1122, 1114 ) = BB≠BW→从S移除1114

F(1122, 1314 ) = BW=BW→将1314保持在S中

1. 应用minimax技术寻找下一个猜想如下： 对于每一个可能的猜测，即1296的任何未使用的代码，而不仅仅是S中的代码，计算出对于每个可能的有色/白色peg分数，S中有多少可能性会被消除。猜测的分数是它可能从S中排除的可能性的最小数目。

对于1296的每个未使用的代码，通过一个循环S将为每个可能的彩色/白色peg分数提供一个“命中计数”；创建一组具有最小最大分数的猜测(因此是最小值)。

从具有最小(最大)分数的猜测集合中，选择一个作为下一个猜测，尽可能选择S的一个成员。

Knuth遵循以最小数值选择猜测的惯例，例如2345低于3456。Knuth还给出了一个例子，说明在某些情况下，S的任何成员都不会是得分最高的猜测之一，因此猜测在下一轮中不可能获胜，但要确保在五局中获胜是必须的。

1. 从步骤3重复

链接到维基百科页面

Answer 1

取一组未试过的代码，称之为T。

在T上迭代，将每段代码视为猜测，g。

对于每个g，再次在T上迭代，将每段代码视为可能的真正隐藏代码，c。

如果真正的代码是c，则计算猜测g生成的黑白钉住分数。

保持一个可能的分数表，当你在可能的c上迭代时，跟踪每个分数产生多少代码。也就是说，有多少个c的选择产生两个黑人，一个白人，多少个产生两个黑人，两个白人，等等。

当您考虑了所有可能的代码( g)时，请考虑最常出现的分数。你可能会说这是猜测g的信息最少的结果，那就是g的分数，越低越好。

当你在g上迭代时，用最低的分数记录猜测。这是猜测。