Algorítmo Minimax

Cuando nos referimos a juegos como el Tic tac toe, en una situación donde estamos con nuestros amigos, y hacemos una apuesta de dinero, podríamos llegar a cuestionarnos ¿Cómo hago para asegurar mi victoria?, ¿Existirá acaso alguna forma que me garantiza ganar siempre? Las respuestas a éstas integorrantes las podría suministrar un famoso método conocido como el minimax.

Árbol_Minimax

El minimax es un método diseñado para juegos de búsqueda, donde se involucre a dos jugadores. Básicamente, el método genera un árbol completo con todos los movimientos posibles a partir de un estado actual de un jugador A. Los movimientos posibles generados se les denomina ramas, donde cada rama está a su vez conformada por otros nodos, los nodos padre de estas ramas son las futuras jugadas de A, los hijos de las jugadas de A, son las jugadas de B, que a su vez sus hijos son las jugadas de A, y así sucesivamente hasta que llegue a una profundidad máxima deseada (hojas).

El objetivo del método es buscar el mejor camino para un jugador actual donde maximíze su ganancia, y al tiempo maximíze el perjuicio de su oponente. El método se basa en información previa de ambos jugadores, como el estado de juego de algún jugador.

 

Pseudocódigo del Minimax:
Pseudocódigo_minimax

Explicación del algorítmo:

La función minimax recibe cuatro parámetros que son el tablero del juego, la profundidad actual, la máxima profundidad, puntaje elegido y movimiento elegido. Lo primero que hace es verificar si hemos llegado a la profundidad máxima (caso base), si es el caso entonces elegirá la rama cuyo puntaje fue el máximo encontrado para el jugador actual (if(better(the_score,best_score)) de todas las llamadas recursivas (minimax(.,.,.,.); En caso contrario, genera una lista que contiene todos los nodos de un nivel (usando la función generate_moves(board)) a partir de la posición actual de jugador, ahora si la lista generada es nula, significa que la posición actual de jugador es una hoja (caso base) y determina la puntuación encontrada para jugador actual en ese punto (evaluation(board)), en caso contrario comienza el recorrido de cada uno de los nodos de un nivel que fueron generados a partir de la posición actual del jugador (el for). El recorrido de cada nodo genera nuevos niveles en cada llamado recursivo, (de izquierda a derecha y de arriba abajo).

Al final elige la puntuación máxima del jugador actual, y a partir de ésta puntuación se ilustra el mejor camino que puede tomar para el jugador actual. La puntuación máxima, así como su respectivo movimiento se almacenan para ser utilizados (chosen_score y chosen_move).

Minimax con cortes Alpha-Beta:

Existen juegos de búsqueda, cuyo árbol es tan enorme, que analizarlo todo no sería óptimo, ya sea por el tiempo que tarda en dar la respuesta, o el uso masivo de los recursos de la máquina donde se procesa. Tal caso se presenta en un juego muy conocido; el ajedréz, se dice que se necesitaría de una memoria con capacidad de almacenamiento infinita para considerar todas las jugadas posibles a partir de una posición inicial, además del tiempo que habría que esperar para que encuentre dicho movimiento óptimo. Por tal razón se es indispensable pensar alguna forma que nos permita una solución en un tiempo considerable además de un uso razonable de recursos.

Aparece un algorítmo denominado “Minimax Alpha-Beta”, que básicamente realiza cortes a cuyas ramas qué representan jugadas no significativas para el jugador actual. Es importante resaltar, que además de éste algorítmo para la poda, se debe definir la profundidad máxima deseada en la cual nuestro algoritmo no debe sobrepasar.
Árbol_alpha

Pseudocódigo Minimax Alpha-Beta:

Psudocódigo_Alpha

Eficiencia de Alfa-Beta

  • Supongamos que el árbol tiene profundidad d y cada nodo (excepto los nodos hoja) tiene exactamente b sucesores. Si no realizamos poda alfa-beta, deberemos revisar nodos hoja.
  • La eficiencia de la poda dependerá obviamente del orden en que se generan los nodos.

¿Cuál es el mejor caso?

¿Y el peor?

  • Es posible demostrar que en el caso promedio, alfa-beta permite aumentar aproximadamente a la profundidad de la búsqueda revisando la misma cantidad de nodos que sin poda.

 

Link de apoyo