Menu
in

Teorema Minimax: Mínima pérdida, máximo resultado

Si te interesa la inteligencia artificial, tal vez quieras ver esto…

Una queja bastante frecuente en los videojuegos es que la inteligencia artificial de los oponentes toma malas decisiones. Por ese motivo es que en algunos casos directamente hacen trampa, pero a veces también sucede lo contrario, y presentan estrategias muy efectivas en juegos a los que podemos considerar como «simples». Una de las razones es la aplicación del teorema Minimax, un algoritmo que tiene el objetivo de minimizar la pérdida máxima esperada en juegos de dos participantes, y con información perfecta para ambas partes.


Muchos juegos ocultan información a los participantes como parte de su mecánica. Sin ir demasiado lejos, piensa en el «fog of war» de juegos clásicos (StarCraft y Civilization vienen a la mente). Ese recurso le permite a la inteligencia artificial conjurar 20 o 30 unidades por arte de magia sin que te enteres (entre otras cosas), y su eliminación es un paso esencial, ya sea enviando unidades a explorar, o desarrollando tecnologías que cancelan su efecto (como los Satélites en Civ).

¿Pero qué sucede cuando la información es perfecta? ¿Cómo se comporta una inteligencia artificial cuando no hay nada que ocultar, y todos los elementos de la partida son conocidos desde el principio? Una de las tantas posibilidades para el desarrollador de turno es la implementación del teorema Minimax. La descripción oficial nos habla de un «método de decisión para minimizar la pérdida máxima esperada», y eso puede parecer sencillo en la superficie, pero merece una exploración más profunda:


Teorema Minimax, soluciones óptimas para juegos de suma cero


El canal BitBoss hace un excelente trabajo resumiendo al algoritmo Minimax, y la mejor parte es que le toma menos de cuatro minutos. Básicamente, Minimax funciona en juegos de suma cero, o sea, que nuestra ganancia o ventaja se convierte en pérdida para el oponente. El ajedrez es un ejemplo clásico de juego de suma cero con información perfecta, pero el vídeo nos lleva por una ruta más sencilla, usando como referencia al ta-te-ti.

Cada fase de la partida puede ser definida con un número, positivo para un jugador, y negativo para el otro. La estrategia del algoritmo Minimax busca seleccionar la mejor jugada disponible, asumiendo por completo que el oponente también seleccionará la mejor jugada en su contra. Si una inteligencia artificial Minimax alcanza la victoria con un número positivo, sus decisiones tratarán de seguir la ruta que favorezca a ese número.


Usando Minimax, la IA logra la victoria con una cruz en el centro (tercera ruta desde arriba)

El gráfico nos muestra los últimos seis movimientos posibles de una inteligencia artificial en una partida de ta-te-ti. Cuatro de ellos expresan una victoria para la IA (amarillo) con una condición de 1, y los otros dos para el jugador humano (azul), con -1. Los movimientos se analizan de abajo hacia arriba, o de atrás hacia adelante: Como a la inteligencia artificial sólo le queda un movimiento, los valores para cada uno se mueven al paso anterior. Siguiendo la misma lógica, el jugador humano posee dos movidas que le garantizan un -1, y una tercera que lo obliga a escoger 1. Por lo tanto, la IA se asegura la victoria colocando presión en esa vía, que comienza con una cruz en el centro.

Obviamente, este es un ejemplo demasiado simple, y posible sólo gracias a los límites naturales del ta-te-ti. Si trasladamos el método Minimax a juegos de alta complejidad como el ajedrez o el go, el número de estados a verificar crece de forma exponencial, y la aplicación de Minimax se vuelve inviable. Una posible solución es limitar la profundidad de exploración, y en términos generales, es más que suficiente para darle una paliza a los n00bs.


Escrito por Lisandro Pardo

Leave a Reply