Algoritmo MiniMax Y Poda Alfabeta

Algoritmo MiniMax

Definición                         
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áximaesperada 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 unabú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).

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 quesomos 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 jugadasvendrá determinada por la profundidad a la que lleguemos en cada exploración. Cuanto más 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 elnú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 nodossuperiores 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 nodosterminales 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 seresumen en la fotografía. 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 más eficiente
En el juego de las tres en raya:
Gana el +1, pierde el -1 y empate 0
La profundidad máxima es de 9, como el número de jugadas posible
No hay restricciones sobre la...