Ensayo minimax, negamax y poda alfa-beta

LOS ALGORITMOS MINIMAX, NEGAMAX Y PODA ALFA-BETA

La teoría de juegos es un concepto bastante amplio y basado en diversos fundamentos, sin embargo muchos matemáticos la definen como los procesos que llevan a un individuo a ganar ya sea a forma de azar o estrategia basándose en las decisiones que este tome. En el siguiente escrito se abordara un algoritmo y dos de sus derivaciones que se despliegan de la teoría de juegos, estos son minimax, negamax y poda alfa-beta. 

Minimax, negamax y poda alfa-beta son todos métodos de la teoría de juegos que se implementaron en algoritmos gracias a Claude Shannon y Alan Turing en el año 1950, ellos fueron los pioneros en la investigación, creación e implementación de los programas poseedores de inteligencia artificial, lograron crear el algoritmo minimax y lo adaptaron para que fuera capaz de jugar ajedrez. El primer algoritmo creado bajo la siguiente sentencia de bloque de código fue minimax: 

El algoritmo minimax es un proceso de decisión que se manifiesta a través de una máquina. Las elecciones que el algoritmo toma están orientadas a la manera en la que la heurística está estructurada de forma que logre minimizar la perdida máxima en un juego con adversario. 

Este algoritmo explora todos los posibles caminos que se pueden tomar mediante nodos y escoge el que logre minimizar la pérdida intentando siempre bloquear la jugada del competidor.

 A continuación se exponen algunas de sus características más importantes:

 •  Está muy cerca de simular problemas reales ya que          es capaz de generar duda en el adversario 

• Es usado frecuentemente con humanos 

• Resulta cómodo para una persona real en el momento de usarlo 

• Es recursivo 

• La información es completa, esto quiere decir que cada jugador sabe en que estado se encuentra el adversario.

 En cuanto al proceso el algoritmo minimax sigue el siguiente: 

1. Define un nodo raíz, este nodo cuenta con profundidad cero

 2. El árbol va expandiendo sus nodos hasta llegar a la cota de profundidad que se le asigno.

3. La función de evaluación se comprueba para que devuelva valores elevados y analice la mejor situación

4. Se realiza el cálculo de los nodos superiores teniendo en cuenta el valor de los nodos inferiores 

5. Se eligen los valores máximos y mínimos representando los movimientos para ambos jugadores 

6. Finalmente la jugada se elige teniendo en cuenta los valores que están en el nivel superior. 

Los algoritmos mejorados del minimax son: 

1. NEGAMAX 

El algoritmo negamax es una mejora compacta del algoritmo minimax, utiliza toda su definición pero cambia los nodos de los valores de los nodos max de esta forma: max(x,y) = -min(-x,-y), consiguiendo el mismo resultado que el minmax, pero tomando el menor.

PODA ALFA-BETA El algoritmo alfa-beta es la otra versión mejorada del algoritmo minimax, lo que hace es acortarlo a la mitad, explora el árbol y elimina los nodos que no son necesario visitar, esto hace que el algoritmo sea más eficiente, rápido y consistente. 

Entre las características de este algoritmo podemos mencionar: 

• Se aplica a arboles cuya profundidad sea n 

• La búsqueda mínima se basa en el concepto primero en profundidad 

• Existen dos valores: alfa y beta cuyo objetivo es acotar la búsqueda 

• Alfa representa la cota inferior y beta la cota superior 

Algunas ventajas que comparten los tres algoritmos serian: 

•Ventajas y desventajas 

•En la mayoría de los casos la maquina queda invicta 

•Es capaz de aprender del adversario 

•Aprende con base en la información que recolecta Y desventajas: 

•El algoritmo es de difícil implementación 

•Solo puede enfrentarse a un adversario a la vez

Como conclusión puede afirmarse que los algoritmos Negamax y Poda alfa-beta son versiones mejoradas del clásico minimax, los tres poseen características positivas que los hicieron la primera elección de los desarrolladores de video juegos y las bancas de inversión, las cuales calculan el balance de la inversión por estos métodos. Obviamente la tecnología avanza y se seguirán implementando y desarrollando algoritmos mucho más complejos y que soporten más capacidad que los que se mencionaron este ensayo pero minimax es la base de la que parten muchas de esas nuevas tecnologías debido a su eficacia y adaptación en el usuario.