Mastermind algoritmo minimax

Estoy intentando implementar en Python el algoritmo de Donald Knuth para descifrar la mente maestra en no más de 5 movimientos. He revisado mi código varias veces, y parece que sigue el algoritmo, como se indica aquí: http://en.wikipedia.org/wiki/Mastermind_(board_game ) #Five- guess_algorithm

Sin embargo, entiendo que algunos de los secretos toman 7 o incluso 8 movimientos para lograrlos. Aquí está el código:

#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 itemitem1Max: #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 

Yo obtengo:

para [5, 3, 3, 4] el contador es 7

para [5, 4, 4, 5] el contador es 8

    ¡Si alguien pudiera ayudarme lo apreciaría mucho!

    Gracias mike

    1. ¿Qué hay de malo en tu implementación?

    Hay cuatro errores.

    1. El comentario está mal en esta línea:

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

      Este es en realidad el “máximo” en el minimax (que debería haber quedado claro desde la llamada al max ). Está intentando encontrar la conjetura que minimiza el tamaño máximo de los grupos de posibles secretos que producen la misma evaluación. Aquí estamos encontrando el tamaño máximo de los grupos, así que ese es el “máximo”.

    2. Ese error te hizo hacer este:

       if m>item1Max: #max of the guesses, the max in minimax 

      Aquí tienes que tomar el mínimo, no el máximo.

    3. En las siguientes líneas, selecciona el primer elemento de optionList que generaría la misma evaluación que item1 :

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

      Pero eso no es correcto: la conjetura que queremos aquí es el item1 , ¡no otra conjetura que genere la misma evaluación!

    4. Finalmente, no maneja adecuadamente el caso donde optionList tiene solo un elemento restante. En este caso, todas las conjeturas posibles son igualmente buenas para distinguir entre este elemento, por lo que el procedimiento de minimax no distingue entre las conjeturas. En este caso, solo debes adivinar optionList[0] .

    2. Otros comentarios sobre tu código.

    1. Los nombres de las variables están mal elegidos. Por ejemplo, ¿qué es item1 ? Esta es la conjetura que estás evaluando, por lo que seguramente debería llamarse algo así como ¿es possible_guess adivinar? Sospecho que su error §1.3 anterior fue en parte causado por esta mala elección de nombre de variable.

    2. Hay vastas cantidades de copias innecesarias. Todos sus [:] son inútiles y pueden eliminarse. La variable List1 también es inútil (¿por qué no asignar simplemente a optionList ?), Como lo es nextGuess (que no solo asignar para guess ?)

    3. Construye dummyList consiste en todos los secretos posibles que coincidirían con la última estimación, pero luego tiras todas las entradas en dummyList que no están también en optionList . Entonces, ¿por qué no hacer un loop sobre optionList y mantener las entradas que coinciden? Me gusta esto:

       optionList = [item for item in optionList if HowManyBc(guess, item)==BC] 
    4. Usted construye una tabla HMList que cuenta el número de ocurrencias de cada patrón de toros y vacas. Ha notado el hecho de que hay 14 pares posibles (toro, vaca) y, por lo tanto, ha escrito las funciones Adjustment y AdjustmentInverse para mapear entre pares (toro, vaca) y sus índices en la lista.

      Estas funciones podrían tener implementaciones mucho más simples si tomara un enfoque basado en datos y usara el método 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] 

      Pero después de corregir el error §1.3 anterior, ya no necesita AjustarInverso. Y el Adjustment podría evitarse si mantuviera los conteos en una collections.Counter Busque en lugar de una lista. Así que en lugar de:

       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) 

      usted podría simplemente escribir:

       m = max(Counter(ListBC).values()) 

    3. Código mejorado

    1. La evaluación de una conjetura (su función HowManyBc ) se puede reducir a solo tres líneas utilizando las collections.Counter clase. HowManyBc de la biblioteca estándar.

       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 

      Resulta que prefiero usar letras para los códigos en Mastermind. ACDB es mucho más ACDB de leer y escribir que [0, 2, 3, 1] . Pero mi función de evaluate es flexible en cuanto a cómo representas los códigos y las conjeturas, siempre que los representes como secuencias de elementos comparables, así que puedes usar listas de números si lo prefieres.

      Tenga en cuenta también que he escrito algunas pruebas : esta es una forma rápida de proporcionar simultáneamente ejemplos en la documentación y probar la función.

    2. La función itertools.product proporciona una manera conveniente de construir la lista de códigos sin tener que escribir cuatro bucles nesteds:

       from itertools import product ALL_CODES = [''.join(c) for c in product('ABCDEF', repeat=4)] 
    3. El algoritmo de cinco conjeturas de Knuth utiliza el principio minimax . Entonces, ¿por qué no implementarlo tomando el min de una secuencia de llamadas al 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) 

      Aquí hay un ejemplo de ejecución:

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