Este equipo de expertos pasados varios días de trabajo y de juntar de información, dieron con la solución, deseamos que todo este artículo sea de utilidad para tu plan.
Solución:
Herramientas clave: entropía, codicia, bifurcaciones y límites; Python, generadores, itertools, patrón decorar-no decorar
Al responder a esta pregunta, quería construir un lenguaje de funciones útiles para explorar el problema. Revisaré 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 en StackOverflow, por lo que no lo presentaré de esta manera.
En primer lugar, necesitaré varios módulos estándar y futuro 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 devolvía una tupla (negros, blancos), pero encontré la salida un poco más clara si usaba una tupla con nombre:
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 que mi solución sea general, paso cualquier cosa específica al problema Mastermind como argumentos de palabras clave. Por lo tanto, he creado una función que crea estos argumentos una vez y uso la sintaxis ** kwargs para pasarlos. Esto también me permite agregar fácilmente nuevos atributos si los necesito más adelante. Tenga en cuenta que permito que las suposiciones contengan repeticiones, pero constriño 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, también necesitaría cambiar la función de puntuació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 necesitaré dividir un conjunto basado en el resultado de aplicar una función a cada elemento del conjunto. Por ejemplo, los números 1..10 se pueden dividir 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 del resultado de la llamada a la función al conjunto de elementos que dieron ese resultado (por ejemplo, 0: pares, 1: probabilidades).
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 use un enfoque entrópico codicioso. En cada paso, calcula la información que podría obtenerse de cada conjetura posible y selecciona la conjetura más informativa. A medida que aumenta el número de posibilidades, esto se escalará mal (cuadráticamente), ¡pero intentémoslo! 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, por conveniencia, permitiré entradas que no estén normalizadas, es decir, que no sumen 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 dada, 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 la mayor cantidad 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 asigna un número: una gran cantidad de conjuntos pequeños puntuarán más alto 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 conjetura que maximice la entropía. Además, si varias suposiciones tienen la misma entropía, prefiera 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 Python decorate-undecorate junto con el método max 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 a esta función hasta que se adivine el resultado correcto. Pasé por una serie de implementaciones de este algoritmo hasta que encontré una que parecía correcta. Varias de mis funciones querrán abordar esto de diferentes maneras: algunas enumeran todas las posibles secuencias de decisiones (una por suposición que puede haber tomado el oponente), mientras que otras solo están interesadas en un solo 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 perezoso”, donde cada parte del árbol es un generador que se puede evaluar o no, lo que permite al usuario evitar costosos cálculos que no necesitará. También terminé usando dos tuplas con nombre más, nuevamente para mayor claridad del 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, según una función de puntuación proporcionada:
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 puntúa las conjeturas de la computadora. Jugar con esto revela algunas cosas interesantes. Por ejemplo, la primera suposición más informativa es la forma (amarillo, amarillo, azul, verde), no (amarillo, azul, verde, rojo). Se obtiene información adicional utilizando exactamente la mitad de los colores disponibles. Esto también es válido para Mastermind de 6 colores y 3 agujeros – (amarillo, azul, verde) – y Mastermind de 8 colores y 5 agujeros – (amarillo, amarillo, azul, verde, 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 Mastermind cuando era niño, a menudo tardaba más que esto. Sin embargo, desde que creé este solucionador y jugué con él, he mejorado mucho mi técnica, y 5 pasos es un objetivo alcanzable incluso cuando no tienes tiempo para calcular la suposición entrópica ideal en cada paso;)
¿Qué posibilidades hay de que el solucionador dé 5 pasos? ¿Terminará alguna vez en 1 o 2 pasos? Para averiguarlo, 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 número de pasos en el peor de los casos. La parte final de mi lenguaje de propósito general es un algoritmo que decide si hay o no alguna soluciones para un determinado límite en el peor de los casos. Esto nos dirá si el entrópico codicioso es ideal o no. Para hacer esto, adopto una estrategia de bifurcació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 es necesario un poco más de explicación. El primer paso es dividir las soluciones restantes en función de su puntuación después de una conjetura, como antes, pero esta vez no sabemos qué conjetura vamos a hacer, por lo que almacenamos todas las particiones. Ahora nosotros podría simplemente recurrir a cada uno de estos, enumerando efectivamente todo el universo de posibles árboles de decisión, pero esto llevaría un tiempo horriblemente largo. En cambio, observo que, si en este punto no hay una partición que divida las soluciones restantes en más de n conjuntos, tampoco puede haber tal partición en ningún paso futuro. Si nos quedan k pasos, eso significa que podemos distinguir entre como máximo nk-1 soluciones antes de que nos quedemos sin conjeturas (en el último paso, siempre debemos adivinar correctamente). Por lo tanto, podemos descartar cualquier partición que contenga una puntuación asignada 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 hace la recursividad, utilizando todas y cada una de las funciones de Python para mayor claridad, y probando primero las decisiones de entropía más alta 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 estándar decorar-no decorar, esta vez para envolver el patrón de Python ordenado función.
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 límite inferior estricto en el número de pasos necesarios en el peor de los casos para una solución Mastermind: 5 pasos. El enfoque entrópico codicioso es realmente óptimo.
Por curiosidad, inventé otro juego de adivinanzas, al que llamé "dosD". En esto, intentas adivinar un par de números; en cada paso, se le dice 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 casos de cinco pasos, pero hay una mejor solución posible con el peor de los casos de cuatro pasos, lo que confirma mi intuición de que la codicia miope es solo una coincidencia 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 que para Mastermind, lo que me permite explorar otros juegos con un mínimo de codificación adicional.
¿Qué pasa con el rendimiento? Obviamente, al implementarse en Python, este código no va a ser increíblemente rápido. También eliminé algunas optimizaciones posibles a favor de un código claro.
Una optimización barata es observar que, en el primer movimiento, la mayoría de las conjeturas 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 la cantidad 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 Mastermind de 8 colores y 5 orificios, incluso con esta optimización. En cambio, porté los algoritmos a C ++, manteniendo la estructura general igual y empleando operaciones bit a bit para mejorar el rendimiento en los bucles internos críticos, para una aceleración de muchos órdenes de magnitud. Dejo esto como ejercicio para el lector 🙂
Anexo, 2018: Resulta que el enfoque entrópico codicioso tampoco es óptimo para el problema Mastermind de 8 colores y 4 agujeros, ¡con una longitud de 7 pasos en el peor de los casos cuando existe un algoritmo que toma como máximo 6!
Una vez escribí un solucionador "Jotto" que es esencialmente "Master Mind" con palabras. (Cada uno escoge una palabra y nos turnamos para adivinar la palabra del otro, puntuando coincidencias "correctas" (exactas) y "en otro lugar" (letra / color correcto, pero ubicación incorrecta).
La clave para resolver este 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 lo mismo score() función para comparar mi conjetura anterior con cualquier otra posibilidad y elimine las que no den exactamente la misma puntuación.
Permítanme dar un ejemplo: la palabra oculta (objetivo) es "puntuación" ... la suposición actual es "tontos" --- la puntuación es 1,1 (una letra, 'o', es "justo"; otra la letra, 's', está "en otro lugar"). Puedo eliminar la palabra "adivinar" porque el `score (" adivinar ") (contra" tontos ") devuelve (1,0) (coincidencias de la 's' final, pero nada más lo hace). Entonces, la palabra "adivinar" no es consistente con "tontos" y una puntuación contra alguna palabra desconocida que dio como resultado una puntuación de (1,1).
Así que ahora puedo revisar cada palabra de cinco letras (o una combinación de cinco colores / letras / dígitos, etc.) y eliminar cualquier cosa que no tenga un puntaje de 1,1 contra "tontos". Haga eso en cada iteración y rápidamente convergerá en el objetivo. (Para palabras de cinco letras, pude obtener en 6 intentos cada vez ... y generalmente solo 3 o 4). Por supuesto, hay sólo unas 6000 "palabras" y estás eliminando cerca del 95% por cada conjetura.
Nota: para la siguiente discusión, estoy hablando de una "combinación" de cinco letras en lugar de cuatro elementos de seis colores. Se aplican los mismos algoritmos; sin embargo, el problema es órdenes de magnitud más pequeñas para el antiguo juego "Master Mind" ... solo hay 1296 combinaciones (6 ** 4) de clavijas de colores en el programa clásico "Master Mind", asumiendo que se permiten duplicados. La línea de razonamiento que conduce a la convergencia implica algunas combinatorias: hay 20 puntuaciones posibles no ganadoras 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 tienes curiosidad. Por lo tanto, esperaríamos que cualquier selección aleatoria válida tenga aproximadamente un 5% de posibilidades de igualar nuestro puntaje ... el otro 95% no lo hará y, por lo tanto, será eliminado por cada intento puntuado. Esto no tiene en cuenta la posible agrupación en patrones de palabras, pero el comportamiento en el mundo real es lo suficientemente cercano para las palabras y definitivamente aún más cercano para las reglas de la "Mente Maestra". Sin embargo, con solo 6 colores en 4 ranuras, solo tenemos 14 posibles puntajes no ganadores, 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 (generar cada combinación de letras, 'aaaaa' a 'zzzzz' --- que es 26 ** 5 ... o ~ 1,1 millones). Un generador de combinación trivial en Python tarda aproximadamente 1 minuto en generar todas esas cadenas ... uno optimizado debería ser mucho mejor. (También puedo agregar un 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 multiplicado por 26 ** 4 combinaciones más) .
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) se puede generar en menos de un segundo (usando el mismo generador de combinación que usé anteriormente).
Si estuviera escribiendo este programa "Jotto" hoy, en Python por ejemplo, haría "trampa" al tener un hilo que genere todas las combinaciones de letras en el fondo mientras todavía estoy eliminando palabras del diccionario (mientras mi oponente me estaba anotando, adivinar, etc.). A medida que los generaba, también eliminaría 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, contra un jugador humano, he "ocultado" la mayor parte de mi retraso de cálculo 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 demonio local para solicitar secuencias consistentes con un conjunto de puntuaciones. El demonio mantendría una lista generada localmente de todas las combinaciones de letras y usaría un select.select() modelo para retroalimentar las posibilidades de cada una de las instancias en ejecución del juego --- cada una alimentaría mis pares de palabra / puntuación de demonio que mi demonio 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 lista compilada de unos pocos miles de palabras --- en bien menos de un segundo. Construyo su lista de palabras escribiendo un generador de combinación de letras simple (ver más abajo) ... guardando los resultados en un archivo moderadamente grande, luego ejecutando el corrector ortográfico de mi procesador de textos con una macro para eliminar todo lo que era " mal escrito "--- luego utilicé otra macro para ajustar todas las líneas restantes en la puntuación correcta para hacerlas asignaciones estáticas válidas a mi matriz, que era un archivo #include en mi programa. Todo eso me permitió construir un juego independiente programa que "sabía" casi todas las palabras válidas en inglés de 5 letras; el programa era un .COM --- menos de 50 KB si no recuerdo mal).
Por otras razones, recientemente escribí un generador de combinación arbitraria simple en Python. Se trata de 35 líneas de código y lo he publicado en mi wiki de "fragmentos trillados" en bitbucket.org ... no es un "generador" en el sentido de Python ... sino una clase que puedes instanciar en una secuencia infinita de Combinación "numérica" o "simbólica" de elementos (esencialmente contando en cualquier base de números enteros positivos).
Puede encontrarlo en: Trite Snippets: Generador de combinación de secuencia arbitraria
Para la parte exacta de nuestro score() función, solo 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 algo de la belleza de Python: zip() subir las dos secuencias, devolver cualquiera que coincida y tomar la longitud de los resultados).
Encontrar las coincidencias en "otras" ubicaciones es engañosamente más complicado. Si no se permiten repeticiones, simplemente puede usar conjuntos para encontrar las intersecciones.
[In my earlier edit of this message, when I realized how I could use zip() for exact matches, I erroneously thought we could get away with other = len([x for x,y in zip(sorted(x), sorted(y)) if x==y]) - exacto ... pero era tarde y estaba cansado. Mientras dormía, me di cuenta de que el método era defectuoso. ¡Malo, Jim! No publiques sin adecuado testing! * (Probé varios casos que funcionaron)].
En el pasado, el enfoque que usé fue ordenar ambas listas, comparar las cabezas de cada una: si las cabezas son iguales, incrementar el recuento y sacar nuevos elementos de ambas listas. de lo contrario, introduzca un nuevo valor en la menor de las dos cabezas y vuelva a intentarlo. Romper tan pronto como cualquiera de las listas esté vacía.
Esto funciona; pero es bastante detallado. Lo mejor que se me ocurre al usar ese enfoque es un poco 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
Usando un diccionario, puedo recortar eso a 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
(Usando la nueva clase "collections.Counter" (¿Python3 y programada para Python 2.7?) Podría presumiblemente reducir esto un poco más; tres líneas aquí están inicializando la colección de contadores).
Es importante disminuir el "contador" cuando encontramos una coincidencia y es vital probar un contador mayor que cero en nuestra prueba. Si una letra / símbolo determinado aparece en "este" una vez y "aquel" dos veces, solo debe contarse como una coincidencia una vez.
El primer enfoque es definitivamente un poco más complicado de escribir (hay que tener cuidado de evitar los límites). También en un par de evaluaciones comparativas rápidas (probando un millón de pares de patrones de letras generados aleatoriamente), el primer enfoque toma aproximadamente un 70% más que el que usa diccionarios. (Generando el millón de pares de cadenas usando random.shuffle() asumió el doble de tiempo que la más lenta de las funciones de puntuación, por otro lado).
Un análisis formal del desempeño de estas dos funciones sería complicado. El primer método tiene dos tipos, por lo que sería 2 * O (nlog (n)) ... y itera a través de al menos una de las dos cadenas y posiblemente tenga que iterar hasta el final de la otra cadena (mejor caso O (n), peor caso O (2n)) - - force Estoy usando mal la notación Big-O aquí, pero esto es solo una estimación aproximada. El segundo caso depende enteramente de las características de rendimiento del diccionario. Si estuviéramos usando árboles b, entonces el rendimiento sería aproximadamente O (nlog (n) para la creación y encontrar cada elemento de la otra cadena en el mismo sería otra operación O (n * log (n)). Sin embargo, los diccionarios de Python son muy eficientes y estas operaciones deben ser casi constantes (muy pocas colisiones de 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 "Master Mind", veo que Donald Knuth utilizó un enfoque que comienza 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 eliminaría 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 capacidad de reproducción (en un XT, preferiblemente usando menos de 64 KB de RAM, aunque podría cambiar al formato .EXE y usar hasta 640 KB). Quería mantener el tiempo de respuesta bajo en el ámbito de uno o dos segundos (lo cual fue fácil con mi enfoque, pero sería mucho más difícil con la puntuación especulativa adicional). (Recuerde que estaba trabajando en Pascal, bajo MS-DOS ... sin subprocesos, aunque implementé el soporte para el sondeo asincrónico crudo de la interfaz de usuario que resultó ser innecesario)
Si estuviera escribiendo algo así hoy, también agregaría un hilo para hacer la mejor selección. Esto me permitiría dar la mejor suposición que encontré dentro de un cierto límite de tiempo, para garantizar que mi jugador no tuviera que esperar demasiado para mi suposición. Naturalmente, mi selección / eliminación se estaría ejecutando mientras esperaba las conjeturas de mi oponente.
¿Te ha parecido el intento de Raymond Hettingers? Sin duda, se ajustan a algunos de sus requisitos.
Me pregunto cómo se comparan sus soluciones con las tuyas.
Aquí puedes ver las reseñas y valoraciones de los lectores
Acuérdate de que te damos el privilegio valorar este artículo si descubriste tu problema a tiempo.