G. MINIMAX, NEGAMAX Y ALFA_BETA

MINIMAX

Minimax es un algoritmo aplicado a los juegos que utilizan búsqueda con adversario, permite elegir el mejor movimiento para cada jugador suponiendo que el contrincante escogerá uno peor, se usa en juegos en donde se conoce el estado del adversario.

El algoritmo se representa sobre arboles alternados en donde en cada nivel se alterna entre buscar el valor mínimo y el valor máximo, el árbol se crea cada vez que se va a realizar un movimiento(jugada), el algoritmo continua generándose hasta que algún jugador gana, se ha explorado todo el árbol, caso en el cual se aplica el movimiento, y si siguen habiendo movimientos posibles se vuelve a generar el arbol, en caso de que haya un ganador, o ya no se puedan hacer más movimientos el algoritmo termina.

El algoritmo  tiene en cuenta varios aspectos fundamentales para funcionar:

•  La Posición Inicial
• Operadores o Reglas del juego
• Estado terminal
• Función de utilidad que determina si un jugador Gana, Pierde o empata.

El algoritmo inicia generando el árbol, el valor numérico de los nodos hoja o nodos terminales los determina la función de utilidad, y desde ahí el valor de los nodos superiores se obtiene a partir de los nodos inferiores, eligiendo los valores mínimos y máximos en cada nivel, representando así los movimientos tanto del jugador como los de su oponente, al jugador que espera valores negativos se conoce como MINIMIZADOR, y el jugador que espera valores positivos se conoce como MAXIMIZADOR. Cuando entra en funcionamiento la función de utilidad, por lo general asigna los valores 0 o 1 dependiendo si la jugada lleva al jugador a perder o no.

MINIMAX ALFA/BETA

El algoritmo  ALFA/BETA es una mejora del MINIMAX que aplica la búsqueda en profundidad, es aplicado a juegos en donde existen demasiados estados posibles como para analizar todos los nodos, y no se conoce el estado del adversario.

ALFA/BETA, delimita la búsqueda, omitiendo la expansión de nodos que por sus valores no seraían escogidos por MIN o MAX, es decir que no pueden ser los mejores o los peores; se escoge algún nivel cualquiera, a los nodos de ese nivel les aplica la función heurística o función de utilidad y desde ahi empieza a subir, determinando máximos y mínimos (profundidad limitada).

ALFA/BETA trabaja con dos variables con esos respectivos nombres, MAX depende del valor de alfa, el cual se inicia en menos infinito, el valor de MIN depende del valor de beta, que se inicia en infinito positivo. para cada nodo, si el nodo es MIN, BETA toma el valor más bajo y que sea menor al valor actual de BETA, si el nodo es MAX, ALFA toma el mayor valor y que sea mayor al valor actual de ALFA. 

NEGAMAX

Es una variante del algoritmo mínimax, aunque los niveles se marquen con la clasificación MIN o MAX, para cada nodo con hijos, siempre se tomará el valor máximo y no el mínimo( funciona como si todos los niveles fueran MAX), con la condición de que en todos los niveles MAX, al valor de sus nodos se le cambia el signo, de ahi el nombre, ya que el algoritmo tomará siempre valores máximos, pero con los signos cambiados, por ejemplo si un nodo MAX tomaría el valor 5, se le asigna el -5, logrando asi el mismo efecto, ya que al tomar el mayor valor con el signo cambiado es equivalente a tomar el menor nodo, así cuando se esta en un nivel MIN, al tomar el valor mayor, realmente esta  es tomando al menor. 

Negamax se basa en la siguiente igualdad matemática:   max(x,y)= -min(-x,-y); y se le pueden aplicar podas y heurísticas para acortar su ejecución.

BIBLIOGRAFIA

• http://www.itnuevolaredo.edu.mx/takeyas/Apuntes/Inteligencia%20Artificial/Apuntes/IA/Minimax.pdf, Algoritmo Minimax, Ing. Bruno López Takeyas, consultado el 29 de abril de 2017. 
• http://www.itnuevolaredo.edu.mx/takeyas/apuntes/Inteligencia%20Artificial/Apuntes/IA/Alfa-Beta.pdf, Poda Alfa-Beta, Ing. Bruno López Takeyas, consultado el 29 de abril de 2017.
• http://tesis.uson.mx/digital/tesis/docs/20586/Capitulo3.pdf, Algoritmos de búsqueda,  consultado el 29 de abril de 2017.
• http://www.cs.upc.edu/~bejar/ia/material/trabajos/Algoritmos_Juegos.pdf, Algoritmos de Juegos, consultado el 29 de abril de 2017.