python - structures - the algorithms

¿Cómo resolver el juego de adivinanzas "Mastermind"? (9)

¿Pareces el attempt Raymond Hettingers? Sin duda coinciden con algunos de sus requisitos.

Me pregunto cómo se comparan sus soluciones con las suyas.

¿Cómo crearías un algoritmo para resolver el siguiente rompecabezas, "Mastermind"?

Su oponente ha elegido cuatro colores diferentes de un conjunto de seis (amarillo, azul, verde, rojo, naranja, morado). Debes adivinar qué han elegido y en qué orden. Después de cada adivinanza, tu oponente te dice cuántos (pero no cuáles) de los colores que adivinaste eran del color correcto en el lugar correcto ["negros"] y cuántos (pero no cuáles) tenían el color correcto pero en el lugar equivocado ["ropa blanca"]. El juego termina cuando adivinas correctamente (4 negros, 0 blancos).

Por ejemplo, si su oponente ha elegido (azul, verde, naranja, rojo), y adivina (amarillo, azul, verde, rojo), obtendrá un "negro" (para el rojo) y dos blancos (para el azul y verde). Obtendrá el mismo puntaje para adivinar (azul, naranja, rojo, morado).

Me interesa saber qué algoritmo elegiría y (opcionalmente) cómo traducirlo en código (preferiblemente Python). Estoy interesado en soluciones codificadas que son:

Claro (fácil de entender)
Conciso
Eficiente (rápido para adivinar)
Eficaz (menor cantidad de conjeturas para resolver el rompecabezas)
Flexible (puede responder fácilmente preguntas sobre el algoritmo, por ejemplo, ¿cuál es su peor caso?)
General (se puede adaptar fácilmente a otros tipos de rompecabezas que Mastermind)

Estoy contento con un algoritmo que es muy efectivo pero no muy eficiente (¡siempre que no solo esté mal implementado!); sin embargo, un algoritmo muy eficiente y eficaz implementado de manera inflexible e impenetrable no es útil.

Tengo mi propia solución (detallada) en Python que publiqué, pero este no es, de ninguna manera, el único o el mejor enfoque, ¡así que publiquen más! No estoy esperando un ensayo;)

Aquí hay un enlace al solucionador puro de Python para Mastermind (tm): http://code.activestate.com/recipes/496907-mastermind-style-code-breaking/ Tiene una versión simple, una forma de experimentar con varias estrategias de adivinación, medición del rendimiento y un acelerador C opcional.

El núcleo de la receta es corto y dulce:

import random from itertools import izip, imap digits = 4 fmt = ''%0'' + str(digits) + ''d'' searchspace = tuple([tuple(map(int,fmt % i)) for i in range(0,10**digits)]) def compare(a, b, imap=imap, sum=sum, izip=izip, min=min): count1 = [0] * 10 count2 = [0] * 10 strikes = 0 for dig1, dig2 in izip(a,b): if dig1 == dig2: strikes += 1 count1[dig1] += 1 count2[dig2] += 1 balls = sum(imap(min, count1, count2)) - strikes return (strikes, balls) def rungame(target, strategy, verbose=True, maxtries=15): possibles = list(searchspace) for i in xrange(maxtries): g = strategy(i, possibles) if verbose: print "Out of %7d possibilities. I''ll guess %r" % (len(possibles), g), score = compare(g, target) if verbose: print '' ---> '', score if score[0] == digits: if verbose: print "That''s it. After %d tries, I won." % (i+1,) break possibles = [n for n in possibles if compare(g, n) == score] return i+1 def strategy_allrand(i, possibles): return random.choice(possibles) if __name__ == ''__main__'': hidden_code = random.choice(searchspace) rungame(hidden_code, strategy_allrand)

Así es como se ve el resultado:

Out of 10000 possibilities. I''ll guess (6, 4, 0, 9) ---> (1, 0) Out of 1372 possibilities. I''ll guess (7, 4, 5, 8) ---> (1, 1) Out of 204 possibilities. I''ll guess (1, 4, 2, 7) ---> (2, 1) Out of 11 possibilities. I''ll guess (1, 4, 7, 1) ---> (3, 0) Out of 2 possibilities. I''ll guess (1, 4, 7, 4) ---> (4, 0) That''s it. After 5 tries, I won.

Hay un gran sitio sobre la estrategia de MasterMind here . El autor comienza con problemas muy simples de MasterMind (usando números en lugar de letras e ignorando el orden y la repetición) y construyendo gradualmente hasta un problema completo de MasterMind (usando colores, que pueden repetirse, en cualquier orden, incluso con la posibilidad de errores) en las pistas).

Los siete tutoriales que se presentan son los siguientes:

Herramientas clave: entropía, codicia, sucursal y obligado; Python, generators, itertools, decorate-undecorate pattern

Al responder esta pregunta, quería construir un lenguaje de funciones útiles para explorar el problema. Examinaré estas funciones, describiéndolas y su intención. Originalmente, estos tenían documentos extensos, con pequeñas pruebas unitarias integradas probadas usando doctest; No puedo elogiar esta metodología lo suficiente como una forma brillante de implementar el desarrollo basado en pruebas. Sin embargo, no se traduce bien a , así que no lo presentaré de esta manera.

En primer lugar, necesitaré varios módulos estándar y futuras importaciones (trabajo con Python 2.6).

from __future__ import division # No need to cast to float when dividing import collections, itertools, math

Necesitaré una función de puntuación. Originalmente, esto devolvió una tupla (negros, blancos), pero encontré la salida un poco más clara si usaba una tilde nombrada:

Pegs = collections.namedtuple(''Pegs'', ''black white'') def mastermindScore(g1,g2): matching = len(set(g1) & set(g2)) blacks = sum(1 for v1, v2 in itertools.izip(g1,g2) if v1 == v2) return Pegs(blacks, matching-blacks)

Para hacer que mi solución sea general, paso algo específico para el problema de Mastermind como argumentos de palabra clave. Por lo tanto, he creado una función que crea estos argumentos una vez y utiliza la sintaxis de ** kwargs para pasarla. Esto también me permite agregar nuevos atributos fácilmente si los necesito más tarde. Tenga en cuenta que permito que las suposiciones contengan repeticiones, pero limitan al oponente a elegir colores distintos; para cambiar esto, solo necesito cambiar G a continuación. (Si quisiera permitir repeticiones en el secreto del oponente, necesitaría cambiar la función de puntuación también).

def mastermind(colours, holes): return dict( G = set(itertools.product(colours,repeat=holes)), V = set(itertools.permutations(colours, holes)), score = mastermindScore, endstates = (Pegs(holes, 0),)) def mediumGame(): return mastermind(("Yellow", "Blue", "Green", "Red", "Orange", "Purple"), 4)

A veces tendré que particionar un conjunto basado en el resultado de aplicar una función a cada elemento en el conjunto. Por ejemplo, los números 1..10 pueden dividirse en números pares e impares mediante la función n% 2 (las probabilidades dan 1, los pares dan 0). La siguiente función devuelve dicha partición, implementada como un mapa desde el resultado de la llamada a la función al conjunto de elementos que dieron ese resultado (por ejemplo, {0: evens, 1: odds}).

def partition(S, func, *args, **kwargs): partition = collections.defaultdict(set) for v in S: partition[func(v, *args, **kwargs)].add(v) return partition

Decidí explorar un solucionador que utiliza un enfoque entrópico codicioso . En cada paso, calcula la información que podría obtenerse de cada posible conjetura y selecciona la conjetura más informativa. A medida que el número de posibilidades crezca, esto se escalará mal (en forma cuadrática), ¡pero pruébelo! Primero, necesito un método para calcular la entropía (información) de un conjunto de probabilidades. Esto es solo -Σp log p. Sin embargo, para su comodidad, permitiré entradas que no están normalizadas, es decir, no agreguen hasta 1:

def entropy(P): total = sum(P) return -sum(p*math.log(p, 2) for p in (v/total for v in P if v))

Entonces, ¿cómo voy a usar esta función? Bueno, para un conjunto dado de posibilidades, V, y una suposición determinada, g, la información que obtenemos de esa suposición solo puede provenir de la función de puntuación: más específicamente, cómo esa función de puntuación divide nuestro conjunto de posibilidades. Queremos hacer una suposición que distinga mejor entre las posibilidades restantes, las divide en el mayor número de conjuntos pequeños, porque eso significa que estamos mucho más cerca de la respuesta. Esto es exactamente a lo que la función de entropía anterior le está asignando un número: una gran cantidad de conjuntos pequeños puntuará más que una pequeña cantidad de conjuntos grandes. Todo lo que tenemos que hacer es conectarlo.

def decisionEntropy(V, g, score): return entropy(collections.Counter(score(gi, g) for gi in V).values())

Por supuesto, en cualquier paso dado lo que realmente tendremos es un conjunto de posibilidades restantes, V, y un conjunto de posibles conjeturas que podríamos hacer, G, y tendremos que elegir la suposición que maximiza la entropía. Además, si varias conjeturas tienen la misma entropía, prefieren elegir una que también podría ser una solución válida; esto garantiza que el enfoque terminará. Utilizo el patrón estándar decorar-decodificar de python junto con el método máximo incorporado para hacer esto:

def bestDecision(V, G, score): return max((decisionEntropy(V, g, score), g in V, g) for g in G)[2]

Ahora todo lo que tengo que hacer es llamar repetidamente esta función hasta que se adivine el resultado correcto. Pasé por varias implementaciones de este algoritmo hasta que encontré uno que parecía correcto. Varias de mis funciones querrán abordar esto de diferentes maneras: algunas enumeran todas las posibles secuencias de decisiones (una por adivinanza que el oponente puede haber hecho), mientras que otras solo están interesadas en un único camino a través del árbol (si el oponente ya ha elegido un secreto, y solo estamos tratando de llegar a la solución). Mi solución es un "árbol flojo", donde cada parte del árbol es un generador que puede evaluarse o no, lo que permite al usuario evitar costosos cálculos que no necesitará. También terminé usando dos más namedtuples, una vez más por claridad de código.

Node = collections.namedtuple(''Node'', ''decision branches'') Branch = collections.namedtuple(''Branch'', ''result subtree'') def lazySolutionTree(G, V, score, endstates, **kwargs): decision = bestDecision(V, G, score) branches = (Branch(result, None if result in endstates else lazySolutionTree(G, pV, score=score, endstates=endstates)) for (result, pV) in partition(V, score, decision).iteritems()) yield Node(decision, branches) # Lazy evaluation

La siguiente función evalúa una única ruta a través de este árbol, en función de una función de puntuación suministrada:

def solver(scorer, **kwargs): lazyTree = lazySolutionTree(**kwargs) steps = [] while lazyTree is not None: t = lazyTree.next() # Evaluate node result = scorer(t.decision) steps.append((t.decision, result)) subtrees = [b.subtree for b in t.branches if b.result == result] if len(subtrees) == 0: raise Exception("No solution possible for given scores") lazyTree = subtrees[0] assert(result in endstates) return steps

Esto ahora se puede usar para construir un juego interactivo de Mastermind donde el usuario califica las suposiciones de la computadora. Jugar con esto revela algunas cosas interesantes. Por ejemplo, la primera conjetura más informativa es de la forma (amarillo, amarillo, azul, verde), no (amarillo, azul, verde, rojo). Se obtiene información adicional al usar exactamente la mitad de los colores disponibles. Esto también se aplica a Mastermind de 3 agujeros y 6 colores (amarillo, azul, verde) y Mastermind de 8 colores y 5 agujeros (amarillo, amarillo, azul, verde y rojo).

Pero todavía hay muchas preguntas que no se responden fácilmente con un solucionador interactivo. Por ejemplo, ¿cuál es la mayor cantidad de pasos necesarios para el enfoque entrópico codicioso? ¿Y cuántas entradas dan tantos pasos? Para facilitar la respuesta a estas preguntas, primero produzco una función simple que convierte el árbol perezoso de arriba en un conjunto de rutas a través de este árbol, es decir, para cada posible secreto, una lista de conjeturas y puntajes.

def allSolutions(**kwargs): def solutions(lazyTree): return ((((t.decision, b.result),) + solution for t in lazyTree for b in t.branches for solution in solutions(b.subtree)) if lazyTree else ((),)) return solutions(lazySolutionTree(**kwargs))

Encontrar el peor de los casos es una simple cuestión de encontrar la solución más larga:

def worstCaseSolution(**kwargs): return max((len(s), s) for s in allSolutions(**kwargs)) [1]

Resulta que este solucionador siempre se completará en 5 pasos o menos. Cinco pasos! Sé que cuando jugaba a Mastermind cuando era niño, a menudo me llevaba más tiempo que esto. Sin embargo, desde la creación de este solucionador y jugando con él, he mejorado mucho mi técnica, y 5 pasos es de hecho un objetivo alcanzable, incluso cuando no tienes tiempo para calcular la conjetura entropically ideal en cada paso;)

¿Qué tan probable es que el solucionador dé 5 pasos? ¿Alguna vez terminará en 1 o 2 pasos? Para descubrirlo, creé otra pequeña función simple que calcula la distribución de la longitud de la solución:

def solutionLengthDistribution(**kwargs): return collections.Counter(len(s) for s in allSolutions(**kwargs))

Para el enfoque entrópico codicioso, con repeticiones permitidas: 7 casos toman 2 pasos; 55 casos toman 3 pasos; 229 casos toman 4 pasos; y 69 casos toman el máximo de 5 pasos.

Por supuesto, no hay garantía de que el enfoque entrópico codicioso minimice el peor número de pasos. La parte final de mi lenguaje de propósito general es un algoritmo que decide si hay alguna solución para un determinado caso del peor caso. Esto nos dirá si la entropía codiciosa es ideal o no. Para hacer esto, adopto una estrategia de ramificación y vinculación:

def solutionExists(maxsteps, G, V, score, **kwargs): if len(V) == 1: return True partitions = [partition(V, score, g).values() for g in G] maxSize = max(len(P) for P in partitions) ** (maxsteps - 2) partitions = (P for P in partitions if max(len(s) for s in P) <= maxSize) return any(all(solutionExists(maxsteps-1,G,s,score) for l,s in sorted((-len(s), s) for s in P)) for i,P in sorted((-entropy(len(s) for s in P), P) for P in partitions))

Esta es definitivamente una función compleja, por lo que un poco más de explicación está en orden. El primer paso es dividir las soluciones restantes en función de su puntaje después de una suposición, como antes, pero esta vez no sabemos qué supongo que vamos a hacer, así que almacenamos todas las particiones. Ahora podríamos recurrir a cada uno de estos, enumerando de manera efectiva todo el universo de posibles árboles de decisión, pero esto tomaría un tiempo terriblemente largo. En su lugar, observo que, si en este momento no hay una partición que divida las soluciones restantes en más de n conjuntos, tampoco puede haber ninguna partición en un paso futuro. Si nos quedan k pasos, eso significa que podemos distinguir entre la mayoría ^{de las} soluciones n ^k-1 antes de que se nos acaben las suposiciones (en el último paso, siempre debemos adivinar correctamente). Por lo tanto, podemos descartar cualquier partición que contenga un puntaje asignado a más de esta cantidad de soluciones. Estas son las siguientes dos líneas de código.

La última línea de código realiza la recursión, usando cualquiera y todas las funciones de Python para mayor claridad, y probando las decisiones de entropía más alta primero para minimizar el tiempo de ejecución en el caso positivo. También recurre primero a la parte más grande de la partición, ya que es más probable que falle rápidamente si la decisión fue incorrecta. Una vez más, utilizo el patrón decorate-undecorate estándar, esta vez para ajustar la función ordenada de Python.

def lowerBoundOnWorstCaseSolution(**kwargs): for steps in itertools.count(1): if solutionExists(maxsteps=steps, **kwargs): return steps

Al llamar a solutionExists repetidamente con un número creciente de pasos, obtenemos un estricto límite inferior en la cantidad de pasos necesarios en el peor caso para una solución Mastermind: 5 pasos. El enfoque entrópico codicioso es de hecho óptimo.

Por curiosidad, inventé otro juego de adivinanzas, que apodé "twoD". En esto, intentas adivinar un par de números; en cada paso, se le informa si su respuesta es correcta, si los números que adivinó no son menores que los correspondientes en el secreto, y si los números no son mayores.

Comparison = collections.namedtuple(''Comparison'', ''less greater equal'') def twoDScorer(x, y): return Comparison(all(r[0] <= r[1] for r in zip(x, y)), all(r[0] >= r[1] for r in zip(x, y)), x == y) def twoD(): G = set(itertools.product(xrange(5), repeat=2)) return dict(G = G, V = G, score = twoDScorer, endstates = set(Comparison(True, True, True)))

Para este juego, el enfoque entrópico codicioso tiene el peor de los cinco pasos, pero hay una mejor solución posible con el peor de los cuatro pasos, lo que confirma mi intuición de que la avaricia miope es solo casualmente ideal para Mastermind. Más importante aún, esto ha demostrado cuán flexible es mi lenguaje: todos los mismos métodos funcionan para este nuevo juego de adivinanzas como lo hizo para Mastermind, permitiéndome explorar otros juegos con un mínimo de codificación adicional.

¿Qué hay del rendimiento? Obviamente, al implementarse en Python, este código no será increíblemente rápido. También he descartado algunas posibles optimizaciones a favor de un código claro.

Una optimización barata es observar que, en el primer movimiento, la mayoría de las suposiciones son básicamente idénticas: (amarillo, azul, verde, rojo) realmente no es diferente de (azul, rojo, verde, amarillo) o (naranja, amarillo, rojo) , púrpura). Esto reduce en gran medida el número de conjeturas que debemos considerar en el primer paso; de lo contrario, la decisión más costosa del juego.

Sin embargo, debido a la gran tasa de crecimiento del tiempo de ejecución de este problema, no pude resolver el problema de mentalidad de 8 colores y 5 agujeros, incluso con esta optimización. En cambio, porté los algoritmos a C ++, manteniendo la estructura general igual y empleando operaciones bit a bit para aumentar el rendimiento en los circuitos internos críticos, para una aceleración de varios órdenes de magnitud. Dejo esto como un ejercicio para el lector :)

Adición, 2018: Resulta que el enfoque entrópico codicioso tampoco es óptimo para el problema de mente maestra de 8 colores y 4 agujeros, con una duración de 7 pasos en el peor de los casos cuando existe un algoritmo que toma como máximo 6!

Solo pensé en contribuir con mis 90 líneas de código impares. Me baso en la respuesta de @Jim Dennis , en su mayoría eliminando la pista sobre la puntuación simétrica. Implementé el algoritmo minimax como lo describe Knuth en el artículo de la wikipedia de Mastermind , con una excepción: restrinjo mi próximo paso a la lista actual de posibles soluciones, ya que el rendimiento se deterioró gravemente al tener en cuenta todas las soluciones posibles en cada paso. El enfoque actual me deja con el peor caso de 6 conjeturas para cualquier combinación, cada uno encontrado en menos de un segundo.

Tal vez sea importante señalar que no hago restricción alguna en la secuencia oculta, lo que permite cualquier cantidad de repeticiones.

from itertools import product, tee from random import choice COLORS = ''red '', ''green'', ''blue'', ''yellow'', ''purple'', ''pink''#, ''grey'', ''white'', ''black'', ''orange'', ''brown'', ''mauve'', ''-gap-'' HOLES = 4 def random_solution(): """Generate a random solution.""" return tuple(choice(COLORS) for i in range(HOLES)) def all_solutions(): """Generate all possible solutions.""" for solution in product(*tee(COLORS, HOLES)): yield solution def filter_matching_result(solution_space, guess, result): """Filter solutions for matches that produce a specific result for a guess.""" for solution in solution_space: if score(guess, solution) == result: yield solution def score(actual, guess): """Calculate score of guess against actual.""" result = [] #Black pin for every color at right position actual_list = list(actual) guess_list = list(guess) black_positions = [number for number, pair in enumerate(zip(actual_list, guess_list)) if pair[0] == pair[1]] for number in reversed(black_positions): del actual_list[number] del guess_list[number] result.append(''black'') #White pin for every color at wrong position for color in guess_list: if color in actual_list: #Remove the match so we can''t score it again for duplicate colors actual_list.remove(color) result.append(''white'') #Return a tuple, which is suitable as a dictionary key return tuple(result) def minimal_eliminated(solution_space, solution): """For solution calculate how many possibilities from S would be eliminated for each possible colored/white score. The score of the guess is the least of such values.""" result_counter = {} for option in solution_space: result = score(solution, option) if result not in result_counter.keys(): result_counter[result] = 1 else: result_counter[result] += 1 return len(solution_space) - max(result_counter.values()) def best_move(solution_space): """Determine the best move in the solution space, being the one that restricts the number of hits the most.""" elim_for_solution = dict((minimal_eliminated(solution_space, solution), solution) for solution in solution_space) max_elimintated = max(elim_for_solution.keys()) return elim_for_solution[max_elimintated] def main(actual = None): """Solve a game of mastermind.""" #Generate random ''hidden'' sequence if actual is None if actual == None: actual = random_solution() #Start the game of by choosing n unique colors current_guess = COLORS[:HOLES] #Initialize solution space to all solutions solution_space = all_solutions() guesses = 1 while True: #Calculate current score current_score = score(actual, current_guess) #print ''/t''.join(current_guess), ''/t->/t'', ''/t''.join(current_score) if current_score == tuple([''black''] * HOLES): print guesses, ''guesses for/t'', ''/t''.join(actual) return guesses #Restrict solution space to exactly those hits that have current_score against current_guess solution_space = tuple(filter_matching_result(solution_space, current_guess, current_score)) #Pick the candidate that will limit the search space most current_guess = best_move(solution_space) guesses += 1 if __name__ == ''__main__'': print max(main(sol) for sol in all_solutions())

Si alguien detecta posibles mejoras en el código anterior, me interesaría mucho su sugerencia.

Una vez escribí un " Jotto " solucionador que es esencialmente "Master Mind" con palabras. (Cada uno escoge una palabra y nos turnamos adivinando la palabra del otro, marcando las coincidencias "a la derecha" (exactas) y "en otro lugar" (letra / color correctos, pero colocación incorrecta).

La clave para resolver ese problema es darse cuenta de que la función de puntuación es simétrica.

En otras palabras, si score(myguess) == (1,2) entonces puedo usar la misma función de score() para comparar mi anterior con cualquier otra posibilidad y eliminar cualquiera que no dé exactamente el mismo puntaje.

Permítanme dar un ejemplo: la palabra oculta (objetivo) es "puntaje" ... la conjetura actual es "tontos" --- el puntaje es 1,1 (una letra, "o", "correcto"; letra, ''s'', es "en otro lugar"). Puedo eliminar la palabra "adivinar" porque la `puntuación (" adivinar ") (contra" tontos ") devuelve (1,0) (las coincidencias finales ''s'', pero nada más lo hace). Entonces la palabra "adivinar" no es consistente con "tontos" y un puntaje en contra de una palabra desconocida que dio una puntuación de (1,1).

Así que ahora puedo leer cada palabra de cinco letras (o una combinación de cinco colores / letras / dígitos, etc.) y eliminar cualquier cosa que no puntúe 1,1 contra "tontos". Hazlo en cada iteración y convergerás rápidamente en el objetivo. (Para palabras de cinco letras, pude obtener 6 intentos cada vez ... y usualmente solo 3 o 4). Por supuesto, solo hay unas 6000 "palabras" y está eliminando cerca del 95% para cada conjetura.

Nota: para la siguiente discusión estoy hablando de cinco letras "combinación" en lugar de cuatro elementos de seis colores. Se aplican los mismos algoritmos; sin embargo, el problema es mucho menor para el antiguo juego "Master Mind" ... solo hay 1296 combinaciones (6 ** 4) de clavijas de colores en el clásico programa "Master Mind", suponiendo que se permiten duplicados. La línea de razonamiento que conduce a la convergencia implica algunos combinatorios: hay 20 puntajes posibles no ganadores para un objetivo de cinco elementos ( n = [(a,b) for a in range(5) for b in range(6) if a+b <= 5] para verlos todos si tiene curiosidad. Por lo tanto, esperaríamos que cualquier selección válida al azar tenga aproximadamente un 5% de posibilidades de igualar nuestra puntuación ... el otro 95% no lo hará y, por lo tanto, se eliminará para cada suposición anotada. Esto no tiene en cuenta el posible agrupamiento en patrones de palabras, pero el comportamiento del mundo real es lo suficientemente cercano para las palabras y definitivamente aún más cerca para las reglas de "Mente maestra". Las máquinas tragamonedas solo tenemos 14 posibles puntuaciones no ganadoras, por lo que nuestra convergencia no es tan rápida).

Para Jotto, los dos desafíos menores son: generar una buena lista mundial ( awk -f ''length($0)==5'' /usr/share/dict/words o similar en un sistema UNIX) y qué hacer si el usuario ha elegido una palabra que no está en nuestro diccionario (genera cada combinación de letras, ''aaaaa'' a ''zzzzz'' --- que es 26 ** 5 ... o ~ 1.1 millones). Un generador de combinaciones triviales en Python toma alrededor de 1 minuto para generar todas esas cadenas ... una optimizada debería ser mucho mejor. (También puedo agregar el requisito de que cada "palabra" tenga al menos una vocal ... pero esta restricción no ayuda mucho --- 5 vocales * 5 ubicaciones posibles para eso y luego se multiplica por 26 ** 4 otras combinaciones) .

Para Master Mind usas el mismo generador de combinación ... pero con solo 4 o 5 "letras" (colores). Cada combinación de 6 colores (15,625 de ellos) puede generarse en menos de un segundo (usando el mismo generador de combinación que utilicé anteriormente).

Si estuviera escribiendo este programa "Jotto" hoy, en Python, por ejemplo, "engañaría" al tener un hilo generando todas las combinaciones de letras en el fondo mientras aún estaba eliminado las palabras del diccionario (mientras mi oponente me estaba anotando, adivinando, etc.). Cuando los generé también eliminaría contra todas las conjeturas hasta ahora. Por lo tanto, después de haber eliminado todas las palabras conocidas, tendría una lista relativamente pequeña de posibilidades y, en contra de un jugador humano, he "ocultado" la mayor parte de mi retraso de cómputo al hacerlo en paralelo a su entrada. (Y, si escribiera una versión de servidor web de dicho programa, haría que mi motor web hablara con un daemon local para pedir secuencias consistentes con un conjunto de puntajes. El daemon mantendría una lista generada localmente de todas las combinaciones de letras y usaría un modelo select.select() para retroalimentar las posibilidades de cada una de las instancias en ejecución del juego; cada una de ellas alimentaría mis pares de palabra / puntaje daemon que mi daemon aplicaría como un filtro sobre las posibilidades que retroalimenta a ese cliente).

(En comparación, escribí mi versión de "Jotto" hace unos 20 años en un XT usando Borland TurboPascal ... y podría hacer cada iteración de eliminación --- comenzando con su compilación en la lista de unos pocos miles de palabras --- en un pozo en un segundo. Construyo su lista de palabras escribiendo un generador de combinaciones de letras simples (ver a continuación) ... guardando los resultados en un archivo moderadamente grande, luego ejecuto el corrector ortográfico de mi procesador de textos con una macro para eliminar todo lo que fue " mal escrito "--- luego usé otra macro para envolver todas las líneas restantes en la puntuación correcta para convertirlas en asignaciones estáticas válidas a mi matriz, que era un archivo #include en mi programa. Todo eso me permitió crear un juego independiente programa que "sabía" casi todas las palabras válidas de 5 letras en inglés, el programa era .COM --- menos de 50 KB si recuerdo correctamente).

Por otras razones, recientemente escribí un generador de combinaciones arbitrarias simple en Python. Son alrededor de 35 líneas de código y las publiqué en mi wiki de "fragmentos triviales" en bitbucket.org ... no es un "generador" en el sentido de Python ... pero una clase puede crear instancias en una secuencia infinita de combinación "numérica" o "simbólica" de elementos (esencialmente contando en cualquier base entera positiva).

Puede encontrarlo en: Trite Snippets: Arbitrary Sequence Combination Generator

Para la parte de coincidencia exacta de nuestra función de score() , puede usar esto:

def score(this, that): ''''''Simple "Master Mind" scoring function'''''' exact = len([x for x,y in zip(this, that) if x==y]) ### Calculating "other" (white pegs) goes here: ### ... ### return (exact,other)

Creo que esto ejemplifica parte de la belleza de Python: zip() sube las dos secuencias, devuelve cualquier coincidencia y toma la longitud de los resultados).

Encontrar las coincidencias en "otras" ubicaciones es engañosamente más complicado. Si no se permitieron repeticiones, entonces simplemente podría usar conjuntos para encontrar las intersecciones.

[En mi edición anterior de este mensaje, cuando me di cuenta de cómo podía usar zip() para las coincidencias exactas, pensé erróneamente que podíamos salirnos con other = len([x for x,y in zip(sorted(x), sorted(y)) if x==y]) - exact ... pero era tarde y estaba cansado. Mientras dormía, me di cuenta de que el método era defectuoso. ¡Malo, Jim! ¡No publique sin una prueba adecuada ! * (Probó varios casos que funcionó) .

En el pasado, el enfoque que utilicé fue ordenar las dos listas, comparar las cabezas de cada una: si las cabezas son iguales, incremente el recuento y saque elementos nuevos de ambas listas. de lo contrario, muestre un nuevo valor en la menor de las dos cabezas y vuelva a intentarlo. Divida tan pronto como cualquiera de las listas esté vacía.

Esto funciona; pero es bastante detallado. Lo mejor que puedo llegar a utilizar ese enfoque es más de una docena de líneas de código:

other = 0 x = sorted(this) ## Implicitly converts to a list! y = sorted(that) while len(x) and len(y): if x[0] == y[0]: other += 1 x.pop(0) y.pop(0) elif x[0] < y[0]: x.pop(0) else: y.pop(0) other -= exact

Utilizando un diccionario puedo recortarlo hasta aproximadamente nueve:

other = 0 counters = dict() for i in this: counters[i] = counters.get(i,0) + 1 for i in that: if counters.get(i,0) > 0: other += 1 counters[i] -= 1 other -= exact

(Utilizando la nueva clase "collections.Counter" (Python3 y programada para Python 2.7?) Podría presumiblemente reducir esto un poco más, aquí tres líneas están inicializando la colección de contadores).

Es importante disminuir el "contador" cuando encontremos una coincidencia y es vital probar el contador mayor que cero en nuestra prueba. Si una letra / símbolo dado aparece en "esto" una vez y "eso" dos veces, entonces solo se debe contar como una coincidencia una vez.

El primer enfoque es definitivamente un poco más complicado de escribir (uno debe tener cuidado para evitar los límites). También en un par de puntos de referencia rápidos (probando un millón de pares de patrones de letras generados aleatoriamente) el primer enfoque toma alrededor de un 70% más que el que usa diccionarios. (Generar los millones de pares de cadenas usando random.shuffle() tomó el doble de tiempo que la función de puntuación más lenta, por otro lado).

Un análisis formal del desempeño de estas dos funciones sería complicado. El primer método tiene dos géneros, por lo que sería 2 * O (n log (n)) ... y recorre al menos una de las dos cadenas y posiblemente deba iterar hasta el final de la otra cadena (mejor caso O (n), peor caso O (2n)) - fuerza Estoy mal usando la notación de O grande aquí, pero esto es solo una estimación aproximada. El segundo caso depende completamente de las características de rendimiento del diccionario. Si utilizáramos b-trees, el rendimiento sería aproximadamente O (n log (n) para la creación y encontrar cada elemento de la otra cadena sería otra operación O (n * log (n)). Sin embargo, los diccionarios de Python son muy eficiente y estas operaciones deberían estar cerca del tiempo constante (muy pocas colisiones hash). Por lo tanto, esperaríamos un rendimiento de aproximadamente O (2n) ... que por supuesto se simplifica a O (n). Eso coincide aproximadamente con mis resultados de referencia .

Echando un vistazo al artículo de Wikipedia sobre " Mente Maestra ", veo que Donald Knuth utilizó un enfoque que comenzó de manera similar al mío (y 10 años antes), pero agregó una optimización significativa. Después de reunir todas las posibilidades restantes, selecciona la que elimine la mayor cantidad de posibilidades en la siguiente ronda. Consideré tal mejora en mi propio programa y rechacé la idea por razones prácticas. En su caso, estaba buscando una solución óptima (matemática). En mi caso, me preocupaba la jugabilidad (en un XT, preferiblemente con menos de 64 KB de RAM, aunque podía cambiar al formato .EXE y usar hasta 640 KB). Quería mantener el tiempo de respuesta en el dominio de uno o dos segundos (lo cual fue fácil con mi enfoque, pero que sería mucho más difícil con el puntaje especulativo adicional). (Recuerde que estaba trabajando en Pascal, en MS-DOS ... sin hilos, aunque implementé el soporte para una encuesta asíncrona cruda de la UI que resultó innecesaria)

Si estuviera escribiendo algo así hoy, agregaría un hilo para hacer la mejor selección, también. Esto me permitiría dar la mejor suposición que haya encontrado dentro de una cierta restricción de tiempo, para garantizar que mi jugador no tenga que esperar demasiado para mi suposición. Naturalmente, mi selección / eliminación se estaría ejecutando mientras esperaba las suposiciones de mi oponente.

Mi amigo estaba considerando una caja relativamente simple: 8 colores, sin repeticiones, sin espacios en blanco.

Sin repeticiones, no es necesario tener en cuenta la entropía máxima, todas las suposiciones tienen la misma entropía y todas las conjeturas al azar funcionan bien.

Aquí está el código completo para resolver esa variante:

# SET UP import random import itertools colors = (''red'', ''orange'', ''yellow'', ''green'', ''blue'', ''indigo'', ''violet'', ''ultra'') # ONE FUNCTION REQUIRED def EvaluateCode(guess, secret_code): key = [] for i in range(0, 4): for j in range(0, 4): if guess[i] == secret_code[j]: key += [''black''] if i == j else [''white''] return key # MAIN CODE # choose secret code secret_code = random.sample(colors, 4) print (''(shh - secret code is: '', secret_code, '')/n'', sep='''') # create the full list of permutations full_code_list = list(itertools.permutations(colors, 4)) N_guess = 0 while True: N_guess += 1 print (''Attempt #'', N_guess, ''/n-----------'', sep='''') # make a random guess guess = random.choice(full_code_list) print (''guess:'', guess) # evaluate the guess and get the key key = EvaluateCode(guess, secret_code) print (''key:'', key) if key == [''black'', ''black'', ''black'', ''black'']: break # remove codes from the code list that don''t match the key full_code_list2 = [] for i in range(0, len(full_code_list)): if EvaluateCode(guess, full_code_list[i]) == key: full_code_list2 += [full_code_list[i]] full_code_list = full_code_list2 print (''N remaining: '', len(full_code_list), ''/n'', full_code_list, ''/n'', sep='''') print (''/nMATCH after'', N_guess, ''guesses/n'')

Para resolver el "peor" caso, en lugar de usar entropía estoy buscando la partición que tiene el número máximo de elementos, entonces selecciono el intento que es un mínimo para este máximo => Esto me dará el número mínimo de posibilidades restantes cuando no tengo suerte (lo que sucede en el peor de los casos).

Esto siempre resuelve el caso estándar en 5 intentos, pero no es una prueba completa de que realmente se necesiten 5 intentos porque podría suceder que para el siguiente paso un conjunto de posibilidades mayor hubiera dado un resultado mejor que uno más pequeño (porque es más fácil distinguir entre )

Aunque para el "Juego estándar" con 1680 tengo una prueba formal simple: para el primer paso, la prueba que da el mínimo para la partición con el número máximo es 0,0,1,1: 256. Jugar 0,0,1 , 2 no es tan bueno: 276. Para cada prueba posterior hay 14 resultados (1 no colocado y 3 colocados es imposible) y 4 colocado da una partición de 1. Esto significa que en el mejor de los casos (todas las particiones del mismo tamaño) obtendremos una partición máxima que es un mínimo de (número de posibilidades - 1) / 13 (redondeado porque tenemos un número entero así que necesariamente algunos serán menos y otros más, de modo que el máximo se redondea hacia arriba).

Si aplico esto:

Después de la primera jugada (0,0,1,1) me quedan 256.

Después del segundo intento: 20 = (256-1) / 13

Después del tercer intento: 2 = (20-1) / 13

Entonces no tengo más remedio que probar uno de los dos que quedan para el cuarto intento.

Si no tengo suerte, se necesita un quinto intento.

Esto prueba que necesitamos al menos 5 intentos (pero no que esto sea suficiente).

Aquí hay un algoritmo genérico que escribí que usa números para representar los diferentes colores. Es fácil de cambiar, pero creo que los números son mucho más fáciles de trabajar que las cadenas.

Puede utilizar cualquier parte o parte de este algoritmo, siempre que se otorgue el crédito correspondiente.

Tenga en cuenta que solo soy un estudiante de Informática de Grado 12, por lo que estoy dispuesto a apostar que definitivamente hay soluciones más optimizadas disponibles.

De todos modos, aquí está el código:

import random def main(): userAns = raw_input("Enter your tuple, and I will crack it in six moves or less: ") play(ans=eval("("+userAns+")"),guess=(0,0,0,0),previousGuess=[]) def play(ans=(6,1,3,5),guess=(0,0,0,0),previousGuess=[]): if(guess==(0,0,0,0)): guess = genGuess(guess,ans) else: checker = -1 while(checker==-1): guess,checker = genLogicalGuess(guess,previousGuess,ans) print guess, ans if not(guess==ans): previousGuess.append(guess) base = check(ans,guess) play(ans=ans,guess=base,previousGuess=previousGuess) else: print "Found it!" def genGuess(guess,ans): guess = [] for i in range(0,len(ans),1): guess.append(random.randint(1,6)) return tuple(guess) def genLogicalGuess(guess,previousGuess,ans): newGuess = list(guess) count = 0 #Generate guess for i in range(0,len(newGuess),1): if(newGuess[i]==-1): newGuess.insert(i,random.randint(1,6)) newGuess.pop(i+1) for item in previousGuess: for i in range(0,len(newGuess),1): if((newGuess[i]==item[i]) and (newGuess[i]!=ans[i])): newGuess.insert(i,-1) newGuess.pop(i+1) count+=1 if(count>0): return guess,-1 else: guess = tuple(newGuess) return guess,0 def check(ans,guess): base = [] for i in range(0,len(zip(ans,guess)),1): if not(zip(ans,guess)[i][0] == zip(ans,guess)[i][1]): base.append(-1) else: base.append(zip(ans,guess)[i][1]) return tuple(base) main()