Maven es un reproductor de Scrabble con inteligencia artificial , creado por Brian Sheppard en 1986. Ya no está disponible comercialmente, pues Hasbro adquirió los derechos en 1996. Desde entonces, se ha utilizado en juegos de Scrabble oficiales con licencia de Hasbro .
La jugabilidad de Maven se subdivide en tres fases: la fase de "mitad del juego", la fase de "pre-final del juego" y la fase de "final del juego".
La fase de "mitad del juego" dura desde el comienzo del juego hasta que quedan nueve fichas o menos en la bolsa. El programa utiliza un algoritmo rápido para encontrar todas las jugadas posibles en el conjunto dado, y luego una parte del programa llamada "kibitzer" utiliza una heurística simple para ordenarlas en un orden aproximado de calidad. Las jugadas más prometedoras se evalúan entonces mediante "simulación", en la que el programa simula la extracción aleatoria de fichas, reproduce hacia delante un número determinado de jugadas y compara la distribución de puntos de los resultados de las jugadas. Al simular miles de extracciones aleatorias, el programa puede dar una evaluación cuantitativa muy precisa de las diferentes jugadas. (Si bien es una búsqueda de Monte Carlo, Maven no utiliza la búsqueda de árbol de Monte Carlo porque evalúa árboles de juego solo de 2 capas de profundidad, en lugar de jugar hasta el final del juego, y no reasigna lanzamientos a ramas más prometedoras para una exploración más profunda; en la terminología de aprendizaje de refuerzo , la estrategia de búsqueda de Maven podría considerarse "simulación de Monte Carlo truncada". Una verdadera estrategia MCTS es innecesaria porque el final del juego se puede resolver. La búsqueda superficial se debe a que el autor de Maven argumenta [1] que, debido a la rápida rotación de letras en la bolsa de uno, normalmente no es útil buscar más de 2 capas de profundidad, porque si en cambio uno buscara más profundamente, por ejemplo, 4 capas, la varianza de las recompensas será mayor y las simulaciones tomarán varias veces más tiempo, mientras que solo ayudarán en unas pocas situaciones exóticas: "Sostenemos que si se requiere una situación extrema como CACIQUE para ver el valor de una simulación de cuatro capas, entonces no vale la pena hacerlo". Como el valor del tablero se puede evaluar con una precisión muy alta en Scrabble, a diferencia de juegos como Go , Es poco probable que simulaciones más profundas cambien la evaluación inicial).
La fase "previa al final del juego" funciona casi de la misma manera que la fase "intermedia del juego", excepto que está diseñada para intentar generar una buena situación de final del juego.
La fase de "final del juego" comienza tan pronto como no quedan fichas en la bolsa. En juegos de dos jugadores, esto significa que los jugadores pueden deducir de la distribución inicial de letras las fichas exactas que se encuentran en los estantes de cada uno. Maven utiliza el algoritmo de búsqueda B-star para analizar el árbol del juego durante la fase de final del juego.
Maven ha utilizado varios algoritmos para la generación de movimientos , pero el que se ha mantenido es el algoritmo DAWG . El algoritmo GADDAG es más rápido, pero un DAWG para inglés norteamericano ocupa solo 0,5 MB, en comparación con los 2,5 MB de un GADDAG. Esto supone una diferencia significativa para los juegos de descarga, mientras que la ventaja de velocidad no es importante. (Tenga en cuenta que poco importante no significa que la diferencia sea pequeña, sino simplemente que los usuarios no pueden notar la diferencia. El GADDAG es quizás el doble de rápido, pero ambos algoritmos son lo suficientemente rápidos).
La primera versión (1986) de Maven utilizó un conjunto de aproximadamente 100 patrones para asignar valores a los racks. Cada mosaico tenía un valor (27 patrones). Cada duplicado tenía un valor (22 patrones). Había patrones para los triplicados y cuádruples para las letras que tenían suficiente representación en la bolsa. Finalmente, la combinación QU era un patrón.
Poco después de la primera versión, Maven adquirió términos de evaluación de bastidores para el equilibrio de vocales y consonantes y la distribución Q/U. El equilibrio de vocales y consonantes era una búsqueda en una tabla basada en el recuento de vocales y consonantes que quedaban en el bastidor. La distribución Q/U variaba los valores de Q y U utilizando una búsqueda en una tabla indexada por la cantidad de cada una que quedaba en la bolsa.
Poco tiempo después, Maven adquirió un evaluador de duplicación de mosaicos. La idea era variar un rack dependiendo de la probabilidad de obtener duplicados. Por ejemplo, A es generalmente mejor que I como mosaico, pero si quedan 7 A y solo 2 I en la bolsa, entonces tal vez deberíamos preferir mantener la I.
El ajuste de parámetros se realizó ajustando los valores para predecir el total de puntajes futuros. Hoy en día, esto se llamaría aprendizaje de diferencia temporal .
Este diseño de evaluación de racks fue original de Maven y tuvo mucho éxito a la hora de competir con los campeones humanos de la época.
El diseño fue ampliado posteriormente por otros investigadores. Mark Watkins defendió lo que llamó "patrones de sinergia de mosaicos". Se trata de combinaciones como ADES que forman la base de muchas palabras de alto puntaje. Se trata de una extensión natural del diseño, que mejora significativamente el juego. El conjunto de patrones de Maven se expandió gradualmente desde el conjunto básico de 100 a más de 400.
Desde entonces, Maven ha adoptado una arquitectura completamente diferente, propuesta por John O'Laughlin e implementada en Quackle. Se trata de la arquitectura "exhaustiva", en la que el programa tiene un parámetro de evaluación de rack diferente para cada una de las 3 millones de combinaciones posibles de 0 a 7 mosaicos. Con los avances en potencia informática durante la última década, se ha hecho posible ajustar conjuntos de parámetros tan grandes.
La desventaja de utilizar un enfoque exhaustivo es que Maven perdió la capacidad de variar las evaluaciones en función de las fichas que quedaban en la bolsa. El punto es que el evaluador exhaustivo de racks no tiene términos que relacionen el valor de un rack con las posibles extracciones de la bolsa.
La versión de Maven de la evaluación exhaustiva de racks ha añadido esa capacidad. En Maven, cada rack tiene su propio evaluador de líneas, donde el valor de ese rack varía en función de la probabilidad de obtener un duplicado, la probabilidad de obtener una vocal y la probabilidad de obtener Q y U. Este sistema tiene 5 parámetros por rack, lo que supone unos 15 millones de parámetros en total.
El gran campeón humano Ron Tiekert había estudiado el Scrabble jugando posiciones individuales docenas de veces y tabulando los resultados. Sugirió que con la velocidad de Maven, debería ser posible automatizar ese proceso en partidas nocturnas. Brian Sheppard denominó a este proceso "simulación", aunque en el backgammon se lo conoce como "rollout" y en el Go como "playout".
El proceso consistía en seleccionar N movimientos candidatos utilizando la heurística de puntuación+rack. Luego, se jugaban esos movimientos cientos o miles de veces para ver qué candidato se desempeñaba mejor. Se puede variar la profundidad del juego para adaptarlo a su propósito; jugar dos o cuatro movimientos por adelantado para tener una buena idea sobre la diferencia de puntos, o jugar hasta el final del juego para medir las posibilidades de ganar.
A mediados de los años 90, las computadoras se habían vuelto lo suficientemente rápidas como para que Maven usara la simulación para elegir movimientos en juegos competitivos bajo controles de tiempo de torneo. Las mejoras algorítmicas fueron importantes para escalar la simulación para este propósito. La innovación más importante fue variar el número de ensayos que se les daba a los candidatos para que los candidatos más exitosos recibieran más esfuerzo. También fue útil controlar los racks para que todos los movimientos de los candidatos se muestrearan contra la misma distribución imparcial.
El análisis de los juegos jugados por el motor de simulación de Maven sugiere que Maven ha superado el nivel de habilidad de los campeones humanos.
El juego fuerte en los finales de Scrabble es mucho más difícil de lo que parece. En teoría, los finales son un juego de información perfecta, por lo que el algoritmo de poda Alfa-Beta debería funcionar. Pero en la práctica, Alfa-Beta funciona mal en Scrabble.
El problema con Alpha Beta es que algunos finales de Scrabble requieren 14 movimientos para completarse y no es posible investigar tan profundamente. Esto no es meramente una posibilidad teórica. Cuando un jugador está "atascado" con una ficha, entonces jugar todas las fichas restantes es imposible. En esa situación, la estrategia óptima para ambos lados suele ser jugar una ficha en cada turno.
Maven utiliza un enfoque diferente. El algoritmo de búsqueda B* es un algoritmo de profundidad selectiva y ampliación progresiva que garantiza la búsqueda de soluciones óptimas para juegos de dos jugadores cuando se pueden calcular límites superiores e inferiores para los valores de cada posición.
Resulta que es posible estimar límites superiores e inferiores en las posiciones de los finales. Estos límites son correctos (es decir, el valor verdadero se encuentra dentro del intervalo) para la abrumadora mayoría de las posiciones. Dado que B* es razonablemente robusto en presencia de un pequeño porcentaje de error en los límites, Maven puede resolver finales que otros enfoques no pueden.
Un refinamiento adicional hace que las soluciones de final de juego de Maven sean asintóticamente óptimas incluso en presencia de errores. Cuando la búsqueda B* termina con una prueba de que un movimiento es el mejor y todavía queda tiempo, Maven amplía sus estimaciones en 1 punto y busca nuevamente. Estas nuevas búsquedas suelen ser muy rápidas, porque el árbol de la búsqueda anterior sigue siendo válido en gran medida. El uso repetido de esta política identificará progresivamente los errores, comenzando con los errores más pequeños (y presumiblemente los más probables).
Cuando sólo quedan 1 o 2 fichas en la bolsa ("PEG-1" o "PEG-2"), es posible realizar búsquedas exhaustivas del espacio de estados.
El caso de un PEG-1 es importante, porque casi la mitad de todos los juegos pasan por ese estado. Maven puede reproducir dichos estados exhaustivamente en casi todos los casos. Es decir, para todos los movimientos legales, Maven puede reproducir los finales resultantes (hasta 8 para cada movimiento legal) y calcular qué lado ganará el juego en cada caso. Debido a que hay algunas situaciones (por ejemplo, dos espacios en blanco, atascado con Q) que requieren un esfuerzo adicional, el cálculo se realiza de manera progresiva. Es decir, Maven amplía su análisis primero donde la decisión es cercana y relevante.
En un PEG-2 normalmente no es posible examinar exhaustivamente todas las secuencias de movimientos, por lo que Maven va tan lejos como puede en el tiempo disponible.
Una característica de estas situaciones de fichas bajas es que resulta muy difícil reducir de forma segura la lista de movimientos legales. Por ejemplo, la jugada óptima se clasifica detrás de más de 50 movimientos según la heurística de puntuación+rack más del 1 % del tiempo.
Esta política no produce un juego que sea teóricamente perfecto, porque es imposible saber cuál debería ser la distribución inicial real de las fichas no vistas. Suponiendo que la distribución sea uniforme, es posible calcular inferencias sobre las fichas no vistas que mejoren marginalmente esa suposición.
Otra limitación es que Maven no aborda el aspecto de "información oculta" de tales situaciones. Es decir, en teoría hay situaciones en las que los jugadores maximizan las expectativas al elegir movimientos al azar según una distribución de probabilidad. Maven elige estrategias puras en cada nodo.