如何解决“策划者”猜谜游戏？

Question

您将如何创建一种算法来解决以下难题“ Mastermind”？

您的对手从六种颜色中选择了四种不同的颜色（黄色，蓝色，绿色，红色，橙色，紫色）。您必须猜测他们选择了哪个，以及选择了什么顺序。每次猜测之后，您的对手都会告诉您，您猜到了多少（但不是哪种）颜色在正确的位置[“黑色”]，以及多少（但不是哪种）是正确的颜色但是在错误的位置[“白人”]。如果猜对了，游戏就会结束（4个黑色，0个白色）。

例如，如果您的对手选择了（蓝色，绿色，橙色，红色），而您猜测（黄色，蓝色，绿色，红色），则将得到一个“黑色”（红色）和两个白色（红色）。蓝色和绿色）。您将获得相同的猜测分数（蓝色，橙色，红色，紫色）。

我对您会选择哪种算法以及（可选）如何将其转换为代码（最好是Python）感兴趣。我对以下编码解决方案感兴趣：

1. 清晰（易于理解）
2. 简洁
3. 高效（快速猜测）
4. 有效（解决难题的最少猜测数）
5. 灵活（可以轻松回答有关算法的问题，例如，最坏的情况是什么？）
6. 一般（可以很容易地适应Mastermind以外的其他类型的难题）

我对一个非常有效但不是非常有效的算法感到满意（前提是它不仅实现不佳！）；但是，不能灵活地，毫不费力地实施非常有效的算法。

我已经在Python中发布了自己的（详细的）解决方案，但这绝不是唯一或最佳的方法，所以请发布更多！我不希望有论文;）

Answer 1

关键工具：熵，贪婪，分支定界；Python，生成器，itertools，decorate-unecorate模式

在回答这个问题时，我想建立一种有用的函数语言来探讨这个问题。我将介绍这些功能，并描述它们及其意图。最初，这些工具具有广泛的文档，并且使用doctest对小型嵌入式单元测试进行了测试；我不能高度称赞这种方法是实现测试驱动开发的绝妙方法。但是，它不能很好地转换为StackOverflow，因此我不会以这种方式呈现。

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

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

我将需要一个计分功能。最初，这返回了一个元组（黑色，白色），但是如果我使用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)

为了使我的解决方案具有通用性，我将与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)

有时，我需要根据将函数应用于集合中每个元素的结果对集合进行 分区
。例如，可以通过函数n％2将数字1..10划分为偶数和奇数（奇数为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
decorate-undecorate模式以及内置的max方法来执行此操作：

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

现在，我要做的就是重复调用此函数，直到猜出正确的结果为止。我经历了该算法的多种实现，直到发现一个似乎正确的实现。我的几个职能部门希望以不同的方式来实现这一目标：一些职能部门列举所有可能的决策顺序（每个对手可能做出的猜测），而其他职能只对穿过树的单个路径感兴趣（如果对手已经选择了）一个秘密，而我们只是试图达成解决方案）。我的解决方案是“懒树”，其中树的每个部分都是可以评估与否的生成器，从而使用户可以避免不需要的昂贵计算。我还最终使用了另外两个namedtuple，再次是为了使代码清晰。

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孔策划者（黄色，蓝色，绿色）和8色5孔策划者（黄色，黄色，蓝色，绿色，红色）。

但是，仍有许多问题无法通过交互式求解器轻松解决。例如，贪婪熵方法最多需要多少步骤？多少输入采取了这么多步骤？为了使回答这些问题更加容易，我首先提供了一个简单的函数，该函数将上面的惰性树变成通过该树的一组路径，即，针对每个可能的秘密，列出猜测和分数。

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的所有函数进行清晰说明，并首先尝试最大熵的决策，以期在肯定的情况下最大程度地减少运行时间。它也首先递归到分区的最大部分，因为如果决策错误，这很可能会很快失败。再次，我使用标准的decorate-
unecorate模式，这一次包装了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一样工作，这使我可以用最少的额外编码来探索其他游戏。

性能如何？显然，以Python实现时，该代码的运行速度不会很快。我还放弃了一些可能的优化，以使用清晰的代码。

一种便宜的优化方法是，首先观察到，大多数猜测基本上都是相同的：（黄色，蓝色，绿色，红色）与（蓝色，红色，绿色，黄色）或（橙色，黄色，红色）确实没有区别。
，紫色）。这大大减少了我们在第一步中需要考虑的猜测数量，否则将是游戏中最昂贵的决定。

但是，由于此问题的运行时增长率很高，因此即使进行了这种优化，我也无法解决8色5孔Mastermind问题。取而代之的是，我将算法移植到C
++，使通用结构保持不变，并采用按位运算来提高关键内部循环中的性能，从而加快了多个数量级的速度。我把这留给读者练习：)

附录，2018年： 事实证明，贪婪熵方法对于8色4孔Mastermind问题也不是最佳选择，当算法最多需要6个步骤时，最坏情况下需要7步！