DEFINICION
El algoritmo MiniMax es el algoritmo más 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 teoría de juegos, Minimax es un
método de decisión para minimizar la pérdida máxima esperada en juegos con
adversario. 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.
Se utilizará una estrategia de profundidad limitada para explorar el
conjunto de jugadas. Como es imposible hacer una exploración exhaustiva de
todas las jugadas, se hace una búsqueda 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).
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 función de evaluación heurística 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 exploración. 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 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.
Funcionamiento
del algoritmo
- 1. Generación del árbol de
juego. Se generarán todos los nodos hasta llegar a un estado terminal o
determinando una profundidad concreta (poda o corte). Se considera el nodo
raíz como la situación actual del juego.
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.
En este caso el número máximo es 9.
·
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.
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.
No hay comentarios:
Publicar un comentario