你将如何创建一个算法来解决以下难题,"Mastermind"？
你的对手选择了六种不同的颜色(黄色,蓝色,绿色,红色,橙色,紫色).你必须猜测他们选择了哪个,以及以什么顺序.在每次猜测之后,你的对手会告诉你你猜到的颜色中有多少(但没有哪种)是正确的颜色["黑色"]和多少(但不是哪个)是正确的颜色但是在错误的地方[ "白色"].当你猜对了时,游戏结束(4个黑人,0个白人).
例如,如果您的对手选择了(蓝色,绿色,橙色,红色),并且您猜测(黄色,蓝色,绿色,红色),您将获得一个"黑色"(红色)和两个白色(用于蓝色和绿色).猜测会得到相同的分数(蓝色,橙色,红色,紫色).
我对您选择的算法感兴趣,并且(可选)如何将其转换为代码(最好是Python).我对以下编码解决方案很感兴趣:
清楚(容易理解)
简洁
高效(快速猜测)
有效(解决难题的猜测次数最少)
灵活(可以轻松回答有关算法的问题,例如最糟糕的情况是什么？)
一般(可以很容易地适应其他类型的拼图而不是Mastermind)
我很满意一种非常有效但效率不高的算法(前提是它不仅实现得不好!); 然而,一种非常有效且无效的算法实施起来是不可用的.
我已经发布了我自己的(详细)Python解决方案,但这绝不是唯一或最好的方法,所以请发布更多!我不期待一篇文章;)
关键工具:熵,贪婪,分支和束缚; Python,生成器,itertools,decorate-undecorate模式
在回答这个问题时,我想建立一种有用函数的语言来探索这个问题.我将介绍这些功能,描述它们和它们的意图.最初,这些文档具有广泛的文档,使用doctest测试了小型嵌入式单元测试; 作为实现测试驱动开发的绝佳方式,我不能高度赞扬这种方法.但是,它不能很好地转换为StackOverflow,所以我不会这样说.
首先,我将需要几个标准模块和未来的导入(我使用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个步骤,这意味着我们可以在我们用完猜测之前区分最多n个k-1解决方案(在最后一步,我们必须总是正确猜测).因此,我们可以丢弃包含映射到这么多解决方案的分数的任何分区.这是接下来的两行代码.
最后一行代码使用Python的any和all函数进行递归,并首先尝试最高熵决策,以期在正面情况下最小化运行时间.它还首先递归到分区的最大部分,因为如果决定错误,最有可能很快失败.再次,我使用标准的decorate-undecorate模式,这次包装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孔策划的问题,即使有这样的优化.相反,我将算法移植到C++,保持一般结构相同,并采用按位运算来提高关键内循环的性能,加速数个数量级.我将此作为练习留给读者:)
附录,2018年:事实证明,对于8色4洞Mastermind问题,贪婪的熵方法也不是最优的,当存在最多6个算法时,最差情况下的长度为7步!
我曾经写过一个" Jotto "求解器,它基本上是用语言" 掌心 ".(我们每个人都选择一个单词,我们轮流猜测对方的单词,评分"正确"(精确)匹配和"其他地方"(正确的字母/颜色,但错误的位置).
解决这个问题的关键是认识到评分函数是对称的.
换句话说,如果score(myguess) == (1,2)那时我可以使用相同的score()功能来比较我之前的猜测与任何其他可能性,并消除任何不给出完全相同的分数.
让我举一个例子:隐藏的单词(目标)是"得分"...当前的猜测是"傻瓜"---得分为1,1(一个字母,"o","正确";另一个信,'s',是"其他地方").我可以消除"猜测"这个词,因为"得分("猜测")(对"傻瓜")返回(1,0)(最后的'匹配,但没有别的做).因此,"猜测"一词与"傻瓜"不一致,并且对某些未知单词的分数得分为(1,1).
因此,我现在可以浏览每五个字母单词(或五种颜色/字母/数字等的组合),并消除任何不对"傻瓜"得分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"规则而言,这些词语肯定更接近.但是,在4个插槽中只有6种颜色我们只有14种可能的非获胜分数,所以我们的收敛速度不是那么快.
对于Jotto来说,两个小的挑战是:生成一个好的世界列表(awk -f 'length($0)==5' /usr/share/dict/words或类似于UNIX系统)以及如果用户选择了一个不在我们的字典中的单词怎么办(生成每个字母组合,'aaaaa'到'zzzzz' ---这是26**5 ......或~1.1百万).Python中的一个简单的组合生成器大约需要1分钟来生成所有这些字符串......优化的字符串应该要好得多.(我还可以添加一个要求,即每个"单词"至少有一个元音...但这个约束没有多大帮助--- 5个元音*5个可能的位置,然后乘以26**4个其他组合) .
对于Master Mind,您使用相同的组合生成器......但只有4或5个"字母"(颜色).每个6色组合(15,625个)可以在一秒钟内生成(使用与我上面使用的相同的组合生成器).
如果我今天正在编写这个"Jotto"程序,例如在Python中,我会通过在后台生成所有字母组合的线程来"欺骗",而我仍然从字典中删除了单词(而我的对手正在给我打分,猜测等).当我生成它们时,我也会消除所有猜测到目前为止.因此,在我消除了所有已知单词之后,我会有一个相对较小的可能性列表,并且对于一个人类玩家,我通过与它们的输入并行地"隐藏"了我的大部分计算滞后.(并且,如果我编写了这样一个程序的Web服务器版本,我会让我的Web引擎与本地守护进程通信,要求获得与一组分数一致的序列.守护进程将保留所有字母组合的本地生成列表.将使用一个select.select()模型将可能性反馈给每个正在运行的游戏实例 - 每个都将提供我的守护进程单词/分数对,我的守护进程将应用它作为对它反馈给该客户端的可能性的过滤器).
(相比之下,大约20年前,我使用Borland TurboPascal在XT上编写了我的"Jotto"版本......它可以完成每次消除迭代 - 从其编译的几千字的列表开始 - 在井中我写了一个简单的字母组合生成器(见下文)来构建它的单词列表...将结果保存到一个中等大的文件,然后用宏来运行我的文字处理器的拼写检查以删除所有"错误拼写"---然后我用另一个宏将所有剩余的行包裹在正确的标点符号中,使它们对我的数组有效的静态赋值,这是我程序的一个#include文件.所有这些让我构建一个独立的游戏程序"知道"几乎每个有效的英文5个字母单词;程序是.COM ---如果我没记错的话,不到50KB).
出于其他原因,我最近在Python中编写了一个简单的任意组合生成器.这是大约35行代码,我已将它发布到bitbucket.org上的"trite snippets"wiki ...它不是Python语义中的"生成器"...但是你可以实例化为无限序列的类元素的"数字"或"符号"组合(基本上以任何正整数基数计算).
您可以在以下位置找到它:Trite Snippets:任意序列组合生成器
对于我们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......但是已经很晚了我累了.当我睡觉时,我意识到这种方法存在缺陷. 吉姆,不好!如果没有足够的测试,请不要发布!*(测试了几个恰好工作的案例) ].
在过去,我使用的方法是对两个列表进行排序,比较每个列表的头部:如果头部相等,则递增计数并从两个列表中弹出新项目.否则在两个头中较小的一个中弹出一个新值并重试.只要列表为空,就会中断.
这确实有效; 但它相当冗长.我能想出的最好的方法就是十几行代码:
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(n log(n))...并且它遍历两个字符串中的至少一个,并且可能必须一直迭代到另一个字符串的末尾(最好的情况是O(n),最坏的情况是O(2n)) - 强迫我在这里误用了大O符号,但这只是一个粗略的估计.第二种情况完全取决于字典的性能特征.如果我们使用b-tree,那么性能大致为O(n log(n)用于创建,并且从其中的其他字符串中查找每个元素将是另一个O(n*log(n))操作.但是,Python字典是非常有效,这些操作应该接近恒定时间(非常少的哈希冲突).因此我们期望大约O(2n)的性能...当然简化为O(n).这大致匹配我的基准测试结果.
浏览维基百科关于" 大师心灵 "的文章我看到唐纳德克努特使用的方法与我的方法类似(10年前),但他增加了一个重要的优化.在收集了所有剩余的可能性之后,他选择了哪一个可以消除下一轮中最大数量的可能性.我认为这是对我自己的计划的这种改进,并且出于实际原因拒绝了这个想法.在他的案例中,他正在寻找最佳(数学)解决方案.在我的情况下,我担心可玩性(在XT上,最好使用少于64KB的RAM,尽管我可以切换到.EXE格式并使用高达640KB).我希望将响应时间保持在一秒或两秒的范围内(这对我的方法来说很容易,但对于进一步的投机评分来说会更加困难).(记得我在Pascal工作,在MS-DOS下......没有线程,虽然我确实实现了对UI的粗略异步轮询的支持,结果证明是不必要的)
如果我今天写这样的东西,我也会添加一个线程来做更好的选择.这将允许我在一定的时间限制内给出我发现的最佳猜测,以保证我的玩家不必等待太久我的猜测.当然,我的选择/淘汰将在等待对手猜测的同时进行.
你有没有看过Raymond Hettingers的尝试？它们肯定符合您的一些要求.
我想知道他的解决方案与你的解决方案相比.
京公网安备 11010802040832号 | 京ICP备19059560号-6 