Desde el advenimiento de la Inteligencia Artificial (IA), el juego ha sido una de las aplicaciones más interesantes de la IA.
Los primeros programas de ajedrez fueron escritos por Claude Shannon y Alan Turing en 1950, casi tan pronto como las computadoras se volvieron programables.
Juegos como ajedrez, tic-tac-toe y Go son interesantes porque ofrecen una abstracción pura de la competencia entre los dos ejércitos.
Es esta abstracción la que hace del juego un área atractiva para la investigación de IA.
En este artículo, repasaremos los conceptos básicos del algoritmo Minimax junto con el funcionamiento del algoritmo.
También echaremos un vistazo a la optimización del algoritmo minimax, la poda alfa-beta.
¿Qué es el algoritmo Minimax?
Minimax es un algoritmo recursivo que se utiliza para elegir un movimiento óptimo para un jugador suponiendo que el otro jugador también está jugando de manera óptima.
Se utiliza en juegos como tic-tac-toe, go, ajedrez, Isola, damas y muchos otros juegos para dos jugadores.
Estos juegos se llaman juegos de información perfecta porque es posible ver todos los movimientos posibles de un juego en particular.
Puede haber partidas para dos jugadores que no sean de información perfecta, como el Scrabble, porque el movimiento del oponente no se puede predecir.
Es similar a cómo pensamos cuando jugamos una partida: «si hago este movimiento, mi oponente solo puede hacer estos movimientos», y así sucesivamente.
Minimax se llama así porque ayuda a minimizar la pérdida cuando el otro jugador elige la estrategia que tiene la pérdida máxima.
Terminología
- Árbol de juego: Es una estructura en forma de árbol que consta de todos los movimientos posibles que le permiten moverse de un estado del juego al siguiente estado.
Un juego se puede definir como un problema de búsqueda con los siguientes componentes:
- Estado inicial: Comprende la posición del tablero y muestra de quién es el movimiento.
- Función sucesora: Define cuáles son los movimientos legales que un jugador puede hacer.
- Estado terminal: Es la posición del tablero cuando el juego termina.
- Función de utilidad: Es una función que asigna un valor numérico al resultado de un juego. Por ejemplo, en ajedrez o tic-tac-toe, el resultado es una victoria, una pérdida o un empate, y estos pueden ser representados por los valores +1, -1 o 0, respectivamente. Hay juegos que tienen una gama mucho más amplia de resultados posibles; por ejemplo, las utilidades en el backgammon varían de +192 a -192. Una función de utilidad también se puede llamar función de pago.
¿Cómo funciona el algoritmo?
Hay dos jugadores involucrados en un juego, llamado MIN y MAX. El jugador MAX intenta obtener la puntuación más alta posible y MIN intenta obtener la puntuación más baja posible, es decir, MIN y MAX intentan actuar uno frente al otro.
El proceso general del algoritmo Minimax es el siguiente:
Paso 1: Primero, genere el árbol de juego completo comenzando con la posición actual del juego hasta los estados terminales. Así es como se ve el árbol del juego para el juego tic-tac-toe.
Entendamos la terminología definida en términos del diagrama anterior.
- El estado inicial es la primera capa que define que el tablero está en blanco.
- La función sucesora enumera todos los movimientos sucesores posibles. Se define para todas las capas del árbol.
- El Estado terminal es la última capa del árbol que muestra el estado final, es decir, si el jugador MÁXIMO gana, pierde o empata con el oponente.
- Las utilidades en este caso para los estados de terminal son 1, 0 y -1 como se discutió anteriormente, y también se pueden usar para determinar las utilidades de los otros nodos.
Paso 2: Aplique la función utilidad para obtener los valores de utilidad para todos los estados de terminal.
Paso 3: Determine las utilidades de los nodos superiores con la ayuda de las utilidades de los nodos terminales. Por ejemplo, en el diagrama de abajo, tenemos las utilidades para los estados terminales escritas en los cuadrados.
Calculemos la utilidad para el nodo izquierdo (rojo) de la capa sobre el terminal. Dado que es el movimiento del MIN del jugador, elegiremos el mínimo de todas las utilidades. Para este caso, tenemos que evaluar MIN{3, 5, 10}, que sabemos que es ciertamente 3. Así que la utilidad para el nodo rojo es 3.
De manera similar, para el nodo verde en la misma capa, tendremos que evaluar MIN{2,2} que es 2.
Paso 4: Calcule los valores de utilidad con la ayuda de hojas considerando una capa a la vez hasta la raíz del árbol.
Paso 5: Eventualmente, todos los valores respaldados llegan a la raíz del árbol, es decir, al punto más alto. En ese momento, MAX tiene que elegir el valor más alto.
En nuestro ejemplo, solo tenemos 3 capas, por lo que llegamos inmediatamente a la raíz, pero en los juegos reales, habrá muchas más capas y nodos. Así que tenemos que evaluar MAX{3,2} que es 3.
Por lo tanto, el mejor movimiento de apertura para MAX es el nodo izquierdo(o el rojo). Este movimiento se llama la decisión minimax, ya que maximiza la utilidad tras la suposición de que el oponente también está jugando de manera óptima para minimizarla.
En resumen,
Decisión Minimax = MAX{MIN{3,5,10}, MIN{2,2}}
= MAX{3,2}
= 3
Código Psuedocode:
function minimax(node, depth, maximizingPlayer) if depth = 0 or node is a terminal node return the utility of the node if maximizingPlayer bestValue := ?? for each child of node v := minimax(child, depth ? 1, FALSE) bestValue := max(bestValue, v) return bestValue else (* minimizing player *) bestValue := +? for each child of node v := minimax(child, depth ? 1, TRUE) bestValue := min(bestValue, v) return bestValue
Optimización
Los árboles de juegos son, en general, muy lentos de construir, y es solo para juegos simples que se pueden generar en poco tiempo.
Si hay \(b\) movimientos legales, es decir,, \(b\) nodos en cada punto y la profundidad máxima del árbol es \(m\), el tiempo de complejidad del algoritmo minimax es del orden \(b^m (S(b^m))\).
Para frenar esta situación, hay algunas optimizaciones que se pueden agregar al algoritmo.
Afortunadamente, es viable encontrar la decisión real de minimax sin siquiera mirar cada nodo del árbol del juego. Por lo tanto, eliminamos nodos del árbol sin analizar, y este proceso se denomina poda.
Poda alfa-beta
El método que vamos a buscar en este artículo se llama poda alfa-beta.
Si aplicamos poda alfa-beta a un algoritmo minimax estándar, devuelve el mismo movimiento que el estándar, pero elimina (poda) todos los nodos que posiblemente no afecten la decisión final.
Entendamos la intuición detrás de esto primero y luego formalizaremos el algoritmo. Supongamos que tenemos el siguiente árbol de juego:
En este caso,
Decisión Minimax = MAX{MIN{3,5,10}, MIN{2, a, b}, MIN{2,7,3}}
= MAX{3, c,2}
= 3
¡Te sorprenderías!
¿Cómo podríamos calcular el máximo con un valor faltante? Este es el truco. MIN{2, a, b} ciertamente sería menor o igual a 2,es decir, c<=2 y por lo tanto MAX{3, c, 2} tiene que ser 3.
La pregunta ahora es ¿realmente necesitamos calcular c? Por supuesto que no.
Podríamos haber llegado a una conclusión sin mirar esos nodos. Y aquí es donde entra en escena la poda alfa-beta.
Algunas definiciones:
Alfa: Es la mejor opción hasta ahora para el reproductor MAX. Queremos obtener el mayor valor posible aquí.
Beta: Es la mejor opción hasta ahora para MIN, y tiene que ser el valor más bajo posible.
Nota: Cada nodo debe realizar un seguimiento de sus valores alfa y beta. Alfa solo se puede actualizar cuando es el turno de MAX y, de manera similar, beta solo se puede actualizar cuando es la oportunidad de MIN.
¿Cómo funciona la poda alfa-beta?
- Inicializar alpha = – infinity y beta = infinity como los peores casos posibles. La condición para podar un nodo es cuando alfa se vuelve mayor o igual a beta.
- Comience asignando los valores iniciales de alfa y beta a root y dado que alfa es menor que beta, no lo podamos.
- Lleve estos valores de alfa y beta al nodo hijo de la izquierda. Y ahora desde el valor de utilidad del estado de terminal, actualizaremos los valores de alfa y be, por lo que no tenemos que actualizar el valor de beta. De nuevo, no podamos porque la condición sigue siendo la misma. Del mismo modo, el tercer nodo hijo también. Y luego, volviendo a la raíz, establecemos alfa=3 porque ese es el valor mínimo que alfa puede tener.
- Ahora, alfa=3 y beta=infinito en la raíz. Así que no podamos. Llevando esto al nodo central, y calculando MIN{2, infinito}, obtenemos alfa = 3 y beta = 2.
- Poda el segundo y tercer nodos hijos porque alfa es ahora mayor que beta.
- Alfa en la raíz permanece 3 porque es mayor que 2. Llevando esto al nodo secundario más a la derecha, evalúe MIN{infinito, 2} = 2. Actualiza beta a 2 y alfa permanece 3.
- Poda el segundo y tercer nodos hijos porque alfa es ahora mayor que beta.
- Por lo tanto, obtenemos 3, 2, 2 en los nodos MIN izquierdo, central y derecho, respectivamente. Y calculando MAX{3,2,2}, obtenemos 3. Por lo tanto, sin siquiera mirar cuatro hojas, pudimos encontrar correctamente la decisión minimax.
Pseudocódigo (Fuente: Curso NPTEL):
evaluate (node, alpha, beta) if node is a leaf return the utility value of node if node is a minimizing node for each child of node beta = min (beta, evaluate (child, alpha, beta)) if beta <= alpha return beta return beta if node is a maximizing node for each child of node alpha = max (alpha, evaluate (child, alpha, beta)) if beta <= alpha return alpha return alpha
Conclusión
Los juegos son muy atractivos y escribir programas de juego es quizás aún más emocionante. Lo que las carreras de Grand Prix son para la industria del automóvil, el juego es para la IA.
Así como no esperaríamos que un coche de carreras funcione perfectamente en una carretera con baches, no debemos esperar que los algoritmos de juego sean perfectos para cada situación.
También lo es el algoritmo minimax. Puede que no sea la mejor solución para todo tipo de juegos de ordenador que necesitan tener IA.
Pero dada una buena implementación, puede crear un competidor difícil.