python - Mastermind minimax算法

我正在尝试在python中实现唐纳德·克努斯(Donald Knuth)的算法，以不超过5步的代码破解策划者。我已经检查了我的代码几次，它似乎遵循算法，如下所示:
http://en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm

但是，我发现某些 secret 需要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

如果有人可以帮忙，我将不胜感激!

谢谢，迈克

最佳答案

1.您的实现有什么问题

有四个错误。

在此行上的注释是错误的:

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

这实际上是minimax中的“最大值”(应该从对max的调用中清楚了)。您试图找到使产生相同评估的可能 secret 组的最大大小最小化的猜测。在这里，我们找到了组的最大大小，因此就是“最大”。

这个错误使您犯了这个错误:

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]。

2.关于您的代码的其他注释

变量名选择不当。例如，item1是什么？这就是您正在评估的猜测，因此可以肯定地将其称为possible_guess之类的东西？我怀疑您上面的§1.3错误部分是由于变量名选择不当造成的。

有大量不必要的复制。您的所有[:]都是毫无意义的，可以删除。变量List1也是毫无意义的(为什么不只分配给optionList吗？)，就像nextGuess一样(不只是分配给guess吗？)

您将构建dummyList，该dummyList由与上一次猜测相匹配的所有可能的 secret 组成，但是随后您丢弃了optionList中所有不在optionList中的条目。那么，为什么不仅仅循环HMList并保持匹配的条目呢？像这样:

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

您将建立一个表Adjustment，该表将对每种模式的牛市和牛市的发生次数进行计数。您已经注意到一个事实，即有14个可能的(公牛，母牛)对，因此您编写了AdjustmentInverse和list.index函数来在(公牛，母牛)对及其列表中的索引之间来回映射。

如果您采用数据驱动的方法并使用内置的 AdjustmentInverse 方法，则这些函数的实现可能简单得多:

# 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之后，您不再需要Adjustment了。如果将计数保留在 collections.Counter 而不是列表中，则可以避免HowManyBc。因此，而不是:

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.改进的代码

使用标准库中的 collections.Counter 类，可以将猜测(您的函数ACDB)评估为仅三行。

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中使用字母作为代码。 [0, 2, 3, 1]比evaluate更易于阅读和键入。但是我的itertools.product函数可以灵活地表示代码和猜测，只要您将它们表示为可比较项的序列即可，因此您可以根据需要使用数字列表。

还要注意，我已经写了一些doctests:这是在文档中同时提供示例并测试功能的快速方法。

函数 min 提供了一种便捷的方式来构建代码列表，而无需编写四个嵌套循环:

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

Knuth的五猜测算法使用minimax principle。那么，为什么不采用对 max 的一系列调用中的 ojit_code 来实现它呢？

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)