Jugar juegos de estrategia con el algoritmo Minimax

En esta lección, exploraremos un algoritmo popular llamado minimax . También aprenderemos algunas de sus características complementarias amigables para el vecindario, como puntajes heurísticos , profundización iterativa y poda alfa-beta . Usando estas técnicas, podemos crear un agente de juego más flexible y poderoso. Podrá competir en muchos desafíos, incluido el juego de estrategia Isolation.

En mi publicación anterior Cómo ganar sudoku, aprendimos cómo enseñar a las computadoras a resolver el rompecabezas de Sudoku. Si no lo ha leído, siga adelante y déle una lectura rápida. Pero esa fue realmente solo una forma de mojarnos los pies, antes de sumergirnos en métodos más sofisticados de agentes de juego. ¡Especialmente aquellos métodos que pueden hacer movimientos estratégicos contra un oponente!

No te quedes varado

Isolation (o Isola) es un juego de mesa de estrategia por turnos en el que dos jugadores intentan encerrar a su oponente en un tablero de damas de 7x7. Eventualmente, ya no pueden hacer un movimiento (aislándolos así).

Cada jugador tiene una pieza, que puede mover como una reina en el ajedrez: de arriba hacia abajo, de izquierda a derecha y en diagonal. Hay tres condiciones bajo las cuales las piezas se pueden mover:

  1. No pueden colocar su pieza en una casilla ya visitada.
  2. No pueden cruzar cuadrados ya visitados (pasarlos en diagonal está bien).
  3. No pueden cruzar la pieza del otro.

En la imagen de arriba, puedes ver en los cuadrados negros que ambos jugadores han colocado sus piezas en varias partes del tablero. Pero a medida que avanzaba el juego, muestra que el jugador amarillo todavía tiene tres movimientos posibles. Arriba y a la derecha, un cuadrado a la derecha y dos cuadrados a la derecha. Pero el jugador azul no tiene opciones. Por lo tanto, el jugador amarillo es el ganador aquí.

Ahora bien, esto puede parecer un juego simple, y para ser honesto, lo es. No es como si estuviéramos jugando al póquer o Starcraft. Sin embargo, todavía hay una enorme cantidad de movimientos posibles que cualquiera de los jugadores puede realizar en cualquier momento durante el juego.

En acertijos como el Sudoku, hay una "respuesta" que queremos resolver. Pero no hay respuesta cuando se trata de juegos de estrategia.

Estamos jugando contra otro oponente, como una persona, una computadora o un detective de gatos. Esto requiere estrategia y un poco de reflexión sobre cómo puede resultar el juego a medida que avanza.

Estos juegos pueden evolucionar y producir una cantidad absurda de posibles resultados. Por lo tanto, debemos pensar en cómo podemos elegir el mejor movimiento posible, sin perder la cantidad de tiempo que los gatos tardaron en poblar la Tierra.

¡De acuerdo, no más gatos!

Mighty Minimax y amigos

Ahora que sabes cómo jugar Isolation, echemos un vistazo a cómo podemos usar el algoritmo minimax ; un elemento básico en la comunidad de IA. También veremos las puntuaciones heurísticas , la profundización iterativa y la poda alfa-beta . Junto con estos, podemos construir un agente de IA competitivo.

Minimax

El algoritmo minimax es muy popular para enseñar a los agentes de IA cómo jugar juegos de estrategia por turnos. La razón es que tiene en cuenta todos los movimientos posibles que los jugadores pueden realizar en un momento dado durante el juego. Con esta información, intenta minimizar la ventaja del jugador oponente mientras maximiza la del agente en cada turno que el agente de IA llega a jugar.

Ahora, ¿cómo se ve esto?

Bueno, de manera similar a cómo un agente de IA jugaría un juego como el Sudoku, podemos modelar los próximos movimientos posibles que cualquiera de los jugadores puede hacer a través de un árbol de búsqueda . Sin embargo, necesitaremos usar un árbol de búsqueda con amplitud variable, o en otras palabras, el ancho de un nivel de árbol. La razón es que hay un número variable de movimientos que cada jugador puede realizar en un momento dado durante el juego.

El árbol que se muestra arriba representa los próximos movimientos disponibles durante un juego de Aislamiento. Tiene una cuadrícula de 2x3, con el cuadrado inferior derecho inalcanzable. Como puede ver, los dos jugadores son un círculo azul y una cruz roja.

La parte superior del árbol (el nodo raíz) ilustra un movimiento realizado por el jugador rojo. El nivel medio ilustra los próximos movimientos posibles del jugador azul. Y el tercer nivel ilustra los posibles movimientos del jugador rojo, dado el movimiento anterior realizado por el jugador azul.

Cada estado del juego o nodo en el árbol tiene información sobre qué jugador tiene más que ganar con cualquier movimiento potencial.

Ahora te estarás preguntando, ¿qué diablos son esos triángulos debajo de cada movimiento?

El triángulo hacia abajo representa una ubicación en el árbol donde minimax minimizará la ventaja del oponente. Considerando que, los triángulos hacia arriba son los lugares donde minimax maximiza la ventaja del agente.

Pero minimax solo puede conocer la ventaja de cualquiera de los jugadores si conoce los caminos en el árbol que conducen a la victoria de cualquiera de los jugadores. Esto significa que el minimax debe atravesar la parte inferior del árbol para cada posible serie de movimientos. A continuación, tiene que asignar una puntuación (por ejemplo, +1 para una victoria y -1 para una derrota) y propagar esos números a lo largo del árbol. De esta manera, cada estado del juego o nodo en el árbol tiene información sobre qué jugador tiene más que ganar con cualquier movimiento potencial.

En esta imagen, podemos hacer un par de observaciones. El primer minimax asigna un número a los resultados finales del juego en los nodos hoja . Luego los propaga hacia arriba a través del árbol, realizando minimizaciones y maximizaciones en el camino. Una vez que minimax termine de llenar el árbol, siempre que sea el turno del agente de IA, sabrá qué movimientos probablemente conducirán a una victoria o una derrota.

El segundo nivel después del nodo raíz muestra los próximos movimientos posibles para el jugador azul (nuestro agente de IA). Nuestro agente quiere maximizar las puntuaciones disponibles durante su turno. Por lo tanto, elegiría el movimiento representado en el nodo más a la derecha después del nodo raíz. ¡Super guay!

¿Pero tiene sentido simplemente asignar un +1 o -1 a los resultados del juego? ¿No debería esta puntuación tener en cuenta cómo se gana o se pierde el juego?

Alerta de spoiler: ¡la respuesta es sí!

Puntuaciones heurísticas

En el mundo de los juegos de estrategia, una puntuación heurística es esencialmente un valor subjetivo que asignamos a algún estado del juego. Este valor se basa en nuestra comprensión de cómo se gana y se pierde el juego. Al elegir una puntuación heurística bien pensada, podemos enseñar a nuestro agente de IA cómo seleccionar mejor sus próximos movimientos mientras juega el juego Aislamiento.

Ahora, probablemente hay un número ilimitado de puntuaciones heurísticas que podríamos obtener. Pero aquí solo veremos algunos de ellos, aparte de la puntuación ingenua (NS) de +1 y -1.

Una idea podría ser contar todos los próximos movimientos posibles que tiene cada jugador en un momento dado, ya que más movimientos posibles significan menos posibilidades de estar aislado. A esto lo llamaremos puntuación de movimiento abierto (OMS) .

Otra idea podría ser utilizar el valor obtenido de OMS y restar el número de próximos movimientos posibles que tiene el oponente. La razón es que cada jugador quiere aumentar su cantidad de movimientos mientras disminuye la de su oponente. A esto lo llamaremos la puntuación mejorada (IS) .

La figura anterior muestra las tasas de victoria en muchos juegos de aislamiento simulados jugados entre agentes de IA que utilizan diferentes puntuaciones heurísticas. Ahora puede ver qué tan diferentes fueron nuestras puntuaciones durante el juego real. Pero hubo algunas puntuaciones heurísticas que superaron a las que se nos ocurrieron

Curiosamente, los dos primeros son casi exactamente iguales a la puntuación mejorada. Los llamaremos puntaje mejorado agresivo (AIS) y puntaje mejorado súper agresivo (SAIS) . Pero hay una ligera diferencia entre estos puntajes y el original. Los dos puntajes superiores aplican un factor de dos y tres al valor con el que restas (el número de movimientos disponibles para el oponente) al calcular el puntaje mejorado.

¡Puede descubrir un "factor agresivo" óptimo para aplicar al calcular esta puntuación!

Otra alerta de spoiler: existen mejores valores.

Pero, ¿qué pasa si obtenemos una puntuación heurística que requiere mucho tiempo para calcular? ¿Y si el árbol es enorme? ¿Nuestro agente de IA tendrá suficiente tiempo para encontrar sus próximos mejores movimientos, sin dejar de ser lo suficientemente receptivo durante el juego?

Profundización iterativa

Ahora sabemos que nuestro agente de IA puede modelar todos los movimientos posibles utilizando un árbol de búsqueda y la puntuación heurística correspondiente de sus nodos. Pero desafortunadamente, cuando jueguemos a Isolation, nuestro árbol será enorme. ¡Se necesitaría más tiempo para buscar en el árbol y calcular estos valores que años desde el Big Bang!

Ingrese a la profundización iterativa : la estrategia de administración del tiempo para los agentes de juegos. Al usar este método, podemos reducir el tiempo de cálculo y búsqueda a un tiempo máximo de nuestra elección. De esta manera, nuestro agente de inteligencia artificial puede responder al menos tan rápido como podría hacerlo un humano.

Pero, ¿cómo funciona la profundización iterativa?

Permite que minimax se mueva de nivel a nivel y calcule puntuaciones heurísticas hasta un cierto límite de tiempo. Una vez que se alcanza este límite de tiempo, el agente de IA se ve obligado a usar el mejor movimiento que descubrió mientras se movía cada vez más profundo en el árbol.

Ahora bien, esto proporciona una idea de lo difícil que puede ser. Crear un agente de IA que sea lo suficientemente inteligente y receptivo para los juegos de estrategia puede ser bastante complicado, incluso para los magos de la IA. Especialmente si tales juegos contienen un mundo de posibilidades.

Desafortunadamente, la cantidad de movimientos que el agente de IA puede "imaginar" en el futuro es limitada. Entonces, es posible que pueda tomar una decisión que conduzca a su desaparición. Este es un fenómeno bien conocido llamado efecto horizonte . Pero aún tenemos que analizar posiblemente el algoritmo de reducción de tiempo más eficaz que se utiliza al buscar árboles.

Poda Alfa-Beta

De acuerdo, esas son pasas y no ciruelas pasas, pero aún así, ¿cómo fueron estas cosas? Quiero decir, en serio, ¿un grupo de blues con pasas?

Es posible que ya haya adivinado que la poda alfa-beta no tiene nada que ver con las ciruelas pasas y más con la reducción del tamaño (poda) de nuestro árbol de búsqueda. Cuando tenemos un árbol de búsqueda muy grande, resulta que no siempre es necesario recorrer todos los nodos cuando se usa minimax.

Necesitamos darle a minimax la capacidad de dejar de buscar una región particular del árbol cuando encuentre el mínimo o máximo garantizado de ese nivel en particular.

Si podemos hacer eso, esto puede reducir en gran medida el tiempo de respuesta de nuestro agente de inteligencia artificial y mejorar el rendimiento.

¿Cómo funciona la poda alfa-beta?

El algoritmo minimax se mueve a través del árbol utilizando la búsqueda en profundidad. Lo que significa que atraviesa el árbol de izquierda a derecha, y siempre va lo más profundo que puede. Luego descubre valores que deben asignarse a los nodos directamente encima de él, sin siquiera mirar otras ramas del árbol.

La poda alfa-beta permite que minimax tome decisiones tan buenas como las que podría hacer minimax por sí solo, pero con un mayor nivel de rendimiento.

Considere la siguiente imagen, en la que tenemos un árbol con varias puntuaciones asignadas a cada nodo. Algunos nodos están sombreados en rojo, lo que indica que no es necesario revisarlos.

En la parte inferior izquierda del árbol, minimax mira los valores 5 y 6 en el nivel máximo inferior. Determina que se debe asignar 5 al nivel mínimo justo encima de él. Tiene sentido.

Pero, después de mirar 7 y 4 de la rama derecha del nivel máximo, se da cuenta de que al nodo de nivel mínimo anterior se le debe asignar un valor máximo de 4. Dado que el segundo nivel máximo justo encima del primer nivel mínimo tomará el máximo entre 5 y como máximo 4, está claro que elegirá 5. Después de esto, continuará atravesando el árbol para realizar exactamente el mismo conjunto de operaciones dentro de las otras ramas del árbol.

A continuación se muestra la representación algorítmica de minimax con poda alfa-beta.

El uso de este método proporciona una manera fácil de reducir el espacio de búsqueda de nuestro agente de inteligencia artificial. De esta forma, la poda alfa-beta permite que minimax tome buenas decisiones que minimax podría hacer por sí solo, pero con un mayor nivel de rendimiento.

Isola-ter

Hemos explorado cómo construir nuestro propio agente de IA que pueda jugar el juego Isolation a un nivel bastante competitivo. Al usar el algoritmo minmax, vimos cómo el agente de IA puede modelar el juego y puede tomar decisiones basadas en una puntuación heurística. También aprendimos cómo determinar una heurística bien definida para nuestra tarea dada (Aislamiento).

Pero también descubrimos que sería demasiado intenso computacionalmente dejar que minimax se volviera loco. Así que tuvimos que usar técnicas como la profundización iterativa y la poda alfa-beta. Esto obligaría a nuestro agente de inteligencia artificial a realizar el siguiente movimiento en un período de tiempo razonable. Pero, ¿qué pasa si queremos que nuestro agente de IA tenga una mayor tasa de victorias y al menos sea tan receptivo como un humano?

Bueno, hay otras técnicas que podríamos explorar para aumentar la tasa de ganancias de nuestro agente, así como el tiempo de respuesta. Tocamos la idea de ajustar los parámetros de nuestra puntuación heurística (¿recuerdas el "factor agresivo"?). Incluso podríamos llegar a una puntuación heurística mejor adaptada para jugar Isolation.

También hay propiedades reflectantes relacionadas con los posibles movimientos en el tablero de aislamiento. Estos se vuelven evidentes cuando analizamos el árbol de búsqueda completamente poblado, lo que nos permitiría cortar potencialmente muchas ramas del árbol de búsqueda. Además, si actualizamos nuestro hardware, nuestro agente de inteligencia artificial sería más rápido y, por lo tanto, podría explorar más posibilidades.

Si desea entrar en los detalles esenciales de cómo implementar esto usted mismo, eche un vistazo al código que escribí para resolver este problema para mi Udacity Artificial Intelligence Nanodegree. Puede encontrarlo en mi repositorio de GitHub.

¡Hola, soy Grant! Soy un desarrollador y cuantificador independiente. Visite mi sitio web en //freelancequant.com. ¡Salud!