¿Cómo funcionan los algoritmos para juegos de Scrabble de computadora?

Podría funcionar con la búsqueda del diccionario de fuerza bruta, comenzando con la primera de sus letras y buscando en ese subconjunto de palabras coincidencias con cualquiera de las letras restantes en el segundo espacio. Espuma, enjuague, repita, hasta que haya encontrado todas y las mejores opciones.

Eso sería muy lento.

Podría optimizar su diccionario. Podría asignar pesos a cada letra [piense que el grosor de la sección de la letra en el diccionario equivale a un peso más pesado … una letra de mayor puntuación incluso un peso más pesado]. Podría hacer esto para cada posibilidad de letra en cada posición, ya que la N [número de palabras] en su diccionario es fija. Luego, una rápida reorganización de su letra se acumula por peso y encontrará la mejor respuesta más rápida.

Podría crear un mapeo. Supongamos que desea encontrar rápidamente todas las palabras con una U en el segundo lugar, porque tiene una Q y el peso es mayor en su mano. O hay una U en el tablero o hay una en tu mano. El mapeo se puede determinar estáticamente, por lo que no tomará tiempo construirlo durante el juego. Pero reduciría rápidamente la cantidad de palabras a considerar en un mapa de todas las palabras con U en el segundo espacio intersectado con el mapeo de todas las palabras con Q en el primer espacio.

Algo así, estoy seguro. De hecho, estoy empezando a trabajar exactamente en esto para un juego, así que intentaré recordar actualizar mi respuesta si me he equivocado mucho.

Esta revisión de los algoritmos MCTS afirma que las simulaciones de Monte Carlo se utilizaron para vencer a los mejores jugadores humanos alrededor del año 2000. Probablemente haya más detalles en los documentos vinculados.