Algoritmo MiniMax
DEFINICION
El algoritmo MiniMax es el algoritmo ms conocido (y utilizado) para juegos de
2 adversarios, movimientos alternos (ahora tu, ahora yo). No se puede
utilizar en juegos donde hay azar, sino perfectamente definido como las tres
en raya y el ajedrez.
En teora de juegos, Minimax es un mtodo de decisin para minimizar la
prdida mxima esperada en juegos con adversario. Este clculo 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.
Se utilizar una estrategia de profundidad limitada para explorar el conjunto de
jugadas. Como es imposible hacer una exploracin exhaustiva de todas las
jugadas, se hace una bsqueda limitada en profundidad. Significa que en lugar
de estudiar todas las posibles situaciones hasta el fin de la partida, se buscaran
por ejemplo todas las situaciones de aqu 3 turnos (un modo de poda).
FUNCIONAMIENTO DEL ALGORITMO MINIMAX
Aclaraciones Iniciales
Identificaremos a cada jugador como el jugador MAX y el jugador MIN. MAX
ser el jugador que inicia el juego, el cual supondremos que somos nosotros, y
nos marcaremos como objetivo encontrar el conjunto de movimientos que
proporcionen la victoria a MAX (nosotros) independientemente de lo que haga
el jugador MIN.
Deber existir una funcin de evaluacin heurstica que devuelva valores
elevados para indicar buenas situaciones, y valores negativos para indicar
situaciones favorables al oponente.
La calidad de nuestras jugadas vendr determinada por la profundidad a la que
lleguemos en cada exploracin. Cuanto mas profunda sea, mejor jugaremos,
pero mayor coste tendr el algoritmo.
En este juego de las tres en raya se puede llegar a la profundidad mxima
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.
Funcionamiento del algoritmo
1. Generacin del rbol de juego. Se generarn todos los nodos hasta
llegar a un estado terminal o determinando una profundidad concreta (poda o
corte). Se considera el nodo raz como la situacin actual del juego.
Vamos aplicando el algoritmo por un nmero fijo de iteraciones hasta alcanzar
una determinada profundidad. En estas aplicaciones la profundidad suele ser el
nmero de movimientos o los incluso el resultado de aplicar diversos pasos de
planificacin en un juego de estrategia. En este caso el nmero mximo es 9.
2. Clculo de los valores de la funcin de utilidad para cada nodo
terminal.Para cada resultado final, cmo 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 elegirn los valores mnimos y mximos
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 asignndoles un valor numrico
mediante una funcin de utilidad, empezando por los nodos terminales y
subiendo hacia la raz.
La funcin de utilidad como se ha comentado, definir lo buena que es la
posicin para un jugador cuando la alcanza.
Versiones ms avanzadas como el minimax con poda alfa beta hacen que se
reduzca considerablemente el nmero de nodos a visitar por lo que el tiempo
de clculo se reduce ampliamente.
Al aplicar el algoritmo, se suceden una serie de estados que se resumen en la
fotografa. Un estado -1 significa que MAX gana, 0 empate o -1 pierde.
Resumen
El minimax aporta una herramienta de proceso recursiva muy til
Se pueden aplicar modificaciones al algoritmo para hacerlo ms eficiente
En el juego de las tres en raya:
Gana el +1, pierde el -1 y empate 0
La profundidad mxima es de 9, como el nmero de jugadas posible
No hay restricciones sobre la validez de un movimiento, simplemente
que no se haya hecho antes, por lo que el coste del clculo 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 podra ser un problema en otros juegos y limitar la
profundidad por memoria
La mquina nunca pierde, el juego est completado
Las partidas entre jugadores mquina siempre quedan en tablas.
Explicacin ms detallada del funcionamiento del algoritmo.
Supongamos un partida de las tres en raya y que ahora le toca el turno del
ordenador. Como nodo padre (raz) ponemos la situacin del tablero, y como
nodo hijos los posibles movimientos que puede hacer el ordenador (el
ordenador es el jugador MAX). En el siguiente nivel, por cada movimiento que
ha hecho el ordenador en el nivel anterior, suponemos los posibles
movimientos que puede hacer el jugador humano (Jugador MIN). As
seguiremos hasta llegar a un nodo terminal, que es cuando hay un desenlace
de la partida (fin de la misma). Puede pasar que gane el ordenador, el humano
o empate. Como se puede apreciar a cada nivel se alterna el humano y la
maquina, es por eso que se llame el algoritmo Minimax.
Vamos a suponer con un cuadrado los nodos MAX y con un crculo los nodos
MIN.
Cada vez que llegamos a un nodo terminar hay que realizar un evaluacin
(mediante una funcin) y lo que hace esa evaluacin es sopesar que tal buena
es la solucin a la que conduce el nodo terminal, y para poder valorarla se le
asigna un valor numrico. En este caso de las tres en raya podramos utilizar
estos valores:
+1. Cuando gana el Ordenador
0 Cuando se produce empate
-1 . Cuando gana el Humano.
El algoritmo de la imagen superior evala cada nivel del rbol de abajo a
arriba. Y en los niveles MAX elegir los caminos que le lleven a puntuaciones
de la evaluacin ms alta, que en este caso MAX es lo que favorece al
ordenador. En los niveles MIN tratar de elegir los caminos donde la evaluacin
sea mas baja para perjudicar al jugador humano.
El Algoritmo empieza la evaluacin del ltimo nivel. Podemos ver que gana la
maquina en el primero y cuarto nodo. Subimos al nivel superior MAX, por lo
que podemos al padre el valor superior, en este caso como solo hay un nodo se
pone el valor. Cuando subimos al siguiente nivel que es Min, ponemos el
de valor menor (Min es el jugador Humano). Y como el nodo Padre es MAX,
selecciona el de valor mayor, en este caso el nodo de la derecha con valor 0,
por lo que el siguiente movimiento es el indicado en ese nodo.
Una vez el jugador humano seleccione casilla, se vuelve a realizar este
proceso.
VENTAJAS ALGORITMO MINIMAX
Capacidad de aprender de acuerdo a una base de datos histrica de
movimientos realizados.
Algoritmo casi infalible
DESVENTAJAS ALGORITMO MINIMAX
Algoritmo de complejidad elevada a la hora de implementar.
Es de aprendizaje lento
Solo vale para enfrentarse a un oponente a la vez.
MEJORAS DEL ALGORITMO MINIMAX
Hay muchas tcnicas para mejoras la inteligencia y el rendimiento del
algoritmo minimax, como puede ser por ejemplo:
Poda Alfa-beta
Para juegos con un factor de ramificacin elevado, esta profundidad no podr
ser muy grande, ya que el clculo necesario para cada decisin ser
prohibitivo. Su tiempo de exploracin ser muy grande. Para mejorarlo hay que
utilizar heursticos con poda, es decir se utilizar una tcnica de ramificacin y
poda.
Poda de inutilidades, es una evolucin de la Poda Alfa-beta
Bsqueda Sesgada
Algoritmo NegaMax, se trata de una versin mas compacta del
minimax. En vez de utilizar dos rutinas(una para Max y otra para MIN), lo que
hace es utilizar la puntuacin negada utilizando la relacin matemtica:
Max(a,b) = -min(-a,-b)
Aunque es una versin reducida de minimax es posible aplicarle la poda AlfaBeta.
Continuacin Heurstica
Bajada progresiva
Etc.
En teora de juegos, Minimax es un mtodo de decisin para minimizar la
prdida mxima esperada en juegos con adversario y con informacin perfecta.
Este clculo 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. Generacin del rbol de juego. Se generarn todos los nodos hasta llegar a
un estado terminal o determinando una profundidad concreta.
Vamos aplicando el algoritmo por un nmero fijo de iteraciones hasta alcanzar
una determinada profundidad. En estas aplicaciones la profundidad suele ser el
nmero de movimientos o los incluso el resultado de aplicar diversos pasos de
planificacin en un juego de estrategia.
2. Clculo de los valores de la funcin de utilidad para cada nodo terminal.
Para cada resultado final, cmo 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 elegirn los valores mnimos y mximos 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 asignndoles un valor numrico
mediante una funcin de utilidad, empezando por los nodos terminales y
subiendo hacia la raz. La funcin de utilidad como se ha comentado, definir lo
buena que es la posicin para un jugador cuando la alcanza.
Versiones ms avanzadas como el minimax con poda alfa beta hacen que se
reduzca considerablemente el nmero de nodos a visitar por lo que el tiempo
de clculo se reduce ampliamente.
Y para terminar comentar un ejemplo csico, 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
fotografa. 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 mxima 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 cdigo se adjunta en python muy comentado. El bloque principal, y a partir
de ahi todo lo dems en el documento adjunto, es el siguiente:
?
0
1
0
2
0
3
0 b = Board()
4 turn = 1
0 while True:
5
print Turno %i. % turn
0
jugadorHumano(b, Jugador_X)
6
if b.gameOver():
0
break
7
0
jugadorMaquina(b, Jugador_O)
8
if b.gameOver():
0
break
9
turn += 1
1
0
1
1
1
2
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 mquinas o dos humanos
simplemente modificando estas lineas de arriba.
En resumen.
o
El minimax aporta una herramienta de
proceso recursiva muy til
Se pueden aplicar modificaciones al
algoritmo para hacerlo ms eficiente
En el tres en raya:
o
Gana el 1, pierde el -1 y empate 0
La profundida mxima es de 9, como el
nmero 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 clculo 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 podra ser un problema en
otros juegos y limitar la profundidad por
memoria
La mquina nunca pierde, el juego est
completado
Las partidas entre jugadores mquina
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 clculo 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.
ALGORITMO MINIMAX
Algoritmo de decision
para minimizar la prdida maxima aplicada en
juegos de adversarios
Informacin completa (cada jugador conoce el estado del otro)
Eleccin del mejor movimiento
para cada jugador, suponiendo que el
contrincante escoger el peor
El espacio de estados se
representa mediante rboles alternados,
donde:
o Nodo:
Representa
una
situacin del juego
o Sucesores de un nodo:
Situaciones del juego a las que
aplicando sus reglas
o Nivel:
Contiene todas
se accede
por
movimientos legales
las situaciones posibles para uno
de los
jugadores
El algoritmo Minimax es un procedimiento recursivo y el corte
recursin est dado por alguna de las siguientes condiciones:
o Gana algn jugador
o Se han explorado N capas,
siendo N el lmite establecido
de la
o Se ha agotado el tiempo
o Se ha llegado a una
de exploracin
situacin esttica donde no hay
grandes cambios
de un nivel a otro.
Representacin de los juegos
Posicin inicial.
Conjunto
de
operadores
reglas
del
juego (definen movimientos legales)
Estado terminal
Funcin
de
utilidad,
ej.
gana,
pierde,
empata
Pasos del Algoritmo Minimax
1. Generacin
del rbol de juego. Se generarn todos los nodos hasta
llegar a un estado terminal.
2. Clculo
de los valores de la funcin de utilidad para cada nodo
terminal.
3. Calcular
el valor de los nodos superiores a partir del valor de los
inferiores.
Alternativamente
se
elegirn
los
valores
mnimos
mximos 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 asignndoles un valor
numrico mediante una funcin de utilidad, empezando por los
nodos terminales y subiendo hacia la raz.
Colocar 0 1 en los nodos terminales dependiendo si gana MIN o
MAX
La funcin de utilidad definir lo buena que es la posicin para un
jugador cuando la alcanza.
Se requiere de una estrategia
que garantice llegar a estados
terminales ganadores independientemente
de
lo que
haga el
oponente.
Un valor positivo indica la ventaja de un jugador y uno negativo la
ventaja del otro.
El
jugador
que
espera
valores
positivos
se
conoce
como
negativos
se
conoce
como
maximizador
El
jugado
que
espera
valores
Minimizador
El maximizador busca movimientos que lo conduzcan al mayor
nmero positivo
El minimizador busca movimientos que lo conduzcan al menor
nmero negativo
P. ejemplo:
Nivel MAX
2
2
1
7
Nivel MIN
Nivel MAX
El maximizador:
O puede esperar a llegar a un valor de 8 o Sabe que el
minimizador puede escoger un movimiento que lo
lleve a un
valor de 1
Desde el punto de vista de el maximizador, el minimizador puede
escoger 2 1
Los resultados de un nivel determinan la accin y el resultado del
nivel inmediato superior
Clculo de valores de la funcin de utilidad
Calcular el valor minimax del nodo J: V(J)
SI J es Terminal, V(J) ev(J)
SI NO
Genera los sucesores de J: J1, J2, Jn
EJEMPLO
Evala V(J1), V(J2), , V(Jn)
de izq a der
Funcionamiento
Minimax
en un rbol generado para un juego
SI J es nododeMax
ENTONCES
imaginario.
V(J) max[V(J1), V(J2),
, V(Jn)]
SI J es nodo Min ENTONCES
Los posibles valores de la funcin de utilidad tienen un rango de [1-9].
V(J) min[V(J1), V(J2),
En los movimientos del
contrincante suponemos que escoger los
movimientos que minimicen nuestra utilidad
, V(Jn)]
En nuestros movimientos suponemos que escogeremos los movimientos
que maximizan nuestra utilidad.
1er. Paso: Calcular los nodos terminales, en verde.
2. Paso: Calcular el cuarto nivel, movimiento MIN, minimizando lo
elegido (5, 2 y 1).
3er. Paso: Calcular el tercer nivel, movimiento MAX, maximizando
la
utilidad (5, 9).
El segundo nivel es un movimiento MIN (5, 3 y 1).
Finalmente llegamos al primer nivel,
el movimiento actual, elegiremos
el nodo que maximize nuestra utilidad (5).
Aplicacin: El Juego del Gato
Dos jugadores MIN y MAX
Los jugadores colocan fichas en un tablero de
3X3
MAX usa las fichas X
MIN usa las fichas O
MAX gana
Reglas:
Inicialmente el tablero est vaco
MAX empieza y se alternan los
movimientos
MAX gana si obtiene una lnea de 3 Xs
MIN gana si obtiene una lnea de 3 Os
Existe la posibilidad de empate
MIN gana
Empate
Espacio de Estado para el juego del gato
Procedimiento
Se desarrolla una bsqueda por niveles, generando los nodos del cada nivel
Se aplica una funcin de evaluacin a cada nodo
La funcin de evaluacin considera los siguientes factores:
Nmero de casillas restantes
Posicin de casillas vacas
La funcin de evaluacin devolver los siguientes valores:
Positivos
altos:
Si
la
situacin
de uno de los
jugadores es ventajosa
Negativos altos: Si la situacin del otro jugador es ventajosa
Cero: Si ninguno de los jugadores tiene ventaja
Funcin de evaluacin para el juego del gato
Si s no es ganadora para cualquiera de los jugadores (MAX o MIN):
f(s)=No. filas abiertas para MAX - No. Filas,
f(s)= No. Lneas que no contiene una O No.
esto es:
Si s es ganadora para el jugador MAX
f(s)= (mayor nmero positivo posible)
Si s es ganadora para el jugador MIN
f(s)=
-(mayor nmero negativo posible)
MAX elegir los nodos de mayor evaluacin
MIN elegir los nodos de menor evaluacin
Caso prctico de Funcin de evaluacin para el juego del
Se define la funcin de evaluacin:
f(s)=NMAX(s)-NMIN(s)
donde:
S: Situacin o distribucin del tablero
f(s):Funcindeevaluacindeltablero (nodo del espacio de estados)
NMAX(s):
No.
de
filas,
columnas
diagonalesabiertasparaMAX(dondean
puede ganar)
NMIN(s): No. de filas, columnas o diagonales
abiertas
ganar)
para
MIN(dondeanpuede
1.Etapa del Espacio de Estados
2. Etapa del Espacio de Estados
3. Etapa del Espacio de Estados
