如何解决“Mastermind”猜谜游戏？

9 回答

• 1

  关键工具：熵，贪婪，分支和束缚; Python，生成器，itertools，decorate-undecorate模式

  在回答这个问题时，我想 Build 一种有用函数的语言来探索这个问题 . 我将介绍这些功能，描述它们和它们的意图 . 最初，这些文档具有广泛的文档，使用doctest测试了小型嵌入式单元测试;作为实现测试驱动开发的绝佳方式，我不能高度赞扬这种方法 . 但是，它不能很好地转换为StackOverflow，所以我不会这样说 .

  首先，我将需要几个标准模块和 future 导入（我使用Python 2.6） .

  from __future__ import division # No need to cast to float when dividing
  import collections, itertools, math
  

  我需要一个得分功能 . 最初，这返回了一个元组（黑人，白人），但如果我使用了一个名字元组，我发现输出更清晰：

  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)
  

  为了使我的解决方案更通用，我将特定于Mastermind问题的任何内容作为关键字参数传递 . 因此我创建了一个创建这些参数的函数，并使用** kwargs语法来传递它 . 这也允许我在以后需要时轻松添加新属性 . 请注意，我允许猜测包含重复，但约束对手选择不同的颜色;为了改变这一点，我只需要在下面改变G. （如果我想在对手的秘密中允许重复，我也需要改变得分功能 . ）

  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
  

  我决定探索一个使用贪婪熵方法的求解器 . 在每一步，它计算可以从每个可能的猜测中获得的信息，并选择最具信息性的猜测 . 随着可能性的增加，这将会严重（平方）扩展，但让我们试一试！首先，我需要一种方法来计算一组概率的熵（信息） . 这只是-Σplogp . 但是，为方便起见，我将允许未标准化的输入，即不加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))
  

  那么我将如何使用这个功能呢？那么，对于一组给定的可能性，V和给定的猜测，g，我们从该猜测得到的信息只能来自评分函数：更具体地说，评分函数如何划分我们的可能性 . 我们想做一个猜测，在剩下的可能性中区别最好 - 将它们分成最大的数字小集 - 因为这意味着我们更接近答案 . 这正是上面的熵函数给出了一个数字：大量小集将得分高于少数大集 . 我们需要做的只是探索它 .

  def decisionEntropy(V, g, score):
    return entropy(collections.Counter(score(gi, g) for gi in V).values())
  

  当然，在任何给定的步骤中，我们实际拥有的是一组剩余的可能性，V，以及我们可以做出的一组可能的猜测，G，我们需要选择最大化熵的猜测 . 另外，如果几个猜测具有相同的熵，则更喜欢选择一个也可能是有效解决方案;这保证了方法将终止 . 我使用标准的python decorate-undecorate模式和内置的max方法来执行此操作：

  def bestDecision(V, G, score):
    return max((decisionEntropy(V, g, score), g in V, g) for g in G)[2]
  

  现在，我需要做的就是重复调用此函数，直到猜到正确的结果 . 我经历了这个算法的一些实现，直到我找到了一个似乎正确的算法 . 我的一些函数将希望以不同的方式处理它：一些枚举所有可能的决策序列（每个猜测对手可能做出一个），而其他人只对通过树的单个路径感兴趣（如果对手已经选择）一个秘密，我们只是想达到解决方案） . 我的解决方案是一个“懒树”，其中树的每个部分都是可以评估或不评估的生成器，允许用户避免他们不需要的昂贵计算 . 为了清晰的代码，我最后还使用了两个更多的命名元组 .

  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
  

  以下函数根据提供的评分函数评估此树中的单个路径：

  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
  

  现在可以使用它来构建Mastermind的交互式游戏，其中用户对计算机的猜测进行评分 . 玩弄这个揭示了一些有趣的事情 . 例如，最具信息性的第一个猜测是形式（黄色，黄色，蓝色，绿色），而不是（黄色，蓝色，绿色，红色） . 使用正好一半的可用颜色可获得额外信息 . 这也适用于6色3孔Mastermind - （黄色，蓝色，绿色） - 和8色5孔Mastermind - （黄色，黄色，蓝色，绿色，红色） .

  但仍有许多问题无法通过交互式求解器轻松解决 . 例如，贪婪熵方法所需的步骤数量是多少？有多少输入需要这么多步骤？为了更容易回答这些问题，我首先制作一个简单的函数，将上面的懒树变成一组通过这棵树的路径，即每个可能的秘密，一个猜测和分数列表 .

  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))
  

  找到最坏的情况很简单，找到最长的解决方案：

  def worstCaseSolution(**kwargs):
    return max((len(s), s) for s in allSolutions(**kwargs)) [1]
  

  事实证明，这个求解器总是以5步或更少的步长完成 . 五个步骤！我知道当我小时候玩Mastermind时，我经常花费比这更长的时间 . 然而，自从创建这个求解器并玩弄它以后，我已经大大改进了我的技术，即使你没有时间计算每个步骤的熵理想猜测，5个步骤确实是可实现的目标;）

  解算器将采取5个步骤的可能性有多大？它会以1步还是2步完成？为了找到它，我创建了另一个简单的小函数来计算解决方案长度分布：

  def solutionLengthDistribution(**kwargs):
    return collections.Counter(len(s) for s in allSolutions(**kwargs))
  

  对于贪婪的熵方法，允许重复：7例采取2步; 55例采取3步骤; 229例采取4步骤; 69例最多5步 .

  当然，无法保证贪婪的熵方法可以最大限度地减少最坏情况下的步数 . 我的通用语言的最后一部分是一种算法，它决定是否存在针对给定最坏情况界限的任何解决方案 . 这将告诉我们贪婪是否理想 . 为此，我采用了分支定界策略：

  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))
  

  这绝对是一个复杂的功能，因此需要更多解释 . 第一步是在猜测之后根据他们的分数对剩余的解决方案进行分区，如前所述，但这次我们不打算做，所以我们存储所有分区 . 现在我们可以直接进入其中的每一个，有效地列举整个可能的决策树的世界，但这将花费可怕的长时间 . 相反，我观察到，如果此时没有分区将剩余的解决方案划分为多于n个集合，则在将来的任何步骤中都不会有这样的划分 . 如果我们还剩下k步，那意味着我们最多可以区分在我们用完猜测之前的nk-1解决方案（在最后一步，我们必须总是正确猜测） . 因此，我们可以丢弃包含映射到这么多解决方案的分数的任何分区 . 这是接下来的两行代码 .

  最后一行代码使用Python 's any and all functions for clarity, and trying the highest-entropy decisions first to hopefully minimize runtime in the positive case. It also recurses into the largest part of the partition first, as this is the most likely to fail quickly if the decision was wrong. Once again, I use the standard decorate-undecorate pattern, this time to wrap Python'的排序函数进行递归 .

  def lowerBoundOnWorstCaseSolution(**kwargs):
    for steps in itertools.count(1):
      if solutionExists(maxsteps=steps, **kwargs):
        return steps
  

  通过越来越多的步骤重复调用solutionExists，我们得到Mastermind解决方案最坏情况下所需步骤数的严格下限：5个步骤 . 贪婪的熵方法确实是最优的 .

  出于好奇，我发明了另一种猜谜游戏，我昵称为“twoD” . 在这里，你试着猜出一对数字;在每一步，你会被告知你的答案是否正确，如果你猜到的数字不小于秘密中的相应数字，并且数字不是更大 .

  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)))
  

  对于这个游戏，贪婪的熵方法有五个步骤的最坏情况，但有一个更好的解决方案可能与四个步骤的最坏情况，证实我的直觉，近视贪婪只是巧合的Mastermind . 更重要的是，这表明我的语言是多么灵活：所有相同的方法都适用于这个新的猜谜游戏，就像Mastermind一样，让我用最少的额外编码来探索其他游戏 .

  性能怎么样？显然，在Python中实现，这段代码不会非常快 . 我也放弃了一些可能的优化，转而采用清晰的代码 .

  一个便宜的优化是观察到，在第一步中，大多数猜测基本相同:(黄色，蓝色，绿色，红色）实际上没有区别（蓝色，红色，绿色，黄色）或（橙色，黄色，红色） ，紫色） . 这大大减少了我们在第一步需要考虑的猜测次数 - 否则是游戏中最昂贵的决定 .

  但是，由于此问题的运行时间增长率很高，即使使用此优化，我也无法解决8色5孔Mastermind问题 . 相反，我将算法移植到C，保持一般结构相同，并采用按位运算来提高关键内环的性能，加速多个数量级 . 我将此作为练习留给读者:)

  Addendum, 2018: 事实证明，对于8色4洞Mastermind问题，贪婪的熵方法也不是最优的，当存在最多6个算法时，最差情况下的7个步长度！

  回复于 2024-05-06T02:42:51+08:00
• 0

  我曾在其他地方写过“2452440 " solver which is essentially "大师心灵" with words. (We each pick a word and we take turns guessing at each other's word, scoring "”（正确的字母/颜色，但错误的位置） .

  The key to solving such a problem is the realization that the scoring function is symmetric.

  换句话说，如果 score(myguess) == (1,2) 然后我可以使用相同的 score() 函数来比较我之前的猜测与任何其他可能性并消除任何不给出完全相同的分数 .

  让我举一个例子：隐藏的单词（目标）是“得分”...当前的猜测是“傻瓜”---得分为1,1（一个字母，“o”，“正确”;另一个信，'s'，是“其他地方”） . 我可以消除“猜测”这个词，因为“得分（”猜测“）（对”傻瓜“）返回（1,0）（最后的'匹配，但没有别的做） . 因此，“猜测”一词与“傻瓜”不一致，并且对某些未知单词的分数得分为（1,1） .

  因此，我现在可以浏览每五个字母单词（或五种颜色/字母/数字等的组合），并消除任何不对“傻瓜”得分1,1的东西 . 在每次迭代中执行此操作，您将非常快速地收敛到目标 . （对于五个字母的单词，我每次都能在6次尝试中获得...通常只有3或4次） . 当然，只有6000个左右的“单词”，每次猜测你都会消除接近95％的“单词” .

  注意：对于下面的讨论，我说的是五个字母"combination"而不是六种颜色的四个元素 . 适用相同的算法;然而，对于旧游戏来说问题是小了几个数量......在经典的"Master Mind"程序中，只有1296种颜色的钉子组合（6 ** 4），假设允许重复 . 导致收敛的推理线涉及一些组合学：对于五元素目标，有20个非获胜的可能得分（ n = [(a,b) for a in range(5) for b in range(6) if a+b <= 5] 如果你're curious. We would, therefore, expect that any random valid selection would have a roughly 5% chance of matching our score ... the other 95% won' t则看到所有这些得分，因此每个得分猜测都将被淘汰 . 这不会't account for possible clustering in word patterns but the real world behavior is close enough for words and definitely even closer for 2459251 rules. However, with only 6 colors in 4 slots we only have 14 possible non-winning scores so our convergence isn' （同样快） .

  对于Jotto，两个小挑战是：生成一个好的世界列表（在UNIX系统上是 awk -f 'length($0)==5' /usr/share/dict/words 或类似的）以及如果用户选择了一个不是在我们的字典中（生成每个字母组合，'aaaaa'到'zzzzz' ---这是26 ** 5 ......或~110万） . Python中的一个简单的组合生成器大约需要1分钟来生成所有这些字符串......优化的字符串应该要好得多 . （我还可以添加一个要求，即每个"word"至少有一个元音......但是这个约束没有多大帮助--- 5个元音* 5个可能的位置，然后再乘以26 ** 4个其他组合） .

  对于Master Mind，您使用相同的组合生成器......但只有4或5个“字母”（颜色） . 每个6色组合（15,625个）可以在一秒钟内生成（使用与我上面使用的相同的组合生成器） .

  如果我今天正在编写这个"Jotto"程序，例如在Python中，我会通过在后台生成所有字母组合的线程，而我仍然从字典中删除了单词（而我的对手正在给我打分，猜测等） . 当我生成它们时，我删除了所有已知的单词，拥有相对较小的可能性列表，并且针对人类玩家，我让我的网络引擎与本地守护程序进行通信，以询问与一组分数一致的序列 . 守护进程将保留一个本地生成的所有字母组合列表，并使用 select.select() 模型将可能性反馈给每个正在运行的游戏实例 - 每个将提供我的守护进程单词/分数对，我的守护进程将应用于过滤它反馈给该客户的可能性） .

  （相比之下，大约20年前，我使用Borland TurboPascal在XT上编写了我的“Jotto”版本......它可以完成每次消除迭代 - 从其编译的几千字的列表开始 - 在井中我写了一个简单的字母组合生成器（见下文）来构建它的单词列表...将结果保存到一个中等大的文件，然后用宏来运行我的文字处理器的拼写检查以删除所有“错误拼写“---然后我用另一个宏将所有剩余的行包裹在正确的标点符号中，使它们对我的数组有效的静态赋值，这是我程序的一个#include文件 . 所有这些让我构建一个独立的游戏程序“知道”几乎每个有效的英文5个字母单词;程序是.COM ---如果我没记错的话，不到50KB） .

  出于其他原因，我最近在Python中编写了一个简单的任意组合生成器 . 这是大约35行代码，我已将它发布到bitbucket.org上的“trite snippets”wiki ...它不是Python语义中的“生成器”...但是你可以实例化为无限序列的类元素的“数字”或“符号”组合（基本上以任何正整数基数计算） .

  您可以在以下位置找到它：Trite Snippets: Arbitrary Sequence Combination Generator

  对于 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() 两个序列，返回任何匹配，并取结果的长度） .

  在“其他”位置查找匹配看起来更复杂 . 如果不允许重复，那么您可以简单地使用集合来查找交叉点 .

  [在我之前编辑的这条消息中，当我意识到如何使用 zip() 进行完全匹配时，我错误地认为我们可以使用 other = len([x for x,y in zip(sorted(x), sorted(y)) if x==y]) - exact ......但是已经很晚了我累了 . 当我睡觉时，我意识到这种方法存在缺陷 . Bad, Jim! Don't post without adequate testing! (Tested several cases that happened to work)* ] .

  在过去，我使用的方法是对两个列表进行排序，比较每个列表的头部：如果头部相等，则递增计数并从两个列表中弹出新项目 . 否则在两个头中较小的一个中弹出一个新值并重试 . 只要列表为空，就会中断 .

  这确实有效;但它相当冗长 . 我能想出的最好的方法就是十几行代码：

  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
  

  使用字典我可以将其减少到大约九：

  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？）我可能会减少这一点;这里有三行初始化计数器集合） .

  当我们找到匹配时减少“计数器”是很重要的，并且在我们的测试中测试大于零的计数器是至关重要的 . 如果给定的字母/符号在“this”中出现一次而“that”出现两次则必须将其计为一次匹配 .

  第一种方法绝对有点难以编写（必须小心避免边界） . 也在一个几个快速基准测试（测试一百万个随机生成的字母模式对）第一种方法比使用字典的方法长约70％ . （另一方面，使用 random.shuffle() 生成数百万对字符串的时间是评分函数的较慢时间的两倍） .

  对这两个函数的性能进行正式分析会很复杂 . 第一种方法有两种排序，因此它将是2 * O（nlog（n））...并且它遍历两个字符串中的至少一个，并且可能必须一直迭代到另一个字符串的结尾（最好的情况O（n），最坏的情况O（2n）） - 强迫我在这里误用大O符号，但这只是一个粗略的估计 . 第二种情况完全取决于字典的性能特征 . 如果我们使用b-tree，那么性能将大致为O（nlog（n）用于创建，并且从其中的其他字符串中查找每个元素将是另一个O（n * log（n））操作 . 但是，Python字典非常高效且这些操作应该接近恒定时间（非常少的哈希冲突） . 因此我们期望大约O（2n）的性能......当然这简化为O（n） . 这大致匹配我的基准测试结果 .

  浏览一下关于“Master Mind”的维基百科文章，我看到Donald Knuth使用的方法与我的方法类似（10年前），但他添加了一个重要的优化 . 在收集了所有剩余的可能性之后，他选择了哪一个可以消除下一轮中最大数量的可能性 . 我认为这是对我自己的计划的一种改进，并且出于实际原因拒绝了这个想法 . 在他的案例中，他正在寻找最佳（数学）解决方案 . 在我的情况下，我担心可玩性（在XT上，最好使用少于64KB的RAM，尽管我可以切换到.EXE格式并使用高达640KB） . 我希望将响应时间保持在一秒或两秒的范围内（这对我的方法来说很容易，但对于进一步的投机评分来说会更加困难） . （记得我在Pascal工作，在MS-DOS下......没有线程，虽然我确实实现了对UI的粗略异步轮询的支持，结果证明是不必要的）

  如果我今天写这样的东西，我也会添加一个线程来做更好的选择 . 这将允许我在一定的时间限制内给出我发现的最佳猜测，以保证我的玩家不必等待太久我的猜测 . 当然，我的选择/淘汰将在等待对手猜测的同时进行 .

  回复于 2024-05-06T02:42:51+08:00
• 4

  你有没有看过Raymond Hettingers attempt？它们肯定符合您的一些要求 .

  我想知道他的解决方案与你的解决方案相比 .

  回复于 2024-05-06T02:42:51+08:00
• 40

  有一个关于MasterMind策略的好网站here . 作者从非常简单的MasterMind问题开始（使用数字而不是字母，忽略顺序和重复）并逐渐 Build 完整的MasterMind问题（使用颜色，可以以任何顺序重复，即使有可能出错在线索中） .

  提供的七个教程如下：

  • Tutorial 1 - The simplest game setting (no errors, fixed order, no repetition)

  • Tutorial 2 - Code may contain blank spaces (no errors, fixed order, no repetition)

  • Tutorial 3 - Hints may contain errors (fixed order, no repetition)

  • Tutorial 4 - Game started from the middle (no errors, fixed order, no repetition)

  • Tutorial 5 - Digits / colours may be repeated (no errors, fixed order, each colour repeated at most 4 times)

  • Tutorial 6 - Digits / colours arranged in random order (no errors, random order, no repetition)

  • Tutorial 7 - Putting it all together (no errors, random order, each colour repeated at most 4 times)

  回复于 2024-05-06T02:42:51+08:00
• 0

  只是想我在@Jim Dennis ' answer, mostly taking away the hint on symetric scoring. I'已经实现了由Knuth在Mastermind wikipedia article上描述的minimax算法，但有一个例外：我限制我的下一步移动到当前的可能解决方案列表，因为我发现在将所有可能的解决方案带入时，性能严重恶化每一步的帐户 . 目前的方法给我留下了最糟糕的情况，即任何组合的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())
  

  任何人都应该发现上述代码的任何可能的改进，而不是我对你的建议非常感兴趣 .

  回复于 2024-05-06T02:42:51+08:00
• 12

  为了找出“最坏”的情况，而不是使用熵，我正在寻找具有最大元素数量的分区，然后选择最小值为此最大值的尝试=>这将给出我剩余可能性的最小数量当我不幸运时（最糟糕的情况发生） .

  这总是在5次尝试中解决标准情况，但它并不是真正需要5次尝试的完整证据，因为它可能发生在下一步中更大的设置可能性给出了比较小的结果更好的结果（因为更容易区分） .

  虽然对于1680的“标准游戏”，我有一个简单的形式证明：对于第一步，给出具有最大数量的分区的最小值的尝试是0,0,1,1：256 . 播放0,0,1 ，2不是很好：276 . 对于每个后续尝试，有14个结果（1个未放置，3个放置是不可能的），4个放置给出1的分区 . 这意味着在最好的情况下（所有分区相同大小）我们将得到一个最小的最大分区（可能性的数量 - 1）/ 13（向上舍入，因为我们有整数，所以必然有些会更少，其他更多，所以最大值被四舍五入） .

  如果我申请：

  在第一次比赛（0,0,1,1）之后我剩下256分 .

  第二次尝试后：20 =（256-1）/ 13

  第三次尝试后：2 =（20-1）/ 13

  然后我别无选择，只能尝试剩下的两个中的一个进行第四次尝试 .

  如果我运气不好，需要进行第五次尝试 .

  这证明我们至少需要5次尝试（但这并不足够） .

  回复于 2024-05-06T02:42:51+08:00
• 7

  这是我写的一个通用算法，它使用数字来表示不同的颜色 . 易于更改，但我发现数字比字符串更容易使用 .

  只要相应地给予信用，您就可以随意使用此算法的任何全部或部分内容 .

  请注意我只是一名12年级的计算机科学专业的学生，所以我愿意打赌，肯定有更优化的解决方案 .

  无论如何，这是代码：

  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()
  

  回复于 2024-05-06T02:42:51+08:00
• 0

  这里是Mastermind（tm）纯Python解算器的链接：http://code.activestate.com/recipes/496907-mastermind-style-code-breaking/它有一个简单的版本，可以尝试各种猜测策略，性能测量和可选的C加速器 .

  配方的核心是短而甜的：

  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.
  

  回复于 2024-05-06T02:42:51+08:00
• 0

  我的朋友正在考虑相对简单的案例 - 8种颜色，没有重复，没有空白 .

  没有重复，不需要最大熵考虑，所有猜测都具有相同的熵，并且首先或随机猜测都可以正常工作 .

  以下是解决该变体的完整代码：

  # SET UP
  import random
  import itertools
  colors = ('red', 'orange', 'yellow', 'green', 'blue', 'indigo', 'violet', 'ultra')
  
  # ONE FUNCTION REQUIRED
  def EvaluateCode(guess, secret_code):
      key = []
      for i in range(0, 4):
          for j in range(0, 4):
              if guess[i] == secret_code[j]:
                  key += ['black'] if i == j else ['white']    
      return key
  
  # MAIN CODE
  # choose secret code
  secret_code = random.sample(colors, 4)
  print ('(shh - secret code is: ', secret_code, ')\n', sep='')
  # create the full list of permutations
  full_code_list = list(itertools.permutations(colors, 4))
  N_guess = 0
  while True:
      N_guess += 1
      print ('Attempt #', N_guess, '\n-----------', sep='')
      # make a random guess
      guess = random.choice(full_code_list)
      print ('guess:', guess)
      # evaluate the guess and get the key
      key = EvaluateCode(guess, secret_code)
      print ('key:', key)
      if key == ['black', 'black', 'black', 'black']:
          break
      # remove codes from the code list that don't match the key
      full_code_list2 = []
      for i in range(0, len(full_code_list)):
          if EvaluateCode(guess, full_code_list[i]) == key:
              full_code_list2 += [full_code_list[i]]
      full_code_list = full_code_list2
      print ('N remaining: ', len(full_code_list), '\n', full_code_list, '\n', sep='')
  print ('\nMATCH after', N_guess, 'guesses\n')
  

  回复于 2024-05-06T02:42:51+08:00