El Algoritmo Minimax y Poda Alfa-Beta

1.1.       INTRODUCCIÓN

Como hemos venido mencionado en la anterior publicación sobre búsquedas entre adversarios, existen algoritmos que hacen uso de estrategias optimas que los guien a estados objetivos, entre estos algoritmos tenemos al algoritmo minimax, este algoritmo es fundamental para contrincantes óptimos en problemas de juegos, el cual basa su teoría de las investigaciones de Claude Shannon y Alan Turing en el año de 1950.

Otro algoritmo que se utiliza en este tipo de problemas de búsquedas entre adversarios es el algoritmo Poda Alfa-Beta que es una versión mejorada del algoritmo Minimax que no necesita hacer un recorrido de todos los nodos para poder obtener una decisión óptima.

En esta publicación hablaremos sobre el algoritmo Minimax y el algoritmo Poda Alfa-Beta, sus principales características y que tipo de decisiones optimas utilizan en juegos multi-jugadores.

1.2.       OBJETIVO 

Conocer cómo funcionan los algoritmos entre adversario Minimax y Poda Alfa-Beta y en base a qué factores toman decisiones para problemas con juegos.

2.     MARCO TEÓRICO

2.1.       El 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.

Imagen 1: Algoritmo Minimax

1.1.       Decisiones Optimas en Juegos Multi-Jugador

En la actualidad muchos de los juegos son populares se orientan a más de dos jugadores, lo que intenta el algoritmo minimax es proporcionar una idea de cómo enfocar su estrategia utilizando las funcionalidades del mismo. Para explicar de una mejor manera pondré un ejemplo con tres jugadores en donde cada tendrá asignado un nodo, este para poder obtener el estado terminal tendrá que hacer uso de la función de utilidades la cual nos va a devolver un vector de utilidades, seguido de esto tendremos que analizar los estados no terminales para reconocer los movimientos que nos conducirán hacia un estado terminal con utilidades, se podría decir que el valor hacia atrás de un nodo será el vector de utilidades de cualquier estado sucesor que tiene el valor más alto para cada jugador.

Imagen 2: Ejemplo de juego con tres jugadores

1.1.       El algoritmo Poda Alfa-Beta

El algoritmo poda Alfa-Beta como ya lo habíamos mencionado anteriormente es una técnica mejorada del algoritmo Minimax en la cual es posible calcular un estado objetivo sin la necesidad de recorrer todos los nodos del árbol de juegos, este tipo de algoritmo suele utilizarse para cualquier tipo de árbol de búsqueda en profundidad y para subárboles enteros. Este algoritmo al igual que el Minimax hace uso de la búsqueda en profundidad asi que para poder encontrar un resultado solo tendremos que considerar los nodos a lo largo de un solo camino.

Entre las principales características que posee este algoritmo en comparación con el Minimax tenemos:

·         Omisión de expansión de nodos que por sus valores no pueden ser los mejores.

·         No afecta al resultado final.

·         Permite búsquedas el doble de profundas que el Minimax

·         Importancia de orden y no de valores exactos

Hay que tener en cuenta que para poder podar en un árbol que utiliza este algoritmo se debe recorrer el orden ya fijado, los valores de Max (Alfa) son los del límite inferior y los de Min (Beta) son los limites superiores. Esto quiere decir que en los niveles maximizantes solo Beta puede podar y en los niveles minimizantes solo alfa puede podar.

Imagen 3: Algoritmo Poda Alfa-Beta

CONCLUSIONES
Estos algoritmos son de suma importancia para los problemas de arboles de juegos, cada uno a sido diseñado para que los agentes puedan desenvolverse sin dificultades, el algoritmo Minimax  trata de 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 mientras que el algoritmo Poda Alfa-Beta es una version mejorada del algortimo Minimax la cual no necesita explorar todos los nodos para encontrar una solucion optima para problemas de juegos.

BIBLIOGRAFIAS

Russell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España