La primera conjetura matemáticamente óptima en Wordle
Al igual que muchas personas en mi línea de tiempo de Twitter actualmente, he estado jugando Wordle en los últimos días. Es un divertido y sencillo juego en el que adivinas palabras de 5 letras y te dice cuántas letras has acertado y si están en la posición correcta o no. Parte del juego es que solo hay uno por día, y es la misma palabra para todos los que juegan.
Así que decidí hacer un bot para jugar el juego de manera óptima para mí. Ahora, podrías considerar hacer trampa, pero considerando lo fácil que es hacer trampa simplemente «buscando la respuesta del acertijo de hoy», no creo que hacer un bot como este no sea ético ni nada por el estilo. Pero saber cuál es la «mejor primera palabra posible» podría arruinarte el juego, así que deberías dejar de leer ahora si no quieres saberlo.
De todos modos, comencemos.
Primero, agarré las listas de palabras que usa el juego. Hay una lista separada para soluciones y posibles conjeturas (para que pueda ingresar palabras extrañas de Scrabble como AAHED, pero eso no aparecerá como una solución real para el rompecabezas porque no es una palabra de uso común), y ambas listas son accesibles al ver el código fuente del juego. Hay 2315 soluciones posibles y 12972 palabras que acepta como conjeturas.
Una estimación rápida de cuánto tiempo tomaría esto, primero multipliqué 12972 por 2315 para obtener ~30 millones de conjeturas, y evaluar cada conjetura va a multiplicar eso por 2315 nuevamente, lo que hace que sea del orden de 60 mil millones de cálculos. 60 mil millones de cálculos parece mucho, pero es un orden de magnitud similar a la cantidad de operaciones que puede hacer una CPU por segundo (4 ghz x 8 núcleos = 32 mil millones), por lo que debería ser factible hacer esto en la forma tonta de fuerza bruta . Elegí C++ para tener tan pocogastos generalescomo sea posible, y también porque me siento muy cómodo con él.
He subido el código para el bot en github aquí , como referencia.
Después de un poco de codificación, tuve una prueba «simple». Para cada suposición posible, la compara con cada solución posible. Los cuadrados “verdes” (la letra está en el espacio correcto) valen 2 puntos, los cuadrados “amarillos” (la letra existe en la palabra, pero está en el lugar equivocado) valen 1 punto y los cuadrados grises (la letra no existen en la palabra) valen cero puntos. La suposición con el puntaje promedio más alto (la palabra con la mayor probabilidad de tener muchos verdes y amarillos) se devuelve como la suposición.
Este sistema funciona bastante bien. En promedio, encuentra una solución con 3.69017 conjeturas. La primera palabra que elige es SOARE («un halcón joven»). Sin embargo, este bot no siempre gana el juego. En el peor de los casos, se necesitan 8 intentos para encontrar una solución.
Ahora, aunque este método es extremadamente rápido, podemos hacerlo mejor. Una métrica más específica de qué tan buena es una suposición sería «cuántas soluciones posibles quedan en promedio después de hacer esta suposición». Después de un par de horas, tenía una versión del bot que usaría este método, multiproceso, por lo que podría calcular el resultado en un tiempo razonable. Esta versión del bot encuentra una solución en 3.49417 conjeturas en promedio y tiene un peor caso de 5 conjeturas (es decir, *siempre* encuentra una solución). La primera suposición ideal con este método es ROATE.
Honestamente, la eficiencia con la que este bot encuentra soluciones es bastante impresionante de ver. Mira lo rápido que encuentra la solución correcta para el rompecabezas de hoy (29/12):t
Así que ahí lo tienes, la primera suposición ideal para Wordle es ROATE. Significa: «Las ganancias netas acumuladas después de impuestos disponibles para los accionistas comunes, ajustadas por la amortización de intangibles afectados por impuestos, para los trimestres calendario en cada año calendario en un período de tiempo específico dividido por el capital común tangible promedio del accionista».
Pero espere, ROATE podría ser la primera suposición ideal, según la duración promedio de la suposición, pero dado que solo está en la lista de suposiciones y no en la lista de soluciones, nunca puede llegar a un «hoyo en uno». Y si realmente quieres impresionar a tus amigos, querrás poder alcanzar esa probabilidad de 1 en 2315 de conseguirlo en el primer intento. Para esto, la primera suposición ideal sería SUBIR. Con RAISE como primera suposición, promediará 3.49546 suposiciones para resolver en promedio, solo un poco peor que ROATE, pero tiene esa dulce, dulce oportunidad de lograr ese hoyo en uno. (Raise es también la palabra con el mejor rendimiento en el «peor de los casos», por lo que ahora estoy a favor de esto)
Así que ahí lo tienes. ROATE es la primera conjetura matemáticamente óptima en Wordle. RAISE es un poco menos bueno, pero te da la oportunidad de hacer un hoyo en uno. Wordle está resuelto!
…
¿O es eso?
Bien, entonces, ROATE es la primera suposición óptima, si la métrica que está midiendo es «el tamaño de la lista de posibles soluciones después de una suposición». Pero si lo que realmente quieres es «llegar a una solución en el promedio de movimientos mínimos», eso no es del todo equivalente a lo que estaba midiendo aquí.
Tuve que codificar una solución recursiva que mediría directamente el número promedio de conjeturas adicionales que se necesitarían para llegar a una solución basada en cualquier conjetura, pero resultó ser demasiado para mi computadora con el ingenuo método de fuerza bruta allí. . Estamos hablando de cantidades de tiempo de computadora «más largas que la edad del universo». Sin embargo, tengo un trabajo real en el que debería estar trabajando, así que les dejaré resolver esto como tarea. ¡Buena suerte! Envíeme un tweet si logra encontrar la solución óptima *real*.
Escrito por: Tyler Glaiel
