Algoritmo Minimax, un jugador incansable

En teoría de juegos, Minimax es un método de decisión para minimizar la pérdida máxima esperada en juegos con adversario y con información perfecta. Este cálculo se hace de forma recursiva.

El funcionamiento de Minimax puede resumirse como elegir el mejor movimiento para ti mismo suponiendo que tu contrincante escogerá el peor para ti.

La receta del algoritmo Minimax:

1. Generación del árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal o determinando una profundidad concreta.

Vamos aplicando el algoritmo por un número fijo de iteraciones hasta alcanzar una determinada profundidad. En estas aplicaciones la profundidad suele ser el número de movimientos o los incluso el resultado de aplicar diversos pasos de planificación en un juego de estrategia.

2. Cálculo de los valores de la función de utilidad para cada nodo terminal.

Para cada resultado final, cómo de beneficioso me resulta si estamos en MAX o cuanto me perjudicará si estamos en MIN.

3. Calcular el valor de los nodos superiores a partir del valor de los inferiores. Alternativamente se elegirán los valores mínimos y máximos representando los movimientos del jugador y del oponente, de ahí el nombre de Minimax.

4 . Elegir la jugada valorando los valores que han llegado al nivel superior.

El algoritmo explorará los nodos del árbol asignándoles un valor numérico mediante una función de utilidad, empezando por los nodos terminales y subiendo hacia la raíz. La función de utilidad como se ha comentado, definirá lo buena que es la posición para un jugador cuando la alcanza.

Versiones más avanzadas como el minimax con poda alfa beta hacen que se reduzca considerablemente el número de nodos a visitar por lo que el tiempo de cálculo se reduce ampliamente.

Y para terminar comentar un ejemplo cásico, el tres en raya (juego del gato, tatetí, triqui, tres en gallo, michi, la vieja o tic tac toe). Se trata de hacer una fila de tres para ganar y evitar que el oponente la haga antes que tu.

Al aplicar el algoritmo, se suceden una serie de estados que se resumen en la fotografía. Un estado -1 significa que MAX gana, 0 empate o -1 pierde.

Se distinguen los nodos terminales con jugada finalizada y los del trayecto. En este juego se puede llegar a la profundidad máxima puesto que se trata de 9 movimientos fijos, en otros como el ajedrez o las damas es muy necesario limitar la profundidad y aplicar medidas que aumenten la eficiencia.

El código se adjunta en python muy comentado. El bloque principal, y a partir de ahi todo lo demás en el documento adjunto, es el siguiente:

b = Board()
turn = 1
while True:
	print “Turno %i.” % turn
	jugadorHumano(b, Jugador_X)
	if b.gameOver():
		break

	jugadorMaquina(b, Jugador_O)
	if b.gameOver():
	break
	turn += 1

Donde se crea una instancia del tablero, necesaria para detallar los elementos que intervienen en juego y e ir aplicando el algoritmo. Se pueden intercambiar jugadores o incluso hacer que jueguen dos máquinas o dos humanos simplemente modificando estas lineas de arriba.

En resumen.

• El minimax aporta una herramienta de proceso recursiva muy útil
• Se pueden aplicar modificaciones al algoritmo para hacerlo más eficiente

En el tres en raya:

• Gana el 1, pierde el -1 y empate 0
• La profundida máxima es de 9, como el número de jugadas posible
• La cota superior de nodos a visitar es en el peor caso (primer movimiento) 9 factoria -A> 9!
• No hay restricciones sobre la validez de un movimiento, simplemente que no se haya hecho antes, por lo que el coste del cálculo es bajo (no hay que aplicar reglas complejas).
• Almacenar las soluciones intermedias no es excesivamente complejo
• Generar los diferentes tableros con las soluciones intermedias a explorar no es costoso pero podría ser un problema en otros juegos y limitar la profundidad por memoria
• La máquina nunca pierde, el juego está completado
• Las partidas entre jugadores máquina siempre quedan en tablas.

El tiempo que tarda un jugador pc en procesar la primera jugada es de 4047,181 ms en un ordenador medio, el que tarda cuando procesa la jugada que lo hace ganador en el último movimiento 0,568 ms y cuando procesa la que lo deja en tablas 0,337. La diferencia de tiempo de cálculo entre los primeros movimientos cuando quedan muchas opciones y el resto es 8000 veces mayor, por lo que el tema de la eficiencia habrá que tocarlo.

Puedes descargar una implementación en el clásico tres en raya.

Fuente