策划者极大极小算法

Question

我正在尝试用python-donaldknuth的算法在不超过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

如果有人能帮忙，我会非常感激的！在

谢谢，迈克

Answer 1

1。你的实现有什么问题

有四个错误。在

1. 这一行的评论是错误的：

   m=max(HMList)#maximum [B,C], more left - less eliminated (min in minimax)
   

   这实际上是minimax中的“max”（应该在调用max时清除）。你在试图找到一个猜想，那就是最小化产生相同评价的一组可能的秘密的最大规模。这里我们找到了组的最大大小，这就是“最大值”。

2. 这个错误让你犯了这个错误：

   ^{pr2}$

   这里你需要取最小值，而不是最大值。

3. 在下面的行中，您从optionList中选择第一个将生成与item1相同的计算结果的项：

   possibleGuess=[i[:] for i in optionList if   AdjustmentInverse(maxElement)==HowManyBc(item1[:],i[:])]
   nextGuess=possibleGuess[0][:]
   

   但这是不对的：我们在这里想要的猜测是item1，而不是其他会产生相同评估的猜测！

4. 最后，您无法正确处理optionList只有一个剩余项的情况。在这种情况下，所有可能的猜测都能很好地区分这一项，因此minimax过程不区分猜测。在这种情况下，您应该猜测optionList[0]。

2。对代码的其他注释

1. 变量名选择不当。例如，item1是什么？这是您正在评估的猜测，所以它应该被称为possible_guess？我怀疑你上面的§1.3的错误部分是由于变量名选择不当造成的。

2. 有大量不必要的复制。所有的[:]都是没有意义的，可以删除。变量List1也是没有意义的（为什么不直接赋值给optionList？），正如nextGuess（它不仅仅分配给guess？）

3. 您构建了dummyList，它包含了所有可能的秘密，这些秘密将与最后一个猜测相匹配，但是您将丢弃dummyList中不在optionList中的所有条目。那么为什么不直接循环optionList并保留匹配的条目呢？像这样：

   optionList = [item for item in optionList if HowManyBc(guess, item)==BC]
   

4. 您将建立一个表HMList，该表统计每种公牛和奶牛的出现次数。您已经注意到有14个可能的（bull，cow）对，因此您编写了函数Adjustment和{}在列表中（bull，cow）对和它们的索引之间来回映射。在

   如果采用数据驱动方法并使用内置的^{}方法，这些函数的实现可能会简单得多：

   # 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。如果将计数保存在^{}而不是列表中，则可以避免{}。所以不是：

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

3。改进的eh3代码>

1. 使用标准库中的类^{}可以将计算猜测（您的函数HowManyBc）简化为三行。在

   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
   

   我碰巧更喜欢用字母来表示策划者的代码。ACDB比[0, 2, 3, 1]好得多。但是我的evaluate函数对于如何表示代码和猜测是灵活的，只要您将它们表示为可比较项的序列，因此如果您愿意，可以使用数字列表。在

   还请注意，我编写了一些doctests：这些是同时在文档中提供示例和测试函数的快速方法。

2. 函数^{}提供了一种方便的方法来构建代码列表，而不必编写四个嵌套循环：

   from itertools import product
   ALL_CODES = [''.join(c) for c in product('ABCDEF', repeat=4)]
   

3. Knuth的五猜测算法使用minimax principle。{a8}为什么不通过调用^来实现^ a8}？在

   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)