Maven es un jugador de Scrabble de inteligencia artificial , creado por Brian Sheppard. Se ha utilizado en juegos oficiales de Hasbro Scrabble con licencia.
El juego de Maven se subdivide en tres fases: la fase de "mitad del juego", la fase "antes del final del juego" y la fase del "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 usa un algoritmo rápido para encontrar todas las jugadas posibles del estante dado, y luego parte del programa llamado "kibitzer" usa heurística simple para clasificarlas en un orden aproximado de calidad. Luego, los movimientos más prometedores se evalúan mediante "simulación", en el que el programa simula el sorteo aleatorio de fichas, avanza un número determinado de jugadas y compara la distribución de puntos de los resultados de los movimientos. Al simular miles de sorteos aleatorios, el programa puede brindar una evaluación cuantitativa muy precisa de las diferentes jugadas. (Mientras que una búsqueda de Monte Carlo, Maven no utiliza la búsqueda de árbol de Monte Carloporque evalúa los árboles de juego solo en 2 capas de profundidad, en lugar de jugar hasta el final del juego, y no reasigna los lanzamientos a ramas más prometedoras para una exploración más profunda; en la terminología del aprendizaje por refuerzo , la estrategia de búsqueda de Maven podría considerarse una "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 el bolso, por lo general no es útil buscar más de 2 capas de profundidad, porque si uno busca más profundo, por ejemplo, 4 capas , la varianzade recompensas será mayor y las simulaciones llevará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 valen la pena". haciendo." 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 las 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 "a la mitad del juego", excepto que está diseñada para intentar generar una buena situación al final del juego.
La fase de "final del juego" comienza tan pronto como no quedan fichas en la bolsa. En los juegos de dos jugadores, esto significa que los jugadores ahora pueden deducir de la distribución de letras inicial las fichas exactas en los bastidores de cada uno. Maven utiliza el algoritmo de búsqueda de estrellas B para analizar el árbol del juego durante la fase final.
Maven ha utilizado varios algoritmos para la generación de movimientos, pero el que se ha atascado 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. Eso hace una diferencia significativa para los juegos de descarga, mientras que la ventaja de la velocidad no es importante. (Tenga en cuenta que sin importancia no significa que la diferencia sea pequeña, 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).