TEORÍA DE LOS MÉTODOS
ALGORITMO DE MINIMAX
De forma más detallada, la idea de Minimax consiste en comenzar en la posición actual del
juego y usar el generador de movimientos legales para generar las posibles posiciones sucesivas
hasta un cierto límite de niveles (si es posible, porque el juego lo permita, se desarrolla el árbol
completo de juego hasta las posiciones finales). A continuación, se aplica una función de
evaluación estática a los últimos estados obtenidos, que es capaz de decir lo bueno o malo que
es cada estado, y se elige la mejor posición para el jugador correspondiente, llevando los valores
un nivel hacia atrás para continuar la evaluación en todos los niveles anteriores.
Habitualmente, se suele trabajar con una función de evaluación que devuelve valores positivos
para indicar buenas situaciones para el jugador que hace uso del algoritmo, y valores negativos
para indicar buenas situaciones para el adversario. Así planteado, el objetivo es maximizar el
valor de esta función estática sobre las posibles jugadas que se pueden hacer desde la posición
actual del juego.
De este mecanismo es de donde viene el nombre del algoritmo: dada la función evaluadora
estática, el jugador que hace uso del algoritmo intenta maximizar su valor, mientras que el
adversario intenta minimizarlo. En un árbol de juego donde los valores de la función evaluadora
se calculan en relación al jugador maximizante, se maximiza y minimiza alternadamente de un
nivel a otro hasta llegar al nivel actual de juego (cada nivel (pares o impares) corresponde a
estados producidos por la acción previa de un jugador, y donde el contrincante debe decidir el
siguiente paso).
Formalmente, los pasos del algoritmo Minimax son:
1. Generación del árbol de juego: A partir del nodo que representa el estado actual, se generan
todos los nodos hasta llegar a un estado terminal (si no podemos afrontar la generación del
árbol completo, es posible aplicar los pasos siguientes sobre una sección del mismo,
aunque entonces no podremos asegurar la optimalidad de los resultados).
2. Se calculan los valores de la función de evaluación para cada nodo terminal (O las hojas
que hayamos conseguido si no hemos podido construirlo entero) del árbol construido.
3. Se evalúan los nodos superiores a partir del valor de los inferiores. Según si estos nodos
pertenecen a un nivel MAX o un nivel MIN, se elegirán los valores mínimos y máximos
representando los movimientos del jugador y del oponente.
4. Se repite el paso 3 hasta llegar al nodo superior (estado actual).
5. Se selecciona la jugada-nodo directamente accesible desde el nodo actual que optimiza el
valor de la evaluación.
La mayoría de juegos interesantes tienen árboles de juego excesivamente grandes, de forma que
no podemos expandir completamente el árbol hasta llegar a los nodos terminales. Por ello, suele
ser común usar un algoritmo de profundidad limitada que solo expande algunos niveles del
árbol, sin llegar a los nodos terminales. Pero en este caso, ¿cómo se calcula entonces la utilidad
de un movimiento determinado?
Normalmente, para poder trabajar con una expansión limitada y poder usar algoritmos como
Minimax se hace uso de funciones de evaluación que calculan la utilidad de estados no
terminales, es decir, estiman el valor de una acción.
Otra posible generalización es hacia juegos donde no hay suma nula o hay más de 2 jugadores.
En estos casos suele ser común considerar nodos que disponen de valores de utilidad como
tuplas, y cada jugador intenta maximizar su propia componente, lo que a veces podría llevar a
estrategias entre jugadores.
ALGORITMO DE MONTE CARLO
El problema que presenta un algoritmo como Minimax, y otros algoritmos similares, es que el
tamaño del árbol de jugadas/estados puede ser tan grande que tanto la construcción como la
búsqueda dentro del árbol se vuelva impracticable, algo que ocurre con relativa facilidad si el
juego tiene un mínimo de complejidad (por ejemplo, un alto promedio de movimientos
disponibles por turno), haciendo que el tamaño del árbol crezca exponencialmente por niveles.
Como respuesta a este tipo de aproximaciones hace unos años surgió la técnica de Monte Carlo
Tree Search (Búsqueda en Árboles con Monte Carlo) que ofrece algunas ventajas:
Se puede aplicar a juegos con un factor de ramificación tan grande que resultan
inabordables con las técnicas tradicionales anteriores.
se puede configurar para que se detenga después de una cantidad de tiempo prefijada,
haciendo que con tiempos mayores se obtengan jugadores más fuertes.
No requiere necesariamente de un conocimiento específico del juego, por lo que puede ser
utilizado como motor de juego general.
Es adaptable a juegos que incorporan aleatoriedad en las reglas.
Y también algunas desventajas insalvables:
Es un método probabilístico, por lo que no siempre tiene porqué encontrar la solución
óptima.
Si realizar simulaciones de jugadas es costoso, el proceso completo puede ser inabordable.
El origen de este método se encuentra en [Abramson], donde, en vez de usar una función de
evaluación estática, combinaba una búsqueda minimax con un modelo probabilístico para
generar al azar jugadas completas.
Una versión simplificada de este algoritmo se consigue haciendo que la recompensa esté
limitada a 3 posibles valores: 1, cuando el jugador gana; 0, cuando el jugador pierde; y 0.5,
cuando se produce un empate entre ambos jugadores.
