如何解决“大师”猜谜游戏？
你将如何创build一个algorithm来解决下面的难题，“主谋”？
你的对手select了六种不同的颜色（黄色，蓝色，绿色，红色，橙色，紫色）。 你必须猜测他们select了哪一个，以什么顺序。 每次猜测之后，你的对手会告诉你有多less（但不是哪一种）你猜对的颜色是正确的颜色（“黑色”），多less（但不是哪个）是正确的颜色，但在错误的地方[ “白色”]。 游戏结束，当你猜对（4黑人，0白人）。
例如，如果你的对手select了（蓝色，绿色，橙色，红色），你猜（黄色，蓝色，绿色，红色），你会得到一个“黑色”（红色）和两个白色蓝色和绿色）。 你会得到相同的分数猜测（蓝色，橙色，红色，紫色）。
我感兴趣的是你会select什么algorithm，（可选）如何将它转换成代码（最好是Python）。 我感兴趣的编码解决scheme是：
- 清楚（容易理解）
- 简洁
- 高效（快速猜测）
- 有效（解决谜题的最less数量的猜测）
- 灵活（可以轻松回答有关algorithm的问题，例如，最糟糕的情况是什么？）
- 一般（可以很容易地适应其他types的难题比主谋）
我很高兴看到一个非常有效的algorithm，但是效率不是很高（如果不是很差的话）。 然而，一个非常有效而且有效的algorithm是不灵活且难以实现的，并没有被使用。
我已经发布了自己的（详细的）Python解决scheme，但这并不是唯一或最好的方法，所以请发布更多！ 我不期待一篇文章;）
关键工具：熵，贪婪，分支; Python，生成器，itertools，装饰 – undecorate模式
在回答这个问题时，我想build立一个有用的function语言来探讨这个问题。 我将通过这些function，描述他们和他们的意图。 最初，这些文档有大量文档，使用doctesttestingembedded式unit testing; 我不能高度评价这种方法，作为实现testing驱动开发的一个很好的方法。 但是，它不能很好地转换成StackOverflow，所以我不会这样表示。
首先，我将需要几个标准模块和将来的导入（我使用Python 2.6）。
from __future__ import division # No need to cast to float when dividing import collections, itertools, math 我将需要一个得分function。 最初，这返回一个元组（黑人，白人），但我发现输出更清楚一点，如果我使用了一个namedtuple：
Pegs = collections.namedtuple('Pegs', 'black white') def mastermindScore(g1,g2): matching = len(set(g1) & set(g2)) blacks = sum(1 for v1, v2 in itertools.izip(g1,g2) if v1 == v2) return Pegs(blacks, matching-blacks)
为了使我的解决scheme一般，我传入任何特定于Mastermind问题作为关键字参数。 因此，我创build了一个函数来创build这些参数，并使用** kwargs语法来传递它。 这也使我可以轻松地添加新的属性，如果我以后需要他们。 请注意，我允许猜测包含重复，但限制对手select不同的颜色; 改变这一点，我只需要改变下面的G。 （如果我想让对手的秘密重复，我也需要改变得分function。）
def mastermind(colours, holes): return dict( G = set(itertools.product(colours,repeat=holes)), V = set(itertools.permutations(colours, holes)), score = mastermindScore, endstates = (Pegs(holes, 0),)) def mediumGame(): return mastermind(("Yellow", "Blue", "Green", "Red", "Orange", "Purple"), 4)
有时我需要根据将函数应用到集合中的每个元素的结果来划分集合。 例如，数字1..10可以通过函数n％2划分成偶数和奇数（赔率给1，均等给0）。 下面的函数返回这样一个分区，实现为从函数调用的结果映射到给出结果的元素集（例如{0：evens，1：odds}）。
def partition(S, func, *args, **kwargs): partition = collections.defaultdict(set) for v in S: partition[func(v, *args, **kwargs)].add(v) return partition
我决定探索一个使用贪婪熵方法的求解器。 在每个步骤中，它计算可能从每个可能的猜测获得的信息，并select最有信息的猜测。 随着可能性数量的增加，这将会严重地缩放（二次方），但让我们试试吧！ 首先，我需要一种方法来计算一组概率的熵（信息）。 这只是-Σp日志p。 不过，为了方便起见，我会允许没有标准化的input，也就是不加1：
def entropy(P): total = sum(P) return -sum(p*math.log(p, 2) for p in (v/total for v in P if v))
那么我该如何使用这个function呢？ 那么，对于给定的可能性集合V和给定的猜测g，我们从这个猜测中得到的信息只能来自得分函数：更具体地说，得分函数如何划分我们的可能性集合。 我们想猜测一下，在剩下的可能性中区分最好 – 把它们分成最小的一组 – 因为这意味着我们更接近于答案。 这正是上面的熵函数所给出的一个数字：大量的小集合将比小集合高得多。 我们所需要做的就是把它放进去。
def decisionEntropy(V, g, score): return entropy(collections.Counter(score(gi, g) for gi in V).values())
当然，在任何给定的步骤中，我们实际上将会有一组剩余的可能性V和一组可能的猜测G，我们将需要select使熵最大化的猜测。 此外，如果有多个猜测具有相同的熵，则倾向于select一个也可以是有效的解决scheme; 这保证了方法会终止。 我使用标准的python装饰undecorate模式与内置的max方法一起做到这一点：
def bestDecision(V, G, score): return max((decisionEntropy(V, g, score), g in V, g) for g in G)[2]
现在我需要做的就是反复调用这个函数，直到猜到正确的结果。 我经历了这个algorithm的一些实现，直到我find一个看起来是正确的。 我的一些function将会以不同的方式来处理这个问题：一些列举了所有可能的决策顺序（每个对手可能做出的一个猜测），而另一些则只对通过树的单一path感兴趣（如果对手已经select一个秘密，我们只是试图达成解决scheme）。 我的解决scheme是一个“懒树”，其中树的每个部分是一个可以评估或不评估的生成器，允许用户避免昂贵的计算，他们不需要。 为了清晰的代码，我也结束了使用两个更多的名字。
Node = collections.namedtuple('Node', 'decision branches') Branch = collections.namedtuple('Branch', 'result subtree') def lazySolutionTree(G, V, score, endstates, **kwargs): decision = bestDecision(V, G, score) branches = (Branch(result, None if result in endstates else lazySolutionTree(G, pV, score=score, endstates=endstates)) for (result, pV) in partition(V, score, decision).iteritems()) yield Node(decision, branches) # Lazy evaluation
以下函数根据提供的评分函数评估通过此树的单个path：
def solver(scorer, **kwargs): lazyTree = lazySolutionTree(**kwargs) steps = [] while lazyTree is not None: t = lazyTree.next() # Evaluate node result = scorer(t.decision) steps.append((t.decision, result)) subtrees = [b.subtree for b in t.branches if b.result == result] if len(subtrees) == 0: raise Exception("No solution possible for given scores") lazyTree = subtrees[0] assert(result in endstates) return steps
这现在可以用来build立一个用户评分计算机猜测的主谋互动游戏。 玩这个游戏揭示了一些有趣的事情。 例如，最具信息量的第一个猜测是forms（黄色，黄色，蓝色，绿色），而不是（黄色，蓝色，绿色，红色）。 额外的信息是通过使用恰好一半的可用颜色获得的。 这也适用于6色3孔Mastermind（黄色，蓝色，绿色）和8色5孔Mastermind（黄色，黄色，蓝色，绿色，红色）。
但是仍然有许多问题不容易用交互式求解器来解答。 例如，贪婪熵方法所需要的步数是多less？ 有多less投入采取这么多步骤？ 为了更容易地回答这些问题，我首先产生一个简单的函数，把上面的懒树变成一组通过这棵树的path，也就是每个可能的秘密，一个猜测和分数列表。
def allSolutions(**kwargs): def solutions(lazyTree): return ((((t.decision, b.result),) + solution for t in lazyTree for b in t.branches for solution in solutions(b.subtree)) if lazyTree else ((),)) return solutions(lazySolutionTree(**kwargs))
发现最坏的情况是寻找最长解决scheme的一个简单问题：
def worstCaseSolution(**kwargs): return max((len(s), s) for s in allSolutions(**kwargs)) [1]
事实certificate，这个求解器总是会以5步或更less的步骤完成。 五步！ 我知道我小时候玩“师父”时，经常比这个时间长。 但是，由于创build了这个求解器，并且玩了这个求解器，我的技术有了很大的提高，即使没有时间来计算每一步的熵理想猜测，5步确实是一个可以实现的目标;）
解决者有多大可能需要5个步骤？ 它会在1或2步完成吗？ 为了发现这一点，我创build了另一个简单的小函数来计算解的长度分布：
def solutionLengthDistribution(**kwargs): return collections.Counter(len(s) for s in allSolutions(**kwargs))
对于贪婪的熵方法，允许重复：7例分2步; 共55例，分3步; 229个案例分四步; 69例最多5步。
当然，贪婪熵方法不能保证最坏的步骤数量。 我的通用语言的最后一部分是一个algorithm，决定是否有给定的最坏情况下的任何解决scheme。 这将告诉我们贪婪的熵是否理想。 要做到这一点，我采取了分行约束的策略：
def solutionExists(maxsteps, G, V, score, **kwargs): if len(V) == 1: return True partitions = [partition(V, score, g).values() for g in G] maxSize = max(len(P) for P in partitions) ** (maxsteps - 2) partitions = (P for P in partitions if max(len(s) for s in P) <= maxSize) return any(all(solutionExists(maxsteps-1,G,s,score) for l,s in sorted((-len(s), s) for s in P)) for i,P in sorted((-entropy(len(s) for s in P), P) for P in partitions))
这绝对是一个复杂的function，所以更多的解释是为了。 第一步就是像以前一样根据猜测结果根据分数对剩余的解决scheme进行分割，但这次我们不知道我们会做什么猜测，所以我们存储所有的分区。 现在我们可以回想一下每一个，有效地列举了整个可能的决策树的世界，但是这需要很长的时间。 相反，我观察到，如果此时没有将其余解决scheme划分为n个以上的分区，那么在将来的任何一个步骤中都不会有这样的分区。 如果我们还剩下k个步骤，那就意味着在我们用完猜测之前，我们可以区分至多nk-1个解决scheme（最后一步，我们必须总是正确猜测）。 因此，我们可以放弃任何包含分数映射到多个解决scheme的分区。 这是接下来的两行代码。
最后一行代码执行recursion，使用Python的任何和所有函数来清晰起见，并且首先尝试最高熵的决定，希望在正面情况下最小化运行时间。 它也首先回归到分区的最大部分，因为如果这个决定是错误的，这是最有可能失败的。 再一次，我使用标准装饰未打印模式，这次是用来包装Python的sorting函数。
def lowerBoundOnWorstCaseSolution(**kwargs): for steps in itertools.count(1): if solutionExists(maxsteps=steps, **kwargs): return steps
通过不断增加步数来调用solutionExists，我们得到了最差情况下Mastermind解决scheme所需步数的严格下限：5个步骤。 贪婪的熵方法确实是最优的。
出于好奇，我发明了另一个猜谜游戏，我绰号“二维”。 在这里，你试图猜测一对数字; 在每一步，你都会被告知你的答案是否正确，如果你猜的数字不less于秘密中的相应数字，并且数字不大。
Comparison = collections.namedtuple('Comparison', 'less greater equal') def twoDScorer(x, y): return Comparison(all(r[0] <= r[1] for r in zip(x, y)), all(r[0] >= r[1] for r in zip(x, y)), x == y) def twoD(): G = set(itertools.product(xrange(5), repeat=2)) return dict(G = G, V = G, score = twoDScorer, endstates = set(Comparison(True, True, True)))
对于这个游戏，贪婪的熵方法有五个步骤的最坏情况，但有一个更好的解决scheme，最坏的情况下可能有四个步骤，从而证实了我的直觉，即近视贪婪对于谋士来说只是偶然的理想。 更重要的是，这表明了我的语言是多么的灵活：所有相同的方法都适用于这个新的猜谜游戏，就像Mastermind一样，让我用最less的额外编码来探索其他游戏。
性能呢？ 显然，在Python中实现，这个代码不会很快。 我也放弃了一些可能的优化，以支持清晰的代码。
一个便宜的优化是观察，第一步，大多数猜测基本上是相同的：（黄色，蓝色，绿色，红色）与（蓝色，红色，绿色，黄色）或（橙色，黄色，红色） ，紫色）。 这大大减less了我们在第一步中需要考虑的猜测数量 – 否则是游戏中最昂贵的决定。
但是，由于这个问题的运行时间增长率很高，即使进行了这种优化，我也无法解决8色5孔Mastermind问题。 相反，我将algorithm移植到C ++中，保持通用结构相同，并采用按位运算来提高关键内部循环的性能，从而实现了许多数量级的加速。 我把这个作为练习留给读者:)
我曾经写过一个“ Jotto ”求解器，它本质上就是“Master Mind”。 （我们每个字都选一个，我们轮stream猜对方的单词，在“正确”（精确）匹配和“别处”（正确的字母/颜色，但错误的放置）上打分。
解决这个问题的关键是实现评分函数是对称的。
换句话说，如果score(myguess) == (1,2)那么我可以使用相同的score()函数来比较我以前的猜测与任何其他的可能性，并消除任何不完全相同的分数。
让我举一个例子：隐藏的词（目标）是“分数”…当前的猜测是“傻瓜” – 得分是1,1（一个字母，“o”，是“正确的”;另一个字母“，”是“在别处”）。 我可以消除“猜测”这个词，因为分数（“猜测”）（反对“傻瓜”）返回（1,0）（最后的匹配，但没有其他）。 所以“猜测”这个词与“傻子”不一致，对一个不知名的词给出了一个分数（1,1）。
所以我现在可以走过每五个字母的单词（或五个颜色/字母/数字等的组合），并消除任何不符合“傻瓜”的1,1。 在每一次迭代中这样做，你将会很快地收敛在目标上。 （对于五个字母的单词，我每次都能在6次尝试中得到…通常只有3或4个）。 当然，只有6000个左右的“单词”，每个猜测你都可以消除接近95％。
注意：对于下面的讨论，我正在谈论五个字母“组合”，而不是六个颜色的四个元素。 相同的algorithm适用; 然而，对于老式的“精灵”游戏来说，这个问题要小得多……在经典的“精神头脑”计划中，只有1296个彩色钉的组合（6 ** 4），假设允许重复。 导致收敛的推理线涉及一些组合：对于5个元素目标有20个非获胜可能得分（ n = [(a,b) for a in range(5) for b in range(6) if a+b <= 5] ，如果你好奇的话，可以看到所有这些，所以我们希望任何随机的有效select都有大约5％的机会匹配我们的分数，其他的95％因此每一个得分的猜测都会被排除，这并不能解释词汇模式中可能的聚类，但是现实世界的行为已经足够接近单词，并且对于“精神”规则来说更接近，然而，只有4种中的6种颜色插槽我们只有14个可能的非获胜分数，所以我们的收敛速度不是那么快）。
对于Jotto来说，两个小挑战是：在UNIX系统上生成一个好的世界列表（ awk -f 'length($0)==5' /usr/share/dict/words -f'length awk -f 'length($0)==5' /usr/share/dict/words或similar），如果用户select了一个不在我们的字典中的词（生成每个字母组合，'aaaaa'到'zzzzz'，即26 ** 5 …或110万）。 Python中的一个简单的组合生成器需要大约1分钟的时间来生成所有这些string…一个优化的应该更好。 （我还可以添加一个要求，即每个“单词”至less有一个元音…但是这个约束没有多大帮助— 5个元音* 5个可能的位置，然后乘以26 ** 4个其他组合） 。
对于Master Mind，你使用相同的组合发生器…但只有4或5个“字母”（颜色）。 每个6色组合（其中的15,625个）都可以在一秒内生成（使用与上面所用相同的组合生成器）。
如果我今天正在编写这个“Jotto”程序，比如在Python中，我会通过在背景中生成所有字母组合的线程来“作弊”，而我仍然被字典中的字词排除（当我的对手给我打分时，猜测等）。 当我产生他们我也消除了迄今为止所有的猜测。 因此，在我消除了所有已知的单词之后，我会有一个相对较小的可能性列表，而对于一个人类玩家，我通过并行处理他们的input来“隐藏”我的大部分计算滞后。 （而且，如果我写了一个这样的程序的Web服务器版本，我会让我的Web引擎和本地守护进程进行交谈，询问与一组分数一致的序列。守护进程将保留一个本地生成的所有字母组合列表，将使用select.select()模型将可能性反馈给每个正在运行的游戏实例—每个都会提供守护进程将要应用的守护进程的字/记分对，作为filter对其反馈的可能性进行过滤客户）。
（相比之下，我使用Borland TurboPascal在大约20年前的XT版本中编写了我的“Jotto”版本…它可以执行每个消除迭代 – 从编译成几千字的列表开始 – 我写了一个简单的字母组合生成器（见下面）…将结果保存到一个中等大的文件，然后运行我的文字处理器的拼写检查，用macros来删除所有“拼写错误“—然后我用另一个macros来包装正确的标点符号中的所有剩余行，使它们成为我的数组的有效静态赋值，这是我的程序的一个#include文件，所有这一切让我构build了一个独立的游戏程序，“知道”几乎每一个有效的英文字母的单词;程序是.COM —小于50KB，如果我没记错的话）。
由于其他原因，我最近在Python中编写了一个简单的任意组合生成器。 这是大约35行代码，我已经发布到我的“trite snippets”wiki在bitbucket.org …它不是Python的意义上的“生成器”…但是一个类可以实例化为无限序列元素的“数字”或“符号”组合（基本上以任何正整数为基数）。
你可以在： Trite Snippets：Arbitrary Sequence Combination Generator中find它
对于score()函数的完全匹配部分，你可以使用这个：
def score(this, that): '''Simple "Master Mind" scoring function''' exact = len([x for x,y in zip(this, that) if x==y]) ### Calculating "other" (white pegs) goes here: ### ... ### return (exact,other)
我认为这个例子说明了Python的一些优点： zip()两个序列，返回任何匹配的，并取得结果的长度）。
寻找“其他”地点的比赛看似比较复杂。 如果不允许重复，那么你可以简单地使用集合来find交集。
[在我以前编辑这个消息时，当我意识到如何使用zip()进行精确匹配时，我错误地认为我们可以用other = len([x for x,y in zip(sorted(x), sorted(y)) if x==y]) - exact …但是晚了，我累了。 当我睡着时，我意识到这个方法是有缺陷的。 坏，吉姆！ 不要发布没有足够的testing！*（testing了几个案件发生了工作） ]。
在过去，我使用的方法是对两个列表进行sorting，比较每个列表的头部：如果头部相等，则增加计数并从两个列表中popup新项目。 否则将popup一个新值到两个头中的较小者，然后重试。 当任一列表为空时立即中断。
这确实起作用; 但是相当冗长。 我可以用这种方法得到最好的结果就是十几行代码：
other = 0 x = sorted(this) ## Implicitly converts to a list! y = sorted(that) while len(x) and len(y): if x[0] == y[0]: other += 1 x.pop(0) y.pop(0) elif x[0] < y[0]: x.pop(0) else: y.pop(0) other -= exact
使用字典，我可以减less到九：
other = 0 counters = dict() for i in this: counters[i] = counters.get(i,0) + 1 for i in that: if counters.get(i,0) > 0: other += 1 counters[i] -= 1 other -= exact
（使用新的“collections.Counter”类（Python3和预定的Python 2.7？）我可以大概减less这一点;三行这里是初始化计数器集合）。
当我们find一个匹配时，减less“计数器”是非常重要的，在我们的testing中testing大于零的计数器是至关重要的。 如果给定的字母/符号出现在“this”一次和“that”两次，那么它只能被计为一次匹配。
第一种方法写起来有点麻烦（一定要小心避免边界）。 另外在几个快速基准testing（testing一百万个随机生成的字母模式对）中，第一种方法比使用字典的时间长70％。 （使用random.shuffle()生成百万对string的时间比另一方面得分慢了两倍）。
对这两种function的performance进行forms分析将是复杂的。 第一种方法有两种，所以这将是2 * O（n log（n））…并且遍历两个string中的至less一个，并且可能必须一直迭代到另一个string的末尾（最好的情况O（n），最坏的情况O（2n）） – 我在这里错误地使用了大O符号，但这只是一个粗略的估计。 第二种情况完全取决于字典的性能特征。 如果我们使用B树，那么性能将大致为O（n log（n）），而从另一个string中查找每个元素将是另一个O（n * log（n））操作。非常有效率，这些操作应该接近恒定的时间（很less有散列冲突），因此我们期望O（2n）的性能…这当然简化为O（n）。 。
纵观维基百科关于“ 精神头脑 ”的文章，我看到唐纳德·克努特（Donald Knuth）使用了一种类似于我的方法（和十年前的方法），但他又添加了一个重要的优化。 在收集剩下的每一个可能性之后，他会select哪一个可以消除下一轮的最大可能性。 我认为自己的计划有了这样的改进，并因实际原因拒绝了这个想法。 在他的情况下，他正在寻找一个最佳（math）解决scheme。 在我的情况下，我担心可玩性（在XT上，最好使用less于64KB的RAM，尽pipe我可以切换到.EXE格式并使用高达640KB）。 我想把响应时间保持在一秒或两秒钟的时间内（这对我来说很容易，但是进一步推测得分会更困难）。 （记得我在Pascal工作，在MS-DOS下…没有线程，虽然我确实实现了支持粗糙asynchronous轮询的用户界面，结果是没有必要的）
如果我今天正在写这样的东西，我会添加一个线程来做更好的select。 这可以让我在一定的时间限制内发现最好的猜测，以保证我的玩家不必为了猜测而等待太久。 当然，我的select/淘汰将在等待对手的猜测时运行。
你有没有像Raymond Hettingers的尝试 ？ 他们当然符合你的一些要求。
我想知道他的解决scheme与你的解决scheme相比
这里有一个关于MasterMind策略的很棒的网站。 作者从非常简单的MasterMind问题开始（使用数字而不是字母，忽略顺序和重复），逐渐build立一个完整的MasterMind问题（使用颜色，可以以任何顺序重复， 即使有错误的可能性在线索）。
提出的七个教程如下：
- 教程1 – 最简单的游戏设置（ 没有错误，固定顺序，不重复 ）
- 教程2 – 代码可能包含空格（ 没有错误，固定顺序，不重复 ）
- 教程3 – 提示可能包含错误（ 固定顺序，不重复 ）
- 教程4 – 游戏从中间开始（ 没有错误，固定顺序，不重复 ）
- 教程5 – 数字/颜色可以重复（ 没有错误，固定顺序，每个颜色重复最多4次 ）
- 教程6 – 以随机顺序排列的数字/颜色（ 无错误，随机顺序，不重复 ）
- 教程7 – 把它放在一起（ 没有错误，随机顺序，每个颜色重复最多4次 ）
只是以为我会贡献我的90奇怪的代码行。 我已经基于@Jim Dennis的回答，大多拿走了对称得分的暗示。 我已经实现了Minuthxalgorithm，如Knuth的Mastermind维基百科文章中所描述的那样，但有一个例外：我将下一步行动限制在当前可能解决scheme列表中，因为在每个步骤中考虑所有可能的解决scheme时，性能会严重恶化。 目前的方法给我留下了6个猜测的最坏情况下的任何组合，每个发现在一秒钟之内。
也许重要的是要注意，我对隐藏序列没有任何限制，允许任意数量的重复。
from itertools import product, tee from random import choice COLORS = 'red ', 'green', 'blue', 'yellow', 'purple', 'pink'#, 'grey', 'white', 'black', 'orange', 'brown', 'mauve', '-gap-' HOLES = 4 def random_solution(): """Generate a random solution.""" return tuple(choice(COLORS) for i in range(HOLES)) def all_solutions(): """Generate all possible solutions.""" for solution in product(*tee(COLORS, HOLES)): yield solution def filter_matching_result(solution_space, guess, result): """Filter solutions for matches that produce a specific result for a guess.""" for solution in solution_space: if score(guess, solution) == result: yield solution def score(actual, guess): """Calculate score of guess against actual.""" result = [] #Black pin for every color at right position actual_list = list(actual) guess_list = list(guess) black_positions = [number for number, pair in enumerate(zip(actual_list, guess_list)) if pair[0] == pair[1]] for number in reversed(black_positions): del actual_list[number] del guess_list[number] result.append('black') #White pin for every color at wrong position for color in guess_list: if color in actual_list: #Remove the match so we can't score it again for duplicate colors actual_list.remove(color) result.append('white') #Return a tuple, which is suitable as a dictionary key return tuple(result) def minimal_eliminated(solution_space, solution): """For solution calculate how many possibilities from S would be eliminated for each possible colored/white score. The score of the guess is the least of such values.""" result_counter = {} for option in solution_space: result = score(solution, option) if result not in result_counter.keys(): result_counter[result] = 1 else: result_counter[result] += 1 return len(solution_space) - max(result_counter.values()) def best_move(solution_space): """Determine the best move in the solution space, being the one that restricts the number of hits the most.""" elim_for_solution = dict((minimal_eliminated(solution_space, solution), solution) for solution in solution_space) max_elimintated = max(elim_for_solution.keys()) return elim_for_solution[max_elimintated] def main(actual = None): """Solve a game of mastermind.""" #Generate random 'hidden' sequence if actual is None if actual == None: actual = random_solution() #Start the game of by choosing n unique colors current_guess = COLORS[:HOLES] #Initialize solution space to all solutions solution_space = all_solutions() guesses = 1 while True: #Calculate current score current_score = score(actual, current_guess) #print '\t'.join(current_guess), '\t->\t', '\t'.join(current_score) if current_score == tuple(['black'] * HOLES): print guesses, 'guesses for\t', '\t'.join(actual) return guesses #Restrict solution space to exactly those hits that have current_score against current_guess solution_space = tuple(filter_matching_result(solution_space, current_guess, current_score)) #Pick the candidate that will limit the search space most current_guess = best_move(solution_space) guesses += 1 if __name__ == '__main__': print max(main(sol) for sol in all_solutions())
如果有人发现上述代码的任何可能的改进，我会对你的build议非常感兴趣。
要解决“最坏”的情况，而不是使用熵，我正在寻找具有最大元素数的分区，然后select这个最大值的最小值=>这会给我剩下的最小可能性当我不幸运（发生在最坏的情况下）。
这总是在5次尝试中解决标准情况，但并不是完全certificate5次尝试是真正需要的，因为可能发生下一步，更大的设置可能会给出比小的更好的结果（因为更容易区分）。
虽然对于1680年的“标准游戏”，我有一个简单的formscertificate：对于第一步，给最大数目的分区的最小值的尝试是0,0,1,1：256.播放0,0,1 ，2是不是很好：276.对于每个后续的尝试有14个结果（1没有放置和3放置是不可能的）和4放置是给一个1的分区。这意味着在最好的情况下（所有分区相同的大小）我们将得到一个最小的分区（可能性数量为1）/ 13（四舍五入，因为我们有整数，所以一定会less一些，其他更多，所以最大值被四舍五入）。
如果我申请这个：
第一次玩（0,0,1,1）后，我得到了256左。
第二次尝试后：20 =（256-1）/ 13
第三次尝试后：2 =（20-1）/ 13
然后，我别无select，只能尝试其中的一个离开第四次尝试。
如果我运气不好，则需要第五次尝试。
这certificate我们至less需要5次尝试（但不是这样就够了）。
这是我写的一个通用algorithm，它使用数字来表示不同的颜色。 Easy to change, but I find numbers to be a lot easier to work with than strings.
You can feel free to use any whole or part of this algorithm, as long as credit is given accordingly.
Please note I'm only a Grade 12 Computer Science student, so I am willing to bet that there are definitely more optimized solutions available.
Regardless, here's the code:
import random def main(): userAns = raw_input("Enter your tuple, and I will crack it in six moves or less: ") play(ans=eval("("+userAns+")"),guess=(0,0,0,0),previousGuess=[]) def play(ans=(6,1,3,5),guess=(0,0,0,0),previousGuess=[]): if(guess==(0,0,0,0)): guess = genGuess(guess,ans) else: checker = -1 while(checker==-1): guess,checker = genLogicalGuess(guess,previousGuess,ans) print guess, ans if not(guess==ans): previousGuess.append(guess) base = check(ans,guess) play(ans=ans,guess=base,previousGuess=previousGuess) else: print "Found it!" def genGuess(guess,ans): guess = [] for i in range(0,len(ans),1): guess.append(random.randint(1,6)) return tuple(guess) def genLogicalGuess(guess,previousGuess,ans): newGuess = list(guess) count = 0 #Generate guess for i in range(0,len(newGuess),1): if(newGuess[i]==-1): newGuess.insert(i,random.randint(1,6)) newGuess.pop(i+1) for item in previousGuess: for i in range(0,len(newGuess),1): if((newGuess[i]==item[i]) and (newGuess[i]!=ans[i])): newGuess.insert(i,-1) newGuess.pop(i+1) count+=1 if(count>0): return guess,-1 else: guess = tuple(newGuess) return guess,0 def check(ans,guess): base = [] for i in range(0,len(zip(ans,guess)),1): if not(zip(ans,guess)[i][0] == zip(ans,guess)[i][1]): base.append(-1) else: base.append(zip(ans,guess)[i][1]) return tuple(base) main()
Here's a link to pure Python solver for Mastermind(tm): http://code.activestate.com/recipes/496907-mastermind-style-code-breaking/ It has a simple version, a way to experiment with various guessing strategies, performance measurement, and an optional C accelerator.
The core of the recipe is short and sweet:
import random from itertools import izip, imap digits = 4 fmt = '%0' + str(digits) + 'd' searchspace = tuple([tuple(map(int,fmt % i)) for i in range(0,10**digits)]) def compare(a, b, imap=imap, sum=sum, izip=izip, min=min): count1 = [0] * 10 count2 = [0] * 10 strikes = 0 for dig1, dig2 in izip(a,b): if dig1 == dig2: strikes += 1 count1[dig1] += 1 count2[dig2] += 1 balls = sum(imap(min, count1, count2)) - strikes return (strikes, balls) def rungame(target, strategy, verbose=True, maxtries=15): possibles = list(searchspace) for i in xrange(maxtries): g = strategy(i, possibles) if verbose: print "Out of %7d possibilities. I'll guess %r" % (len(possibles), g), score = compare(g, target) if verbose: print ' ---> ', score if score[0] == digits: if verbose: print "That's it. After %d tries, I won." % (i+1,) break possibles = [n for n in possibles if compare(g, n) == score] return i+1 def strategy_allrand(i, possibles): return random.choice(possibles) if __name__ == '__main__': hidden_code = random.choice(searchspace) rungame(hidden_code, strategy_allrand)
以下是输出结果：
Out of 10000 possibilities. I'll guess (6, 4, 0, 9) ---> (1, 0) Out of 1372 possibilities. I'll guess (7, 4, 5, 8) ---> (1, 1) Out of 204 possibilities. I'll guess (1, 4, 2, 7) ---> (2, 1) Out of 11 possibilities. I'll guess (1, 4, 7, 1) ---> (3, 0) Out of 2 possibilities. I'll guess (1, 4, 7, 4) ---> (4, 0) That's it. After 5 tries, I won.
