python - python 中的策划者

Question

我正在尝试在 python 中实现 Donald Knuth 的密码破译策划者算法，不超过 5 步。我已经多次检查我的代码，它似乎遵循算法，如下所述:http://en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm

但是，我知道有些 secret 需要 7 步甚至 8 步才能完成，例如 [5, 4, 4, 5]。

代码如下:

# returns how many bulls and cows
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  
# returns positive's list minimum without including zeros    
def MinimumNozeros(List1):
    minimum=max(List1)+1
    for item in List1:
        if item!=0 and item<minimum:
            minimum=item
    return minimum

TempList=[[5, 4, 4, 5]]

for secret in TempList:
    guess=[0,0,1,1]
    BC=HowManyBc(guess[:],secret[:])
    counter=1
    optionList=[]
    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):
                    optionList.append([i0,i1,i2,i3])
                    allList.append([i0,i1,i2,i3])
    while BC!=[4,0]:
        dummyList=[]
        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[:]
        nextGuess1=[]
        item1Max=0
        L1=optionList[:]
        L2=allList[:]
        for item1 in L1:
            ListBC=[]
            for item2 in L2:
                ListBC.append(HowManyBc(item1[:],item2[:]))
            HMList=[0]*14 # how many times every possible BC appeared
            for BC1 in ListBC:
                index=Adjustment(BC1)
                HMList[index]=HMList[index]+1
            m=MinimumNozeros(HMList[:])
            if m>item1Max:
                item1Max=m
                nextGuess1=item1[:]
        guess=nextGuess1[:]
        BC=HowManyBc(guess[:],secret[:])
        counter=counter+1

有人可以帮忙吗？

谢谢，迈克

Answer 1

Knuth 的算法是:

1. 创建一组 S 的剩余可能性(此时有 1296)。第一个猜测是 aabb。
2. 从 S 中删除所有不会给出相同分数的彩色和白色钉子的可能性，如果它们是答案的话。
3. 对于每个可能的猜测(不一定在 S 中)计算每个可能的有色/白色分数将从 S 中消除多少种可能性。猜测的分数是这些值中最小的。猜最高分 (minimax)。
4. 回到第 2 步，直到你做对为止。

你的算法是:

1. 创建一组 S 的剩余可能性(此时有 1296)。第一个猜测是 aabb。
2. 从 S 中删除所有不会给出相同分数的彩色和白色钉子的可能性，如果它们是答案的话。
3. 对于每个可能的猜测(必须在 S 中)计算所有选项集合中每个选项保留的可能性可能的彩色/白色分数。猜测的分数是这些值中最小的。猜最高分 (minimax)。
4. 回到第 2 步，直到你做对为止。

您可以通过将循环更改为以下方式来解决此问题:

for secret in TempList:
    guess=[0,0,1,1]
    BC=HowManyBc(guess[:],secret[:])
    counter=1
    optionList=[]
    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):
                    optionList.append([i0,i1,i2,i3])
                    allList.append([i0,i1,i2,i3])
    #while BC!=[4,0]:
    while len(optionList)>1:
        dummyList=[]
        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[:]
        nextGuess1=[]
        item1Max=0
        #L1=optionList[:]
        #L2=allList[:]
        L2=optionList[:]
        L1=allList[:]
        for item1 in L1: 
            ListBC=[]
            for item2 in L2: 
                ListBC.append(HowManyBc(item1[:],item2[:]))
            HMList=[0]*14 
            for BC1 in ListBC:
                index=Adjustment(BC1)
                HMList[index]=HMList[index]+1  
            #m=MinimumNozeros(HMList[:])
            m=len(L1)-max(HMList[:]) 
            if m>item1Max:
                item1Max=m
                nextGuess1=item1[:]
        guess=nextGuess1[:]
        BC=HowManyBc(guess[:],secret[:])
        counter=counter+1
print optionList