你会如何创建一个算法来解决以下的难题，智多星？

How would you create an algorithm to solve the following puzzle, "Mastermind"?

您的对手选择了四种不同的颜色从一组六（黄，蓝，绿，红，橙，紫）。你必须猜测，他们都选择和顺序。每次猜测之后，你的对手会告诉你如何你猜对了颜色的许多（但不是这）是正确的颜色在正确的地方[黑人]多少（而不是哪些）是正确的颜色，但在错误的地方[白人。当你猜对了（4黑人，白人0）时，游戏结束。

Your opponent has chosen four different colours from a set of six (yellow, blue, green, red, orange, purple). You must guess which they have chosen, and in what order. After each guess, your opponent tells you how many (but not which) of the colours you guessed were the right colour in the right place ["blacks"] and how many (but not which) were the right colour but in the wrong place ["whites"]. The game ends when you guess correctly (4 blacks, 0 whites).

例如，如果你的对手选择（蓝色，绿色，橙色，红色），你猜（黄色，蓝色，绿色，红色），你会得到一个黑（为红色），和两个白人（用于蓝色和绿色）。你会得到相同的分数猜测（蓝色，橙色，红色，紫色）。

For example, if your opponent has chosen (blue, green, orange, red), and you guess (yellow, blue, green, red), you will get one "black" (for the red), and two whites (for the blue and green). You would get the same score for guessing (blue, orange, red, purple).

我感兴趣的是什么，你会选择算法和（可选），你怎么它转换成code（preferably的Python）。我感兴趣的是codeD的解决方案是：

I'm interested in what algorithm you would choose, and (optionally) how you translate that into code (preferably Python). I'm interested in coded solutions that are:

我很高兴有一个算法，是非常有效的，但不是很有效（只要它不只是执行不力！）;然而，一成不变地和impenetrably实现了一个非常高效的算法是不使用。

I'm happy with an algorithm that's very effective but not very efficient (provided it's not just poorly implemented!); however, a very efficient and effective algorithm implemented inflexibly and impenetrably is not of use.

我在Python我自己的（详细）的解决方案，我已经发布，但是这绝不是唯一或最好的办法，所以请发布更多！我不期待的作文;）

I have my own (detailed) solution in Python which I have posted, but this is by no means the only or best approach, so please post more! I'm not expecting an essay ;)

推荐答案

主要工具：熵，贪婪，分支定界;蟒蛇，发电机，itertools，装饰，去除装饰图案

Key tools: entropy, greediness, branch-and-bound; Python, generators, itertools, decorate-undecorate pattern

在回答这个问题之前，我想建立了有用的功能的语言来探讨问题。我将通过这些功能，描述了他们和他们的意图。原来，这些有着丰富的文档，用小型的嵌入式单元测试使用文档测试测试;我不能称赞这种方法高度不够作为一个辉煌的方式来实现测试驱动开发。但是，它并没有很好的转化为计算器，所以我不会present这样说。

In answering this question, I wanted to build up a language of useful functions to explore the problem. I will go through these functions, describing them and their intent. Originally, these had extensive docs, with small embedded unit tests tested using doctest; I can't praise this methodology highly enough as a brilliant way to implement test-driven-development. However, it does not translate well to StackOverflow, so I will not present it this way.

首先，我会需要几个标准模块和未来进口（我使用Python 2.6的工作）。

Firstly, I will be needing several standard modules and future imports (I work with Python 2.6).

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

我需要一个计分函数。原来，这个返回一个元组（黑人，白人），但我发现输出更清晰一点，如果我用了namedtuple：

I will need a scoring function. Originally, this returned a tuple (blacks, whites), but I found output a little clearer if I used a 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)

为了让我的解决方案一般情况下，我通过在特定的智多星问题作为关键字参数任何东西。因此，我做了，一旦创建这些参数的函数，并使用** kwargs语法各地传递。这也让我可以轻松地添加新的属性，如果我以后需要他们。请注意，我允许猜测包含重复，但限制对手挑不同的颜色;要改变这种状况，我只需要改变下面-G。 （如果我想允许在对手的秘密重复，我需要改变计分函数。）

To make my solution general, I pass in anything specific to the Mastermind problem as keyword arguments. I have therefore made a function that creates these arguments once, and use the **kwargs syntax to pass it around. This also allows me to easily add new attributes if I need them later. Note that I allow guesses to contain repeats, but constrain the opponent to pick distinct colours; to change this, I only need change G below. (If I wanted to allow repeats in the opponent's secret, I would need to change the scoring function as well.)

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：胜算}）。

Sometimes I will need to partition a set based on the result of applying a function to each element in the set. For instance, the numbers 1..10 can be partitioned into even and odd numbers by the function n % 2 (odds give 1, evens give 0). The following function returns such a partition, implemented as a map from the result of the function call to the set of elements that gave that result (e.g. { 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

我决定去探索使用的贪婪的熵方法的求解器。在每一个步骤，它计算，可以从每个可能的猜测而获得的信息，并选择最翔实猜测。由于可能的数量的增长，这将严重缩放（二次），但是让我们给它一个试试吧！首先，我需要一种方法来计算一组概率的熵（信息）。这仅仅是-Σp日志页。为方便起见，不过，我会允许将那些不归，也就是说加起来也不到1：

I decided to explore a solver that uses a greedy entropic approach. At each step, it calculates the information that could be obtained from each possible guess, and selects the most informative guess. As the numbers of possibilities grow, this will scale badly (quadratically), but let's give it a try! First, I need a method to calculate the entropy (information) of a set of probabilities. This is just -∑p log p. For convenience, however, I will allow input that are not normalized, i.e. do not add up to 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，我们从猜测得到的信息只能来自打分功能：更具体地说，是如何评分功能分区我们组的可能性。我们要区分最其余possibilites之间的猜测 - 将其划分为数量最多的小集合 - 因为这意味着我们更接近答案。这正是熵功能上面放一个数字：大量的小套将比分不是少数大型成套高。我们需要做的是下探入。

So how am I going to use this function? Well, for a given set of possibilities, V, and a given guess, g, the information we get from that guess can only come from the scoring function: more specifically, how that scoring function partitions our set of possibilities. We want to make a guess that distinguishes best among the remaining possibilites — divides them into the largest number of small sets — because that means we are much closer to the answer. This is exactly what the entropy function above is putting a number to: a large number of small sets will score higher than a small number of large sets. All we need to do is plumb it in.

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

当然，在任何给定的步骤其实我们都会有是一组剩下的可能性，V，和一组可能的猜测，我们可以做，G，我们将需要选择最大化熵的猜测。此外，如果几个猜测具有相同的熵，preFER挑一其也是一个有效的解决方案;这保证了方法将终止。我同时使用标准Python装饰，去除装饰图案内置最大的方法来做到这一点：

Of course, at any given step what we will actually have is a set of remaining possibilities, V, and a set of possible guesses we could make, G, and we will need to pick the guess which maximizes the entropy. Additionally, if several guesses have the same entropy, prefer to pick one which could also be a valid solution; this guarantees the approach will terminate. I use the standard python decorate-undecorate pattern together with the built-in max method to do this:

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

现在我需要做的就是反复调用此函数，直到正确的结果猜测。我经历了一些算法的实现，直到我发现了一个似乎正确的。我的几个功能将要以不同的方式接近这一点：一些列举的决定所有可能的序列（每猜对手可能做出），而另一些则只能通过树感兴趣的单一路径（如果对手已经选择一个秘密，我们只是想到达的解决方案）。我的解决办法是一种懒惰树，其中树的每个部分是，可以评价或不是，允许用户避免昂贵的计算它们将不再需要一台发电机。我也结束了使用两个namedtuples，再次清晰code。

Now all I need to do is repeatedly call this function until the right result is guessed. I went through a number of implementations of this algorithm until I found one that seemed right. Several of my functions will want to approach this in different ways: some enumerate all possible sequences of decisions (one per guess the opponent may have made), while others are only interested in a single path through the tree (if the opponent has already chosen a secret, and we are just trying to reach the solution). My solution is a "lazy tree", where each part of the tree is a generator that can be evaluated or not, allowing the user to avoid costly calculations they won't need. I also ended up using two more namedtuples, again for clarity of code.

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

下面的函数计算的基础上所提供的计分函数，通过此树的单一路径，

The following function evaluates a single path through this tree, based on a supplied scoring function:

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

此，现在可以用于构建策划的互动游戏，其中用户分数计算机的猜测。与此玩耍揭示了一些有趣的事情。例如，信息量最大的第一猜测的形式为（黄，黄，蓝，绿），而不是（黄，蓝，绿，红）。额外信息是由恰好有一半可用的颜色获得。这同样适用于6色3孔策划 - （黄，蓝，绿） - 和8-色5孔策划 - （黄，黄，蓝，绿，红）

This can now be used to build an interactive game of Mastermind where the user scores the computer's guesses. Playing around with this reveals some interesting things. For example, the most informative first guess is of the form (yellow, yellow, blue, green), not (yellow, blue, green, red). Extra information is gained by using exactly half the available colours. This also holds for 6-colour 3-hole Mastermind — (yellow, blue, green) — and 8-colour 5-hole Mastermind — (yellow, yellow, blue, green, red).

但也有不容易与互动式求解回答仍然有很多问题。举例来说，什么是最数需要的贪婪熵的方法步骤是什么？有多少投入采取这么多步骤？为了回答这些问题比较容易，我第一次产生一个简单的函数，通过这棵树变成了上面的树懒成一组路径，即对于每一个可能的秘密，猜测和分数的列表。

But there are still many questions that are not easily answered with an interactive solver. For instance, what is the most number of steps needed by the greedy entropic approach? And how many inputs take this many steps? To make answering these questions easier, I first produce a simple function that turns the lazy tree of above into a set of paths through this tree, i.e. for each possible secret, a list of guesses and scores.

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

查找最坏的情况是寻找最长溶液的一个简单的事情：

Finding the worst case is a simple matter of finding the longest solution:

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

事实证明，该解算器将始终完整的5级或更少。五步骤！我知道，当我打主谋作为一个孩子，我常常花的时间比这一点。然而，因为创建该解算器，用它玩的时候，我有很大的提高我的技术，和5个步骤的确，即使你没有时间来计算entropically理想的猜测在每一步一个可以实现的目标;）

It turns out that this solver will always complete in 5 steps or fewer. Five steps! I know that when I played Mastermind as a child, I often took longer than this. However, since creating this solver and playing around with it, I have greatly improved my technique, and 5 steps is indeed an achievable goal even when you don't have time to calculate the entropically ideal guess at each step ;)

它是如何可能的解算器将采取5个步骤？他会不会结束在1或2，步骤是什么？要查找出来，我创建了另一个简单的小函数，计算解决方案长度分布：

How likely is it that the solver will take 5 steps? Will it ever finish in 1, or 2, steps? To find that out, I created another simple little function that calculates the solution length distribution:

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

有关贪婪的熵的方法，用重复允许7例采取两个步骤; 55箱子采取3个步骤; 229箱子采取4个步骤; 69例采取的5个步骤的最大值。

For the greedy entropic approach, with repeats allowed: 7 cases take 2 steps; 55 cases take 3 steps; 229 cases take 4 steps; and 69 cases take the maximum of 5 steps.

当然，也不能保证贪婪的熵方法最小化的步骤，最坏情况下的数字。我的通用语言的最后部分是一种算法，判定是否存在的对于给定的最坏情况下的结合的任何的解决方案。这将告诉我们，贪婪的熵是否理想与否。要做到这一点，我采用一个分支，并结合策略：

Of course, there's no guarantee that the greedy entropic approach minimizes the worst-case number of steps. The final part of my general-purpose language is an algorithm that decides whether or not there are any solutions for a given worst-case bound. This will tell us whether greedy entropic is ideal or not. To do this, I adopt a branch-and-bound strategy:

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 解决方案之前，我们用完猜​​测（在最后一步，我们必须始终猜）。因此，我们可以丢弃包含映射到一个得分超过这么多的解决方案的任何分区。这是接下来的两行code。

This is definitely a complex function, so a bit more explanation is in order. The first step is to partition the remaining solutions based on their score after a guess, as before, but this time we don't know what guess we're going to make, so we store all partitions. Now we could just recurse into every one of these, effectively enumerating the entire universe of possible decision trees, but this would take a horrifically long time. Instead I observe that, if at this point there is no partition that divides the remaining solutions into more than n sets, then there can be no such partition at any future step either. If we have k steps left, that means we can distinguish between at most nk-1 solutions before we run out of guesses (on the last step, we must always guess correctly). Thus we can discard any partitions that contain a score mapped to more than this many solutions. This is the next two lines of code.

的code最后一行做递归。它还递归到该分区的最大部分第一，因为这是最容易迅速失败，如果决定是错误的。再一次，我用的是标准的装修，去除装饰图案，这一次换Python的排序的功能。

The final line of code does the recursion, using 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's sorted function.

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

通过反复调用solutionExists与越来越多的步骤，我们得到了严格的下界的需要在最坏的情况下为一个策划溶液步骤的数目：5的步骤。贪心的熵的做法的确是最优的。

By calling solutionExists repeatedly with an increasing number of steps, we get a strict lower bound on the number of steps needed in the worst case for a Mastermind solution: 5 steps. The greedy entropic approach is indeed optimal.

出于好奇，我还发明了猜谜游戏，这是我绰号数组twoD。在此，尝试猜对数字;在每一步，你就会得到告诉如果你的答案是正确的，如果你猜的数字是不低于相应的人的秘密少，如果数字是没有更大的。

Out of curiosity, I invented another guessing game, which I nicknamed "twoD". In this, you try to guess a pair of numbers; at each step, you get told if your answer is correct, if the numbers you guessed are no less than the corresponding ones in the secret, and if the numbers are no greater.

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

对于这场比赛，贪婪的熵方法具有五个步骤最坏的情况，但有一个更好的解决方案可能有四个步骤最坏的情况，证实我的直觉是短视贪婪只是巧合理想的主谋。更重要的是，这已经展示了如何灵活我的语言是：一样的策划都是一样的工作方法，为这个新的猜谜游戏，让我探索其他游戏以最小的额外的编码

For this game, the greedy entropic approach has a worst case of five steps, but there is a better solution possible with a worst case of four steps, confirming my intuition that myopic greediness is only coincidentally ideal for Mastermind. More importantly, this has shown how flexible my language is: all the same methods work for this new guessing game as did for Mastermind, letting me explore other games with a minimum of extra coding.

怎么样的表现？很显然，在Python正在实施，这code未将是极快的。我也放弃了一些可能的优化有利于明确code。

What about performance? Obviously, being implemented in Python, this code is not going to be blazingly fast. I've also dropped some possible optimizations in favour of clear code.

一个便宜的优化是观察到，在第一个举动，大部分的猜测基本相同：（黄，蓝，绿，红）从（蓝，红，绿，黄），或（橙色真的没有什么不同，黄色，红色，紫色）。这大大减少了，我们需要考虑在第一步骤猜测的数 - 否则中最昂贵的决定在游戏

One cheap optimization is to observe that, on the first move, most guesses are basically identical: (yellow, blue, green, red) is really no different from (blue, red, green, yellow), or (orange, yellow, red, purple). This greatly reduces the number of guesses we need consider on the first step — otherwise the most costly decision in the game.

不过，因为这个问题的大量运行时的增长速度，我是不是能够解决的8色，5孔策划的问题，即使有这样的优化。相反，我移植的算法C ++，保持总体结构相同，采用位运算来提高性能，在关键的内部循环，对几个数量级的加速比。在我离开这个作为一个练习留给读者：）

However, because of the large runtime growth rate of this problem, I was not able to solve the 8-colour, 5-hole Mastermind problem, even with this optimization. Instead, I ported the algorithms to C++, keeping the general structure the same and employing bitwise operations to boost performance in the critical inner loops, for a speedup of many orders of magnitude. I leave this as an exercise to the reader :)