Solución:
Suponga el siguiente diccionario: ABC ABD AEF EGH. (Poneré en mayúscula las letras no adivinadas).
Suponga que solo tiene 1 vida (hace que la prueba sea mucho más fácil …).
El algoritmo propuesto anteriormente:
Empezando con A, pierde (1/4) o se queda con aBC aBD aEF (3/4).
Ahora adivina B y pierden (1/3) o se quedan con abC abD (2/3).
Ahora adivina C o D y pierde (1/2) o gana (1/2).
Probabilidad de ganar: 3/4 * 2/3 * 1/2 = 1/4.
Ahora prueba algo más:
Empezando con E, pierde (1/2) o se queda con AeF eGH (1/2).
Ahora sabes qué adivinar y ganar.
Probabilidad de ganar: 1/2.
Claramente, el algoritmo propuesto no es óptimo.
Hay algunas suposiciones críticas que debes hacer sobre lo que es un juego de “Hangman”.
- ¿Solo tienes una palabra que debes adivinar o necesitas adivinar una frase?
- ¿Algunas palabras son más probables que otras?
Una cosa para recordar es que si eliges una letra correcta, no pierdes ni un minuto.
Proporcionaré una solución para el caso de una palabra – y – igualmente probable. El caso de dos palabras se puede generalizar creando un nuevo diccionario igual al producto cartesiano de su diccionario actual, etc. El caso más probable que otros se puede generalizar con un poco de probabilidad.
Antes de definir nuestro algoritmo, definimos el concepto de reducción. Si tuviéramos que adivinar las letras L1, L2, L3, … LN todas una vez, reduciríamos el diccionario a un diccionario más pequeño: algunas palabras serían eliminadoy, además, algunos letras también puede eliminarse. Por ejemplo si tuviéramos el diccionario {dog, cat, rat} y adivinamos a, eliminaríamos {d, g} si la suposición fuera verdadera, o también eliminaríamos {c, r, t} si fuera falsa.
El algoritmo óptimo es el siguiente:
- Considere el árbol del juego
- Mira todos los nodos donde [#guesses left == 1]
- Si no hay ningún nodo, el juego es imposible; si hay un nodo, esa es tu respuesta
Por supuesto, así es como se resuelve cualquier juego, y en su mayor parte es intratable debido a los requisitos de tamaño exponencial. No se puede obtener el óptimo a menos que se repita perfectamente esto, y dudo seriamente que una estrategia que no “mira” dos o más movimientos hacia adelante pueda esperar replicar esto. Sin embargo, puede intentar aproximar la estrategia óptima de la siguiente manera.
Repita lo siguiente en cada paso:
- Considere cada letra: elija la letra que maximizará la reducción de diccionario esperada por penalización esperada: es decir, elija la letra L que maximizará la (
frac words with L#words without L+frac words without L#words with L) / (# words without L/# words total) … tenga en cuenta que esto puede ser infinito si todas las palabras tienen una letra determinada, en cuyo caso siga adelante y adivine ya que no hay penalización. - Haz tu conjetura, obtén un estado actualizado de la placa
- Elimina todas las palabras invalidadas por el nuevo tablero.
Por supuesto, si su diccionario tiene más de 2^[max number of guesses] entradas, el juego “Hangman” es casi imposible en el mundo de la probabilidad igual (a menos que el diccionario esté muy restringido), por lo que tienes que trabajar en el mundo de la probabilidad desigual. En este mundo, en lugar de maximizar la cantidad de eliminación que haces, maximizas la “sorpresa esperada” (también llamada entropía). Cada palabra que asocie una probabilidad previa (por ejemplo, digamos que hay una probabilidad de 0.00001 de que la palabra sea ‘putrefacta’ y una probabilidad de 0.002 de que la palabra sea ‘verdugo’). La sorpresa es igual a la probabilidad, medida en bits (el logaritmo negativo de la probabilidad). Una respuesta a una suposición no arrojará letras, una sola letra o más de una letra (muchas posibilidades). Por lo tanto:
- Para cada posible suposición, considere el efecto que tendría esa suposición
- Para cada resultado posible de la suposición, considere la probabilidad de ese resultado. Por ejemplo, si adivinó ‘A’ para una palabra de 3 letras, tendría que considerar cada resultado posible en el conjunto
{A__, _A_, __A, AA_, A_A, _AA, AAA}. Para cada resultado, calcule la probabilidad utilizando la regla de Bayes y también los nuevos diccionarios posibles (por ejemplo, en un caso, tendría un diccionario de_A_:{cAt, bAt, rAt, ...}yA__:{Art, Ark, Arm, ...}etc.). Cada uno de estos nuevos diccionarios también tiene una razón de verosimilitud, de la formasize(postOutcomeDictionary dictionary)/size(preOutcomeDictionary); el logaritmo negativo de esta relación es la cantidad de información (en bits) que le transmite la elección. - Por lo tanto, desea maximizar la proporción de la cantidad esperada de información (en bits) que obtiene, por el costo esperado (la penalización del costo es 1 si falla y 0 si no lo hace). Para cada conjetura, y para cada resultado de la conjetura, los bits de información obtenidos son
bitsGainedFromOutcome[i] = -log(size(postOutcomeDictionary)/size(preOutcomeDictionary)). Tomamos la suma ponderada de estos:sum{i}( prob(outcome[i])*bitsGainedFromOutcome[i] ), luego dividir por la probabilidad de que estemos equivocados:prob(outcome=='___'). - Elegimos la letra con el mínimo
sum{i}( prob(outcome[i])*bitsGainedFromOutcome[i] )/prob(outcome=='___'); en caso de que sea infinito, no hay nada que perder y lo elegimos automáticamente.
Entonces, para responder a su pregunta:
>En el juego Hangman, ¿se da el caso de que un algoritmo codicioso de frecuencia de letras sea equivalente a un algoritmo de mayor probabilidad de ganar?
Claramente no: si el diccionario fuera
cATs
bATs
rATs
vATs
sATe
mole
vole
role
tu algoritmo adivinaría a o t, que tienen una probabilidad de 5/8 de reducir su diccionario a un tamaño de 5/8 de forma gratuita, y una probabilidad de 3/8 de reducir su diccionario a un tamaño de 3/8 por un costo de 1. Desea elegir las letras que revelen más información. En este caso, debe adivinar S, porque tiene una probabilidad de 4/8 de reducir su diccionario a un tamaño de 4/8 de forma gratuita, una probabilidad de 1/8 de reducir su diccionario a un tamaño de 1/8 de forma gratuita y una probabilidad de 3 / 8 posibilidades de reducir su diccionario a un tamaño de 3/8 por un costo de 1. Esto es estrictamente mejor.
editar: Quería usar un ejemplo de diccionario de inglés (arriba) para demostrar cómo esto no es artificial, y asumí que las personas podrían extrapolar el ejemplo sin estar colgadas de la igualdad no estricta. Sin embargo, aquí hay un contraejemplo inequívocamente claro: tienes 2000 palabras. 1000 palabras contienen la letra A en primer lugar. Las otras 1000 palabras contienen una combinación única de Bs incrustado en otro lugar. Por ejemplo, ?B???, ??B??, ???B?, ????B, ?BB??, ?B?B?, etc. ?s representan caracteres elegidos al azar. No existen As en el primer?, excepto por una palabra (cuyo? es una ‘A’), de modo que la frecuencia de As es estrictamente mayor que la frecuencia de Bs. El algoritmo propuesto adivinaría A lo que daría como resultado {50%: options_halved, 50%: options_halved & lose_one_life}, mientras que este algoritmo dictaría la elección B lo que da como resultado {50%: YOU_WIN, 50%: options_halved & lose_one_life}. Los porcentajes se han redondeado muy ligeramente. (Y no, una palabra con letras dobles no contribuye dos veces a la ‘frecuencia’, pero incluso si lo hiciera bajo una definición loca, podría modificar trivialmente este ejemplo haciendo que las palabras comiencen con AAA...A.)
(con respecto a los comentarios: no es razonable quejarse de la igualdad estricta en este ejemplo, por ejemplo, “999/2000”, ya que puede hacer que las probabilidades se acerquen arbitrariamente entre sí).
(Lo que señala una nota al margen divertida: si el diccionario es lo suficientemente grande como para hacer que el ahorcado sea imposible a veces, una estrategia debería descartar las conjeturas que no espera poder adivinar. Por ejemplo, si solo le quedan 2 movimientos, debería hacer la suposición de mayor probabilidad posible, lo que elimina los subárboles con más de 2 movimientos de bits de sorpresa).
Acerca de su idea de intentar adivinar la palabra en lugar de tratar de adivinar letras, seguramente puede haber algunos casos aislados en los que adivine la palabra desde el primer intento o algo así, pero esto no hace que ese algoritmo sea mejor en el caso promedio. . Se trata de la probabilidad esperada.
Alguna mejora que se podría hacer a ese algoritmo (en la versión publicada por Lajos) es una selección más informada de la letra que se debe probar.
Esto podría lograrse agregando un peso más: considere el uso de cada palabra el vocabulario del idioma.
Por ejemplo, las palabras técnicas, médicas, jurídicas, etc. tendrían muchas menos posibilidades.
Tome este diccionario (con algunos ejemplos de pesos de uso):
frost 6
guilt 5
genes 1
fever 2
meter 1
Aquí e es la letra más frecuente, por lo que sería elegida. Esto significaría dejar solo los términos médicos, que son muy poco probables. Pero si la decisión la toman:
weight(letter) = w * frequency +
(1 - w) * sum( usage_weight(word) where letter in word )
entonces, muy probablemente t sería elegido.
Porque (digamos w = 0.2):
weight(e) = 0.2 * 3 + 0.8 * (1 + 2 + 1)
= 3
weight(r) = 0.2 * 3 + 0.8 * (1 + 2 + 6)
= 7.8
weight
= 10.2
Nota: Por supuesto, deberíamos usar pesos normalizados, como frequency / num_words para obtener una medición de peso precisa.
Nota: Este algoritmo puede y debe adaptarse al oponente:
- cuando se juega contra humanos, las palabras más habituales adquieren mayor peso
- cuando juegas contra la IA, depende del nivel de dificultad:
- en un nivel fácil, apunte a las palabras habituales
- en el nivel difícil, apunte a palabras inusuales