Mik*_*ike 4 python algorithm minimax
我试图在python中实现Donald Knuth的算法,用于在不超过5个动作中进行密码破解.我已经多次检查了我的代码,它似乎遵循算法,如下所述:http: //en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm
但是,我知道一些秘密需要7甚至8个动作来完成.这是代码:
#returns how many bulls and cows there are
def HowManyBc(guess,secret):
invalid=max(guess)+1
bulls=0
cows=0
r=0
while r<4:
if guess[r]==secret[r]:
bulls=bulls+1
secret[r]=invalid
guess[r]=invalid
r=r+1
r=0
while r<4:
p=0
while p<4:
if guess[r]==secret[p] and guess[r]!=invalid:
cows=cows+1
secret[p]=invalid
break
p=p+1
r=r+1
return [bulls,cows]
# sends every BC to its index in HMList
def Adjustment(BC1):
if BC1==[0,0]:
return 0
elif BC1==[0,1]:
return 1
elif BC1==[0,2]:
return 2
elif BC1==[0,3]:
return 3
elif BC1==[0,4]:
return 4
elif BC1==[1,0]:
return 5
elif BC1==[1,1]:
return 6
elif BC1==[1,2]:
return 7
elif BC1==[1,3]:
return 8
elif BC1==[2,0]:
return 9
elif BC1==[2,1]:
return 10
elif BC1==[2,2]:
return 11
elif BC1==[3,0]:
return 12
elif BC1==[4,0]:
return 13
# sends every index in HMList to its BC
def AdjustmentInverse(place):
if place==0:
return [0,0]
elif place==1:
return [0,1]
elif place==2:
return [0,2]
elif place==3:
return [0,3]
elif place==4:
return [0,4]
elif place==5:
return [1,0]
elif place==6:
return [1,1]
elif place==7:
return [1,2]
elif place==8:
return [1,3]
elif place==9:
return [2,0]
elif place==10:
return [2,1]
elif place==11:
return [2,2]
elif place==12:
return [3,0]
elif place==13:
return [4,0]
# gives minimum of positive list without including its zeros
def MinimumNozeros(List1):
minimum=max(List1)+1
for item in List1:
if item!=0 and item<minimum:
minimum=item
return minimum
#list with all possible guesses
allList=[]
for i0 in range(0,6):
for i1 in range(0,6):
for i2 in range(0,6):
for i3 in range(0,6):
allList.append([i0,i1,i2,i3])
TempList=[[0,0,5,4]]
for secret in TempList:
guess=[0,0,1,1]
BC=HowManyBc(guess[:],secret[:])
counter=1
optionList=[]
for i0 in range(0,6):
for i1 in range(0,6):
for i2 in range(0,6):
for i3 in range(0,6):
optionList.append([i0,i1,i2,i3])
while BC!=[4,0]:
dummyList=[] #list with possible secrets for this guess
for i0 in range(0,6):
for i1 in range(0,6):
for i2 in range(0,6):
for i3 in range(0,6):
opSecret=[i0,i1,i2,i3]
if HowManyBc(guess[:],opSecret[:])==BC:
dummyList.append(opSecret)
List1=[item for item in optionList if item in dummyList]
optionList=List1[:] # intersection of optionList and dummyList
item1Max=0
for item1 in allList:
ListBC=[] # [list of all [bulls,cows] in optionList
for item2 in optionList:
ListBC.append(HowManyBc(item1[:],item2[:]))
HMList=[0]*14 # counts how many B/C there are for item2 in optionList
for BC1 in ListBC:
index=Adjustment(BC1)
HMList[index]=HMList[index]+1
m=max(HMList)#maximum [B,C], more left - less eliminated (min in minimax)
maxList=[i for i, j in enumerate(HMList) if j == m]
maxElement=maxList[0] #index with max
possibleGuess=[]
if m>item1Max: #max of the guesses, the max in minimax
item1Max=m
possibleGuess=[i[:] for i in optionList if AdjustmentInverse(maxElement)==HowManyBc(item1[:],i[:])]
nextGuess=possibleGuess[0][:]
guess=nextGuess[:]
BC=HowManyBc(guess[:],secret[:])
counter=counter+1
我明白了:
对于[5,3,3,4]计数器是7
对于[5,4,4,5]计数器是8
如果有人可以提供帮助,我会非常感激!
谢谢,迈克
Gar*_*ees 12
有四个错误.
这条评论错误:
m=max(HMList)#maximum [B,C], more left - less eliminated (min in minimax)
这实际上是极小极大值中的"最大值"(应该从调用中清楚max).您试图找到最小化产生相同评估的可能秘密组的最大大小的猜测.在这里,我们找到了组的最大大小,因此这是"最大".
这个错误导致你做出这个:
if m>item1Max: #max of the guesses, the max in minimax
在这里你需要采取最小值,而不是最大值.
在以下几行中,您选择其中的第一项optionList将生成相同的评估item1:
possibleGuess=[i[:] for i in optionList if AdjustmentInverse(maxElement)==HowManyBc(item1[:],i[:])]
nextGuess=possibleGuess[0][:]
但那是不对的:我们想要的猜测是item1,而不是其他猜测会产生相同的评价!
最后,您没有正确处理optionList只有一个剩余项目的情况.在这种情况下,所有可能的猜测同样善于区分这个项目,因此minimax程序不区分猜测.在这种情况下,你应该猜测optionList[0].
变量名称选择不当.例如,是什么item1？这是你正在评估的猜测,所以它肯定会被称为类似的东西possible_guess？我怀疑你上面的错误§1.3部分是由于变量名称的选择不当引起的.
有大量不必要的复制.你的所有[:]都是毫无意义的,可以删除.该变量List1也没有意义(为什么不只是分配给optionList？),因为它nextGuess(不只是分配给guess？)
你构建dummyList的所有可能的秘密都与最后一次猜测相匹配,但是你扔掉了所有dummyList不在的东西optionList.那么为什么不循环optionList并保持匹配的条目呢？像这样:
optionList = [item for item in optionList if HowManyBc(guess, item)==BC]
您构建了一个表格HMList,用于计算每种公牛和奶牛模式的出现次数.你已经注意到这样一个事实:有14个可能的(牛,牛)对,所以你已经编写了函数Adjustment并AdjustmentInverse在(bull,cow)对和它们在列表中的索引之间来回映射.
如果采用数据驱动方法并使用内置方法,这些函数可以有更简单的实现list.index:
# Note that (3, 1) is not possible.
EVALUATIONS = [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1),
(1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (3, 0), (4, 0)]
def Adjustment(evaluation):
return EVALUATIONS.index(evaluation)
def AdjustmentInverse(index):
return EVALUATIONS[index]
但在修正上面的错误§1.3之后,你不再需要AdjustmentInverse了.Adjustment如果你把计数保存在一个collections.Counter而不是列表中,就可以避免.所以代替:
HMList=[0]*14 # counts how many B/C there are for item2 in optionList
for BC1 in ListBC:
index=Adjustment(BC1)
HMList[index]=HMList[index]+1
m=max(HMList)
你可以简单地写:
m = max(Counter(ListBC).values())
HowManyBc使用collections.Counter标准库中的类,可以将猜测(您的函数)评估为三行.
from collections import Counter
def evaluate(guess, secret):
"""Return the pair (bulls, cows) where `bulls` is a count of the
characters in `guess` that appear at the same position in `secret`
and `cows` is a count of the characters in `guess` that appear at
a different position in `secret`.
>>> evaluate('ABCD', 'ACAD')
(2, 1)
>>> evaluate('ABAB', 'AABB')
(2, 2)
>>> evaluate('ABCD', 'DCBA')
(0, 4)
"""
matches = sum((Counter(secret) & Counter(guess)).values())
bulls = sum(c == g for c, g in zip(secret, guess))
return bulls, matches - bulls
我碰巧更喜欢在Mastermind中使用字母代码.ACDB阅读和打字比阅读和打字好得多[0, 2, 3, 1].但是我的evaluate功能很灵活,只要您将它们表示为可比项目的序列,您可以如何表示代码和猜测,因此如果您愿意,可以使用数字列表.
另请注意,我已经编写了一些doctests:这些是在文档中同时提供示例和测试函数的快速方法.
该函数itertools.product提供了一种方便的方法来构建代码列表,而无需编写四个嵌套循环:
from itertools import product
ALL_CODES = [''.join(c) for c in product('ABCDEF', repeat=4)]
Knuth的五猜算法使用了极小极大原理.那么为什么不通过min一系列调用来实现max呢？
def knuth(secret):
"""Run Knuth's 5-guess algorithm on the given secret."""
assert(secret in ALL_CODES)
codes = ALL_CODES
key = lambda g: max(Counter(evaluate(g, c) for c in codes).values())
guess = 'AABB'
while True:
feedback = evaluate(guess, secret)
print("Guess {}: feedback {}".format(guess, feedback))
if guess == secret:
break
codes = [c for c in codes if evaluate(guess, c) == feedback]
if len(codes) == 1:
guess = codes[0]
else:
guess = min(ALL_CODES, key=key)
这是一个示例运行:
>>> knuth('FEDA')
Guess AABB: feedback (0, 1)
Guess BCDD: feedback (1, 0)
Guess AEAC: feedback (1, 1)
Guess AFCC: feedback (0, 2)
Guess FEDA: feedback (4, 0)