¿Cuál es el algoritmo óptimo para jugar al juego de palabras Hangman?

Question

Supongamos que estamos jugando el juego Hangman . Mi oponente y yo tenemos acceso al diccionario durante el juego. Mi oponente escoge una palabra del diccionario con conocimiento del algoritmo que usaré para adivinar su palabra secreta. Una vez que mi oponente ha escogido una palabra, solo me dan la longitud de la palabra. Puedo adivinar una letra que creo que estará en la palabra, y si está en la palabra, mi oponente identifica todas las posiciones de esa carta en esa palabra. Si supongo una carta que no está en la palabra, eso se cuenta como un error. Si puedo adivinar la palabra antes de muchos errores que gano.

El objetivo de mi oponente debe ser elegir una palabra que maximice el número de errores (conjeturas incorrectas) Hago antes de que pueda adivinar la palabra. Mi objetivo es minimizarlos. (Tradicionalmente, si el número de errores es un número, entonces pierdo el juego, pero podemos relajar esa restricción).

Considerar tres algoritmos para la adivinación de las letras. Estos son los principales que he pensado, pero probablemente haya más, y doy la bienvenida a las ideas alternativas. En los tres algoritmos, el primer paso será recopilar la lista de palabras que son la misma longitud que la palabra secreta. Luego, para cada letra en el alfabeto, cuente la cantidad de palabras en el diccionario que contenga esa letra. Por ejemplo, tal vez 5000 contienen "A", 300 contienen "B", y así sucesivamente. Aquí está en Python:

    alphabet = list('abcdefghijklmnopqrstuvwxyz')

    while not found:
        probabilities = dict.fromkeys(alphabet, 0)

        for word in dictionary:
            for letter in word:
                if letter in alphabet:
                    probabilities[letter] += 1

        # now we have the letter frequencies

Después de eso es donde los tres algoritmos divergen.

1. En el primer algoritmo, adivinamos la letra que la mayor cantidad de palabras restantes contienen. Por lo tanto, si 5000 palabras restantes contienen "A" y ninguna otra letra están en tantas palabras, elegiremos "A" cada vez. Si "A" es correcto, esto nos da información posicional que podemos filtrar aún más la lista. Por ejemplo, podríamos filtrar la lista por todas las palabras que coincidan con ".a ..". (Los puntos son letras desconocidas.) Si "A" es incorrecto, filtramos todas las palabras que contienen "A". En el caso de que haya un empate y se encuentran dos letras en un número igual de palabras, las letras se eligen alfabéticamente. Entonces, si sabemos que la palabra coincide ".ays", simplemente adivinaremos las palabras en orden alfabético.

2. Esto es solo un poco diferente del primer algoritmo. En lugar de elegir siempre el orden alfabético, en el caso de un empate, elegimos letras al azar. Esto tiene el beneficio que nuestro oponente no sabe lo que elegiremos. En la primera estrategia, "Rays" siempre es mejor que "días". Esto evita ese problema.

3. En este caso, recogemos letras con una probabilidad proporcional a la cantidad de palabras que contienen esa letra. Al principio, cuando contemplamos la cantidad de palabras que contienen "A" y el número que contienen "B", etc., ya que "A" se encontró en la mayor cantidad de palabras, en las estrategias 1 y 2, elegimos " un "100% del tiempo. En su lugar, todavía elegiremos "A" una pluralidad de la época, pero una pequeña cantidad de veces que elegiremos "Z" a pesar de que se puede encontrar en 10 veces más palabras. Tengo mis dudas sobre esta estrategia que es óptima pero se usó en la investigación en 2010 .

, así que tengo dos preguntas:

1. ¿Cuál es la estrategia de adivinación de letras óptimas que debería usar asumiendo que mi oponente sabe que usaré esta estrategia ? En esto queremos minimizar el número promedio de conjeturas, se necesitará para adivinar la palabra secreta.
2. Para una palabra dada, diga "Pague", ¿cuál es el número promedio de errores que debo esperar que haga? ¿Hay una forma de formación cerrada de calcular M, a diferencia de ejecutar esta simulación muchas veces y promediar los resultados?

aclaraciones

• Se puede utilizar cualquier diccionario de inglés. Por ejemplo, este diccionario de inglés con 84k palabras. . Los subconjuntos de diccionarios elegidos cuidadosamente para la ambigüedad también podrían ser interesantes, pero están fuera del alcance de esta pregunta.
• No hay restricciones en el tamaño de la palabra siempre que la palabra esté en el diccionario. El adivino conocerá el tamaño de la palabra antes de comenzar a adivinar.
• Solo el número total de errores de errores, que es independiente del tamaño de la palabra. No tiene más posibilidades de palabras más largas, o menos posibilidades de más cortas.
• Solo estoy interesado en minimizar el número promedio de errores. Si hay dos algoritmos óptimos que tienen un número promedio equivalente pequeño de errores, ambos son aceptables.
• En principio, es posible que haya una situación en la que la elección de una letra (diga "B") conduce a más información que otra (por ejemplo, "A"), aunque "A" ocurre en más palabras posibles que "B" lo hace. También estoy abierto a esta posibilidad en la práctica. Los tres algoritmos ilustrados anteriormente asumen que th

no sucede debido al hecho de que una suposición correcta tiende a producir más información que una incorrecta (es decir, la información posicional sobre una letra correcta suele ser mejor que "esta letra no está en la palabra").Pero un algoritmo óptimo no necesita hacer este supuesto.

Answer 1

Es posible calcular la estrategia óptima, pero el cálculo puede ser bastante intensivo, y no estoy seguro de si le dará una ganancia excesiva sobre las heurísticas simples. Voy a explicar la siguiente manera. La idea principal es utilizar la programación dinámica.

Estrategias deterministas

Permítanme comenzar primero con el caso especial de estrategias deterministas para elegir qué letra adivina a continuación, ya que son más fáciles de analizar. Esto nos dará un calentamiento antes de pasar a las estrategias aleatorias (que probablemente serán superiores).

El estado del juego en cualquier punto puede ser resumido por el par $ (g, r) $ , donde $ g $ es el conjunto de letras que se han adivinado hasta ahora, y $ r $ son las respuestas (es decir, la secuencia de espacios en blanco y letras de $ G $ que es visible para el jugador). El orden de las conjeturas pasadas no importa (por eso basta con tener un conjunto $ g $ de las conjeturas pasadas). Deciremos que una palabra $ w $ es consistente con $ (g, r) $ si es sigue siendo posible, es decir, si la palabra del oponente es $ w $ y haces las conjetivas en $ g $ , entonces obtendrías la respuesta $ r $ .

Let $ P (g, r)= 1 $ Si es posible ganar desde aquí, si comienza desde el estado $ (g, r) $ . Eso significa que existe una estrategia para ganar: donde no importa en qué palabra está pensando que el oponente (siempre que sea consistente con $ (g, r) $ ) , el número de conjeturas erróneas que has hecho hasta ahora, más el número que realiza en el futuro con esta estrategia, no excederá el límite superior. De lo contrario, define $ P (g, r)= 0 $ .

Ahora puede calcular $ P (g, r) $ con programación dinámica, utilizando la relación de recurrencia

$$ P (g, r)=bigvee_a \ bigwedge _ {(g ', r')} p (g ', r'), $$

donde $ a $ rangos sobre todas las letras que no están en $ g $ (es decir, todas las posibilidades para ¿Qué letra adivina a continuación), y $ (g ', r') $ rangos sobre todas las respuestas posibles si adivina $ A $ Siguiente (es decir, $ g '= g \ Cup \ {A \} $ , y buscamos todas las palabras $ W $ que son consistentes con $ (g, r) $ y calculan la respuesta $ r '$ para adivinar $ g' $ Si la palabra es $ w $ ) .

En particular, le sugiero que lo compite $ P (g, r) $ utilizando la mejor búsqueda y la memorización de profundidades. Luego, $ P (\ Otalset, - - \ CDOTS -) $ le dirá si es posible ganar dentro del límite superior, sin importar la palabra que el oponente elija el oponente . Al rastrear el cálculo hacia atrás, puede reconstruir la estrategia óptima.

es este factible? Espero que sea. Creo que el número de estados posibles $ (g, r) $ no es demasiado grande. (En particular, puede ignorar a los estados $ (g, r) $ donde ya ha hecho demasiadas conjeturas incorrectas, y cualquier estado donde solo una palabra sea consistente con Ese estado es automáticamente una victoria, por lo que no necesita un análisis adicional). Como optimización, dado un estado $ (g, r) $ , puede intentar enumerar Todas las palabras $ w $ que son consistentes con ellos y simulan algunas heurísticas fijas y verifique si ganará para cada palabra; Si es así, no necesita hacer ningún otro recorrido de profundidad, primero, puede marcar de inmediato $ P (g, R)= 1 $ . Además, solo necesita considerar conjeturas $ a $ que aparecen en al menos una palabra que es consistente con $ (g, r) $ .

Por lo tanto, debe ser bastante sencillo para calcular la estrategia determinista óptima.

Estrategias aleatorias

Podemos seguir un método similar para manejar estrategias aleatorias, pero se involucra un poco más. Ahora permita que $ P (g, r) $ denote la probabilidad de ganar desde aquí, si usamos las estrategias óptimas de aquí en adelante. Podemos computar esto utilizando la programación dinámica.

La diferencia clave está en la relación de recurrencia en la que nos computamos $ P (g, r) $ de las cantidades $ P (g ', R') $ donde $ (g ', r') $ gama sobre todos los estados que podrían occ

UR A continuación, después de adivinar una letra más. Aquí tenemos un simple juego de dos jugadores. Primero, elegimos una distribución de probabilidad sobre las letras que no está en $ g $ . Luego, el oponente ve nuestra distribución, y elige una distribución en las palabras $ w $ que son consistentes con $ (g, r) $ . Nuestra recompensa (y la cantidad que pierde el oponente) es igual a la probabilidad de que ganemos de aquí en dicha opciones. Observe que esto se puede calcular desde el $ P (g ', R') $ valores. Resulta que desde que vamos primero y el oponente ve nuestra elección, el oponente no necesita una estrategia aleatorizada; Pueden hacerlo igualmente bien con una estrategia determinista, es decir, seleccionando una sola palabra $ w $ basado en nuestra distribución. Entonces, si formamos una matriz $ m $ donde $ m_ {w, i} $ sostiene la probabilidad de Ganar si elegimos la letra $ i $ Siguiente y el oponente elige la palabra $ w $ ; Podemos rellenar $ m_ {w, i} $ como $ P (g ', r') $ Donde $ g '= g \ Cup \ {i \ \ \ \ span> y $ r' $ es el Respuesta Para adivinar $ g '$ Si la palabra es $ w $ . Luego, buscamos resolver el problema de optimización $$ \ max_v \ min_w (mv) _w= - \ min_v \ max_w - (mv) _w= - \ min_v \ | -mv \ | _ \ Infty. $$ Esto se puede solucionar usando programación lineal . Entonces, podemos calcular $ P (g, r) $ utilizando la programación lineal de los valores $ p (g ', r ') $ donde $ g' $ es una más grande que $ g $ .

Poniendo esto todos juntos, usaremos el primer recorrido de la profundidad con la memorización (o la programación dinámica), utilizando la programación lineal en cada paso para resolver el juego de 2 jugadores. Esto nos da la estrategia aleatoria óptima para jugar a Hangman.

El cálculo resultante puede ser muy costoso, ya que requiere miles de millones o billones de pasos, donde resuelve un programa lineal en cada paso. Entonces, no sé si es realista usarlo en la práctica.

Algunas optimizaciones son posibles, como se sugiere @j_random_hacker. First First Compute $ P (g, r) $ para estrategias deterministas; Luego, solo necesita considerar estrategias aleatorias para los estados $ (g, r) $ donde $ P (g, r)= 0 $ .

estrategias heurísticas

Usted enumeró algunas heurísticas razonables para elegir una estrategia. Aquí hay una heurística más. Dado el estado $ (g, r) $ , enumere todas las posibilidades para la próxima conjetura $ a \ notin g $ . Centrémonos en una sola letra $ a $ . Luego, para cada $ (g ', r') $ que podría ocurrir como un estado siguiente después de adivinar $ a $ < / span> (por lo $ g '= g \ Cup \ {A \} $ ), cuenta el número de palabras $ w $ consistente con $ (g ', r') $ ; Tome el máximo a lo largo de estos números, y use que como el recuento asociado con $ a $ . La estrategia heurística es elegir la letra $ a $ cuyo conteo es más pequeño.

Computación del número esperado de errores

Puede calcular el número esperado de errores de una estrategia aleatorizada en particular utilizando la programación dinámica. Los detalles son similares a los anteriores, pero la relación de recurrencia se vuelve más sencilla: se convierte en

$$ P (g, r)=min_w \ mathbb {e} [p (g ', r')], $$

donde $ w $ rangos sobre todas las palabras consistentes con $ (g, r) $ , y $ (g ', r') $ es la distribución en el siguiente estado si la palabra es $ w $ Y la siguiente letra supuesta es elegida por su estrategia. Dada su estrategia y la palabra $ w $ , es fácil calcular la distribución en las conjeturas y, por lo tanto, obtener la distribución en los siguientes estados, por lo que es fácil calcular $ \ mathbb {e} [p (g ', r')] $ .