Algoritmo MiniMax

El algoritmo minimax es una de los algoritmos de las búsquedas de adversarios, cuyo objetivo es minimizar la perdida contra adversarios en juegos, para ello hace uso de un cálculo recurrente de cada uno de sus estados sucesores para elegir el mejor movimiento. Este algoritmo hace uso de búsqueda en profundidad para explorar el conjunto de jugadas posibles es decir explora todo el árbol de juegos.

Entre las principales características que posee este algoritmo tenemos:

·         Facilidad de problemas complejos con reglas simples.

·         Pruebas contra humanos escalables

·         Existencia de un solo ganador

·         Exploración de N capas 

·         Tiempo de exploración agotado

·         Situaciones estáticas sin cambios significativos

Este algoritmo principalmente está enfocado en problemas matemáticos de juegos en donde los costos de los tiempos son poco prácticos. 

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.

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

Algoritmo NegaMax

El algoritmo de búsqueda negamax, tiene un funcionamiento similar por no decir idéntico al algoritmo minimax, lo que cambia es que posee una versión reducida en su código al no implementar las variables minimax, sino que en su reemplazo, siempre escoge la mejor opción pero realizando una intercalación en el coste de sus nodos o estados sucesores, de tal manera que niega los valores de una manera intercalada, de esta forma, aunque siempre se escoja el max, de cierta forma, se intercala escogiendo min en una instancia, y max en la siguiente, ya que al realizar la negación, la siguiente opción a elegir, se podría considerar como min.

A este tipo de algoritmo, tambien se le puede implementar la poda alfa beta, ya que en esencia es el mismo algoritmo minmax pero cambiando ligeramente su funcionamiento con una negacion intercalada en vez de una desicion intercalada, es por ello que este algoritmo también  es de busqueda con adversario y utiliza la búsqueda en profundidad planteando una heuristica, la cual determina el costo de los posibles sucesores, y dicha heuristica, también es limitada. 

Es un algoritmo basado en minimax, pero está es más compacta.

No utiliza las funciones de Max y Min, en vez de estos utiliza la siguiente función matemática que traduce en una búsqueda de la Máxima, permitiendo la posibilidad de simplificar el código:

max(a,b) == – min(-a, -b)

Maneja valores positivos para la maquina y negativos para las del adversario.