MiniMax, Negamax y Alfa/Beta

MinMax:

el algoritmo minmax es basicamente un algoritmo mayormente empleado para juegos los cuales se basan en búsqueda con adversario, ello que quiere decir, que este algoritmo es mas amplia mente utilizado en juegos los cuales consta de 2 jugadores como pueden ser el 3 en raya, el ajedrez, el Backgammon, entre otros.

lo que plantea este algoritmo, es que mediante la implementacion de una heuristica al problema planteado, se determine un coste de los posibles sucesores de un estado o nodo inicial, de tal manera que en el algoritmo se exploraran 2 soluciones intercaladas las cuales se podrían tomar representativamente como el juego entre dos jugadores, y teniendo en cuenta ello, se intercala la opción del camino a seguir eligiendo la mejor opción suponiendo que es el jugador principal el que realiza el movimiento, e inmediatamente después a ese movimiento, el algoritmo realiza la peor opción a seguir, o la opción mas baja, en representación de un oponente el cual por beneficio propio, realizara la jugada que mas le convenga a el, la cual se traduciría en la que menos le conviene al jugador principal.

de esta manera el algoritmo necesitaría una heuristica que explorara las primeras opciones de tal forma que decida cual camino es mejor y cual es menos conveniente de tal forma que intercale los nodos a explorar, ello conlleva a una búsqueda limitada para el optimo funcionamiento de dicho algoritmo, ya que explorar todas las opciones posibles y determinar el siguiente paso a seguir conllevaría un elevado coste en cuanto a tiempo y espacio, lo cual dificulta su procesamiento y obliga a una limitación de la búsqueda en profundidad realizada.

Alfa-Beta:

El algoritmo de búsqueda alfa beta es también un algoritmo de búsqueda con adversario, básicamente , es una mejora del algoritmo minimax. como uno de los inconvenientes que tenia el algoritmo minimax , es que cuando exploraba las posibles soluciones aplicando la heuristica y la búsqueda en profundidad, no podía realizar una búsqueda muy profunda, ya que el coste de procesamiento seria alto, lo cual conlleva a la limitación de la búsqueda, el algoritmo alfa beta propone una alternativa a la hora de explorar las posibles soluciones de un nodo y realizar la exploración de los posibles estados sucesores.

Este algoritmo, contiene dos variables adicionales las cuales son alfa y beta, en alfa, se nos almacenara el estado o nodo de menor coste en  un estado maximizante, y analogamente, en beta se almacena el estado o nodo de menor coste en un estado minimizante, esto se tiene en cuenta, para que al momento de realizar la búsqueda en profundidad con la heuristica planteada, descarte o pode, los nodos o estados alfa o beta según corresponda ya que es irrelevante explorarlos, debido a que si en un principio no contienen la mejor o peor solución dependiendo del estado en el que se encuentre la búsqueda, no vale la pena realizar la búsqueda por esos nodos o estados los cuales por definición, no aportan a la solución del algoritmo de búsqueda planteado.

De esta manera se consigue reducir substancialmente el coste al realizar la búsqueda en profundidad, permitiendo hacer una búsqueda mas detallada y mejor planteada, de tal manera que el algoritmo de búsqueda nos podrá ofrecer un mejor desenvolvimiento en el problema que se plantee, y a la hora de desarrollar la solución.

Negamax:

en cuanto al 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.

Bibliografia:

• https://es.wikipedia.org/wiki/Minimax
• https://es.wikipedia.org/wiki/Negamax
• https://es.wikipedia.org/wiki/Poda_alfa-beta
• https://www.google.com.co/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&cad=rja&uact=8&ved=0ahUKEwje-LPijdPTAhXDQSYKHRLiAP4QFgg2MAM&url=http%3A%2F%2Fwww.cs.upc.edu%2F~bejar%2Fia%2Fmaterial%2Ftrabajos%2FAlgoritmos_Juegos.pdf&usg=AFQjCNEm7wauufae6gNq81y9ZHTr0RXxNg&sig2=RS-GDxh4OI9qRCjG5i_Hsw