如何解决"Mastermind"猜谜游戏？

Question

你会怎么设计一个算法来解决这个叫“主脑”的谜题呢？

你的对手从六种颜色中（黄色、蓝色、绿色、红色、橙色、紫色）选择了四种不同的颜色。你需要猜出他们选择了哪些颜色，以及它们的顺序。每次猜完后，对手会告诉你有多少个颜色是对的并且位置也对了（我们称之为“黑色”），还有多少个颜色是对的但位置不对（我们称之为“白色”）。当你猜对了（4个黑色，0个白色）时，游戏就结束了。

举个例子，如果你的对手选择了（蓝色、绿色、橙色、红色），而你猜的是（黄色、蓝色、绿色、红色），那么你会得到一个“黑色”（因为红色对了），还有两个“白色”（因为蓝色和绿色对了但位置不对）。如果你猜的是（蓝色、橙色、红色、紫色），你也会得到同样的分数。

我想知道你会选择什么样的算法，另外（可选）你是怎么把它转化成代码的（最好是用Python）。我对代码解决方案的要求是：

1. 清晰（容易理解）
2. 简洁
3. 高效（快速做出猜测）
4. 有效（用最少的猜测次数解决谜题）
5. 灵活（能轻松回答关于算法的问题，比如最坏情况是什么？）
6. 通用（能容易适应其他类型的谜题，而不仅仅是主脑）

我对一个非常有效但不太高效的算法也可以接受（只要它不是实现得很糟糕！）；不过，一个非常高效但实现得不灵活、难以理解的算法就没什么用。

我有自己的（详细的）Python解决方案已经发过了，但这绝对不是唯一或最好的方法，所以请大家多分享！我不期待你们写一篇论文；）

Answer 1

你见过Raymond Hettinger的尝试吗？他的方案肯定能满足你的一些需求。

我很好奇他的解决方案和你的相比怎么样。

Answer 2

我曾经写过一个“Jotto”的解题程序，基本上就是用单词来玩的“Master Mind”。（我们各自选择一个单词，然后轮流猜对方的单词，得分包括“完全正确”（完全匹配）和“其他地方”（字母正确但位置错误）。

解决这个问题的关键是意识到评分函数是对称的。

换句话说，如果 score(myguess) == (1,2)，那么我可以用同样的 score() 函数来比较我之前的猜测和其他任何可能的单词，排除那些得分不完全相同的单词。

让我举个例子：假设隐藏的单词是“score”，而我当前的猜测是“fools”——得分是1,1（一个字母'o'是“完全正确”；另一个字母's'是“其他地方”）。我可以排除“guess”这个单词，因为 `score("guess") (against "fools")` 返回的是 (1,0)（最后的's'匹配，但其他都不匹配）。所以“guess”这个单词和“fools”不一致，得分也不可能是(1,1)。

因此，我现在可以遍历每一个五个字母的单词（或者五种颜色/字母/数字的组合），排除所有与“fools”得分不为1,1的单词。这样每次迭代都会快速接近目标。（对于五个字母的单词，我每次都能在6次尝试内找到答案……通常只需要3或4次）。当然，只有大约6000个“单词”，而且每次猜测几乎可以排除95%的选项。

注意：在接下来的讨论中，我说的是五个字母的“组合”，而不是四个元素的六种颜色。相同的算法适用；然而，对于旧版“Master Mind”游戏来说，问题的规模小得多……经典“Master Mind”程序中只有1296种组合（6**4），假设允许重复。导致收敛的推理涉及一些组合数学：对于五个元素的目标，有20种非获胜的可能得分（n = [(a,b) for a in range(5) for b in range(6) if a+b <= 5]，如果你感兴趣可以查看所有可能性）。因此，我们可以预期任何随机有效选择与我们的得分匹配的概率大约是5%……其余的95%不会匹配，因此在每次得分猜测中都会被排除。这并没有考虑单词模式中的可能聚类，但在实际情况下，单词的行为相当接近，而对于“Master Mind”的规则则更为接近。然而，只有6种颜色在4个位置中，我们只有14种可能的非获胜得分，所以我们的收敛速度没有那么快。

对于Jotto来说，两个小挑战是：生成一个好的单词列表（awk -f 'length($0)==5' /usr/share/dict/words 或类似的在UNIX系统上）以及如果用户选择了一个不在字典中的单词该怎么办（生成每种字母组合，从'aaaaa'到'zzzzz'——这有26 ** 5……大约110万种组合）。一个简单的组合生成器在Python中大约需要1分钟来生成所有这些字符串……一个优化过的版本应该会更快。（我还可以添加一个要求，即每个“单词”至少有一个元音……但这个限制帮助不大——5个元音 * 5个可能的位置，然后乘以26 ** 4的其他组合）。

对于Master Mind，你可以使用相同的组合生成器……但只有4或5个“字母”（颜色）。每种6色组合（15,625种）可以在不到一秒的时间内生成（使用我上面提到的组合生成器）。

如果我今天在写这个“Jotto”程序，比如用Python，我会“作弊”，在后台启动一个线程生成所有字母组合，同时我还在从字典中排除单词（当我的对手在给我打分、猜测等）。随着我生成这些组合，我也会对所有已知的猜测进行排除。因此，在我排除所有已知单词后，我会有一个相对较小的可能性列表，而在与人类玩家对战时，我通过并行处理隐藏了大部分计算延迟。（而且，如果我写一个这样的程序的网络服务器版本，我会让我的网络引擎与本地守护进程通信，以请求与一组得分一致的序列。守护进程会保持一个本地生成的所有字母组合的列表，并使用 select.select() 模型将可能性反馈给每个正在运行的游戏实例——每个实例会将单词/得分对反馈给我的守护进程，守护进程会将这些作为过滤器应用于它反馈给该客户端的可能性）。

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

出于其他原因，我最近在Python中写了一个简单的任意组合生成器。它大约有35行代码，我把它发布在我的“琐碎代码片段”维基上，地址在bitbucket.org……它不是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 来解决……但那时已经很晚了，我很累。睡了一觉后我意识到这个方法有缺陷。坏了，Jim！不要在没有充分测试的情况下发布！*（测试了几个恰好有效的案例）]

过去我使用的方法是对两个列表进行排序，比较每个列表的头部：如果头部相等，就增加计数并从两个列表中弹出新项。否则，就将较小的头部中的新值弹出，然后再试。只要其中一个列表为空就停止。

这个方法确实有效；但相对冗长。我能想到的使用这种方法的最佳代码大约有十几行：

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？）我可以进一步减少这个；这里的三行是初始化计数器集合）。

在找到匹配项时，减少“计数器”是很重要的，并且在测试中检查计数器是否大于零也是至关重要的。如果某个字母/符号在“这个”中出现一次，而在“那个”中出现两次，那么它只能算作一次匹配。

第一种方法确实有点难写（必须小心避免边界问题）。而且在几个快速基准测试中（测试一百万对随机生成的字母模式），第一种方法的耗时大约比使用字典的方法多70%。（使用 random.shuffle() 生成一百万对字符串的时间是较慢的得分函数的两倍多，另一方面）。

对这两个函数性能的正式分析会很复杂。第一种方法有两个排序，因此是 2 * O(nlog(n))……并且至少要遍历其中一个字符串，可能还需要遍历另一个字符串的末尾（最好情况 O(n)，最坏情况 O(2n)）——我在这里错误地使用了大O符号，但这只是一个粗略估计。第二种情况完全取决于字典的性能。如果我们使用b树，那么性能大约是 O(nlog(n) 用于创建和从另一个字符串中查找每个元素的操作也是 O(n*log(n))。然而，Python字典非常高效，这些操作应该接近常数时间（哈希碰撞非常少）。因此，我们可以预期性能大约是 O(2n)……这当然简化为 O(n)。这大致与我的基准测试结果相符。

浏览维基百科上关于“Master Mind”的文章，我看到Donald Knuth使用的方法与我类似（而且早了10年），但他添加了一个重要的优化。在收集所有剩余可能性后，他选择下一个回合可以排除最多可能性的那个。我考虑过将这样的增强功能添加到我自己的程序中，但出于实际原因拒绝了这个想法。在他的情况下，他在寻找一个最佳（数学）解决方案。而在我的情况下，我关心的是可玩性（在XT上，最好使用不到64KB的RAM，尽管我可以切换到.EXE格式，使用最多640KB）。我想保持响应时间在一两秒的范围内（这对我来说很简单，但如果进一步进行推测评分就会变得困难得多）。（记住，我是在MS-DOS下用Pascal工作……没有线程，尽管我确实实现了对粗略异步轮询UI的支持，但这被证明是多余的）。

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

Answer 3

关键工具：熵、贪婪、分支限界；Python、生成器、itertools、装饰-未装饰模式

在回答这个问题时，我想建立一套有用的函数来探索这个问题。我会逐一介绍这些函数，说明它们的用途。最初，这些函数有详细的文档，并且嵌入了小的单元测试，使用 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: 偶数, 1: 奇数 }）。

def partition(S, func, *args, **kwargs):
  partition = collections.defaultdict(set)
  for v in S: partition[func(v, *args, **kwargs)].add(v)
  return partition

我决定探索一种使用贪婪熵方法的求解器。在每一步，它计算每个可能猜测所能获得的信息，并选择最有信息量的猜测。随着可能性的增加，这种方法的扩展性会变差（呈二次增长），但我们还是试试看！首先，我需要一个方法来计算一组概率的熵（信息）。这就是 -∑p log p。为了方便，我允许输入不归一化的值，也就是说，它们的总和不一定等于 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 装饰-未装饰模式以及内置的 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 游戏，用户为计算机的猜测打分。玩这个游戏会发现一些有趣的事情。例如，最有信息量的第一次猜测是 (yellow, yellow, blue, green)，而不是 (yellow, blue, green, red)。通过使用正好一半的可用颜色可以获得额外的信息。这对于 6 色 3 孔 Mastermind 也是适用的——(yellow, blue, green)——以及 8 色 5 孔 Mastermind——(yellow, yellow, blue, green, red)。

但仍然有很多问题无法通过互动求解器轻松回答。例如，贪婪熵方法需要的最多步骤是多少？有多少输入需要这么多步骤？为了更容易回答这些问题，我首先生成一个简单的函数，将上面的懒惰树转换为这棵树中的一组路径，也就是说，对于每个可能的秘密，生成一个猜测和得分的列表。

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 步，这意味着我们最多可以在用完猜测之前区分 n^k-1 个解决方案（在最后一步，我们必须始终正确猜测）。因此，我们可以丢弃任何映射到超过这个数量解决方案的得分的划分。这是接下来的两行代码。

最后一行代码进行递归，使用 Python 的 any 和 all 函数以便于理解，并优先尝试最高熵的决策，以希望在正面情况下最小化运行时间。它还首先递归到划分中最大的部分，因为如果决策错误，这部分最有可能快速失败。再次使用标准的装饰-未装饰模式，这次是为了包装 Python 的sorted函数。

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 实现，这段代码不会特别快。我也放弃了一些可能的优化，以便于代码的清晰。

一个简单的优化是观察到，在第一步，大多数猜测基本上是相同的：(yellow, blue, green, red) 实际上与 (blue, red, green, yellow) 或 (orange, yellow, red, purple) 没有什么不同。这大大减少了我们在第一步需要考虑的猜测数量——否则这将是游戏中最耗时的决策。

然而，由于这个问题的运行时间增长率很大，我无法解决 8 色 5 孔的 Mastermind 问题，即使有这个优化。相反，我将算法移植到 C++，保持大致结构不变，并使用位运算来提升关键内循环的性能，速度提高了几个数量级。我把这个留给读者作为练习 :)

附录，2018：结果表明，贪婪熵方法在 8 色 4 孔的 Mastermind 问题上也不是最优的，最坏情况长度为 7 步，而存在一个最多 6 步的算法！