Juego de mesa Inteligencia artificial: el algoritmo Minimax: 8 pasos

2024 Autor: John Day | [email protected]. Última modificación: 2024-01-30 08:42

¿Alguna vez te has preguntado cómo se fabrican las computadoras contra las que juegas en ajedrez o damas? Bueno, no busque más, este Instructable le mostrará cómo hacer una inteligencia artificial (IA) simple pero efectiva utilizando el algoritmo Minimax. Al usar el algoritmo Minimax, la IA realiza movimientos bien planificados y pensados (o al menos imita un proceso de pensamiento). Ahora, podría darte el código para la IA que hice, pero eso no sería divertido. Explicaré la lógica detrás de las elecciones de la computadora.

En este Instructable, lo guiaré a través de los pasos sobre cómo hacer una IA para Othello (AKA Reversi) en Python. Debe tener un conocimiento intermedio de cómo codificar en Python antes de abordar este proyecto. Aquí hay algunos buenos sitios web que puede consultar para prepararse para este Instructable: w3schools o learnpython. Al final de este Instructable, deberías tener una IA que hará movimientos calculados y debería poder derrotar a la mayoría de los humanos.

Dado que este Instructable se ocupará principalmente de cómo hacer una IA, no explicaré cómo diseñar un juego en Python. En cambio, daré el código del juego en el que un humano puede jugar contra otro humano y modificarlo para que puedas jugar un juego en el que un humano juega contra la IA.

Aprendí cómo crear esta IA a través de un programa de verano en Columbia SHAPE. Me lo pasé bien allí, así que eche un vistazo a su sitio web para ver si estaría interesado.

Ahora que hemos eliminado la logística, ¡comencemos a codificar!

(Pongo un par de notas en las imágenes así que asegúrate de mirarlas)

Suministros

Esto es facil:

1) Computadora con un entorno de Python como Spyder o IDLE

2) Descarga los archivos del juego Othello desde mi GitHub

3) Tu cerebro con paciencia instalada

Paso 1: descargue los archivos necesarios

Cuando ingrese a mi GitHub, debería ver 5 archivos. Descarga los 5 y colócalos en la misma carpeta. Antes de ejecutar el juego, abra todos los archivos en el entorno de spyder.

Esto es lo que hacen los archivos:

1) othello_gui.py este archivo crea el tablero de juego para que los jugadores jueguen (ya sea humano o computadora)

2) othello_game.py este archivo juega dos computadoras entre sí sin el tablero de juego y solo muestra la puntuación y las posiciones de movimiento

3) ai_template.py aquí es donde pondrás todo tu código para hacer tu IA

4) randy_ai.py esta es una IA prefabricada que elige sus movimientos al azar

5) othello_shared.py un montón de funciones prefabricadas que puede usar para hacer su IA, como verificar los movimientos disponibles, la puntuación o el estado del tablero

6) Los otros tres archivos: Puma.py, erika_5.py y nathan.py, creados por mí, Erika y Nathan respectivamente desde el programa SHAPE, son tres AI diferentes con códigos únicos

Paso 2: Cómo abrir y jugar Python Othello

Una vez que tenga todos los archivos abiertos, en la esquina inferior derecha de la pantalla, escriba "ejecutar othello_gui.py" y presione enter en la consola de IPython. O en la terminal de Mac, escriba "python othello_gui.py" (después de estar en la carpeta correcta, por supuesto). Entonces debería aparecer un tablero en su pantalla. Este modo es el modo humano contra humano. La luz va en segundo lugar y la oscuridad primero. Mira mi video si estás confundido. iEn la parte superior, está la puntuación de cada mosaico de color. Para jugar, haz clic en un espacio de movimiento válido para colocar una ficha allí y luego dale la computadora a tu oponente, quien hará lo mismo y repetirá.

Si no sabes cómo jugar a Othello, lee estas reglas en el sitio web de ultraboards:

Las negras siempre se mueven primero. Se hace un movimiento colocando un disco del color del jugador en el tablero en una posición que "flanquea" uno o más de los discos del oponente. Un disco o una fila de discos se flanquean cuando están rodeados en los extremos por discos del color opuesto. Un disco puede flanquear cualquier número de discos en una o más filas en cualquier dirección (horizontal, vertical, diagonal)…. (terminar de leer en su sitio web)

La diferencia entre el juego original y este juego de Python es que cuando no quedan movimientos válidos para un jugador, el juego termina

Ahora que puedes jugar con un amigo, creemos una IA con la que puedas jugar.

Paso 3: Algoritmo Minimax: Generación de escenarios

Antes de hablar sobre cómo escribir esto en código, repasemos la lógica detrás de esto. El algoritmo minimax es un algoritmo de seguimiento hacia atrás para la toma de decisiones y, por lo general, se utiliza en juegos de dos jugadores por turnos. El objetivo de esta IA es encontrar el siguiente mejor movimiento y los siguientes mejores movimientos hasta que gane el juego.

Ahora bien, ¿cómo determinaría el algoritmo qué movimiento es el mejor? Deténgase y piense cómo elegiría el próximo movimiento. La mayoría de la gente elegiría el movimiento que les daría más puntos, ¿verdad? O si estuvieran pensando en el futuro, elegirían el movimiento que crearía una situación en la que podrían ganar aún más puntos. La última forma de pensar es la forma en que piensa el algoritmo Minimax. Mira hacia adelante a todas las configuraciones futuras del tablero y hace el movimiento que conduciría a la mayor cantidad de puntos.

Llamé a esto un algoritmo de retroceso, porque comienza primero creando y evaluando todos los estados futuros de la placa con sus valores asociados. Esto significa que el algoritmo jugará el juego tantas veces como sea necesario (haciendo los movimientos para sí mismo y el oponente) hasta que se hayan jugado todos los escenarios del juego. Para realizar un seguimiento de todos los estados del tablero (escenarios), podemos dibujar un árbol (mira en las imágenes). El árbol en la imagen de arriba es un ejemplo simple de un juego de Connect 4. Cada configuración de tablero se llama estado de tablero y su lugar en el árbol se llama nodo. Todos los nodos en la parte inferior del árbol son los estados finales del tablero después de realizar todos los movimientos. Obviamente, algunos estados del tablero son mejores para un jugador que para el otro. Entonces, ahora tenemos que hacer que la IA elija a qué estado de la placa quiere llegar.

Paso 4: Minimax: evaluación de las configuraciones de la placa

Para dar valor a los estados del tablero, tenemos que aprender las estrategias del juego que estamos jugando: en este caso, las estrategias de Othello. Debido a que este juego es una batalla de voltear al oponente y sus discos, las mejores posiciones de disco son las que son estables y no se pueden voltear. La esquina, por ejemplo, es el lugar donde cuando se coloca un disco no se puede cambiar al otro color. Por lo tanto, ese lugar sería extremadamente valioso. Otras buenas posiciones incluyen los lados del tablero que te permitirían tomar muchas piedras. Hay más estrategias en este sitio web.

Ahora podemos asignar valores a las posiciones para cada tablero de estado del tablero. Cuando una posición está ocupada por la pieza de la IA, entonces le das un cierto número de puntos dependiendo de la posición. Por ejemplo, un estado del tablero donde la pieza de la IA está en la esquina, puedes dar una bonificación de 50 puntos, pero si estuviera en un lugar desfavorable, la pieza puede tener un valor de 0. Después de tener en cuenta todos los valores de las posiciones, le asignas un valor al estado de la placa. Por ejemplo, si la IA tiene una pieza en la esquina, el estado del tablero puede tener una puntuación de 50, mientras que otro estado del tablero con la pieza de la IA en el medio tiene una puntuación de 10.

Hay muchas formas de hacer esto, y tengo tres heurísticas diferentes para evaluar las piezas del tablero. Te animo a que hagas tu propio tipo de heurística. Subí tres IA diferentes a mi github de tres fabricantes diferentes, con tres heurísticas diferentes: Puma.py, erika5.py, nathanh.py.

Paso 5: Algoritmo Minimax: Elección del mejor movimiento

Ahora sería bueno si la IA pudiera elegir todos los movimientos para llegar al estado del tablero con la puntuación más alta. Pero recuerde que la IA también estaba eligiendo los movimientos para el oponente cuando estaba generando todos los estados del tablero y si el oponente es inteligente, no permitirá que la IA llegue a la puntuación más alta del tablero. En cambio, un oponente inteligente haría el movimiento para hacer que la IA vaya al estado más bajo del tablero. En el algoritmo, llamamos a los dos jugadores un jugador maximizador y un jugador minimizador. La IA sería el jugador maximizador, ya que quiere obtener la mayor cantidad de puntos para sí misma. El oponente sería el jugador minimizador ya que el oponente está tratando de hacer el movimiento donde la IA obtiene la menor cantidad de puntos.

Una vez que se generan todos los estados de la placa y se han asignado valores a las placas, el algoritmo comienza a comparar los estados de la placa. En las imágenes, creé un árbol para representar cómo el algoritmo elegiría sus movimientos. Cada división en las ramas es un movimiento diferente que la IA o el oponente pueden jugar. A la izquierda de las filas de nodos, escribí si el jugador maximizador o minimizador va. La fila inferior son todos los estados del tablero con sus valores. Dentro de cada uno de esos nodos hay un número y esos son los puntajes que asignamos a cada uno de los tableros: cuanto más altos sean, mejor será para la IA.

Definiciones: nodo padre: un nodo que resulta o crea nodos debajo de él; el origen de los nodos secundarios: los nodos que provienen del mismo nodo principal

Los nodos vacíos representan qué movimiento hará la IA para llegar al mejor estado del tablero. Comienza comparando los hijos del nodo más a la izquierda: 10, -3, 5. Dado que el jugador maximizador haría el movimiento, elegiría el movimiento que le daría la mayor cantidad de puntos: 10. Entonces, seleccionamos y almacenamos ese muévase con la puntuación del tablero y escríbalo en el nodo principal. Ahora que 10 está en el nodo principal, ahora es el turno de minimización de jugadores. Sin embargo, el nodo con el que compararíamos 10 está vacío, por lo que tenemos que evaluar ese nodo primero antes de que el jugador minimizador pueda elegir. Así que volvemos al turno del jugador maximizador y comparamos a los hijos del nodo adyacente: 8, -2. Maximizar elegirá 8 y lo escribimos en el nodo padre vacío. Ahora que el algoritmo ha terminado de llenar los espacios vacíos para los hijos de un nodo por encima de él, el jugador minimizador puede comparar esos hijos - 10 y 8 y elegir 8. El algoritmo luego repite este proceso hasta que se completa todo el árbol. Al final de este ejemplo, tenemos el puntaje 8. Ese es el estado de tablero más alto que la IA puede jugar asumiendo que el oponente está jugando de manera óptima. Entonces, la IA elegirá el primer movimiento que lleve al estado de 8 tableros, y si el oponente juega de manera óptima, la IA debería jugar todos los movimientos para llegar al estado de tablero 8. (Siga las notas en mis imágenes)

Sé que fue mucho. Si eres de esos que necesitan que alguien hable contigo para entender algo, aquí hay un par de videos que vi para ayudarme a comprender la idea detrás de esto: 1, 2, 3.

Paso 6: Algoritmo Minimax: Pseudocódigo

Después de comprender la lógica detrás del algoritmo minimax, eche un vistazo a este pseudocódigo (las funciones que son universales para todos los códigos) de wikipedia:

función minimax (nodo, profundidad, maximizingPlayer) es

si la profundidad = 0 o el nodo es un nodo terminal, entonces

devuelve el valor heurístico del nodo

si maximizingPlayer entonces

valor: = −∞

para cada hijo del nodo hacer

valor: = max (valor, minimax (niño, profundidad - 1, FALSO))

valor de retorno

else (* minimizando jugador *)

valor: = + ∞

para cada hijo del nodo hacer

valor: = min (valor, minimax (niño, profundidad - 1, VERDADERO))

valor de retorno

Esta es una función recursiva, lo que significa que se llama a sí misma una y otra vez hasta que llega a un punto de parada. Primero, la función toma tres valores, el nodo, la profundidad y de quién es el turno. El valor del nodo es el lugar donde desea que el programa comience a buscar. La profundidad es la distancia a la que desea que busque el programa. Por ejemplo, en mi ejemplo de árbol tiene una profundidad de 3, porque buscó en todos los estados del tablero después de 3 movimientos. Por supuesto, nos gustaría que la IA verificara cada estado de la placa y elija una victoria ganadora, pero en la mayoría de los juegos donde hay miles, si no millones, de configuraciones de placa, su computadora portátil en casa no podrá procesar todas esas configuraciones. Por lo tanto, limitamos la profundidad de búsqueda de la IA y hacemos que vaya al mejor estado de la placa.

Este pseudocódigo reproduce el proceso que expliqué en los dos pasos anteriores. Ahora demos un paso más y corrijamos esto en código Python.

Paso 7: Crea tu IA con Ai_template.py

Antes de echar un vistazo a mi código de IA de Minimax, intente crear su propia IA con el archivo ai_template.py y el pseudocódigo del que hablamos en el último paso. Hay dos funciones en la plantilla ai llamadas: def minimax_min_node (tablero, color) y def minimax_max_node (tablero, color). En lugar de hacer que la función minimax se llame a sí misma de forma recursiva, tenemos dos funciones diferentes, que se llaman entre sí. Para crear la heurística para evaluar los estados de la placa, deberá crear su propia función. Hay funciones predefinidas en el archivo othello_shared.py que puede usar para construir su IA.

Una vez que tenga su IA, intente ejecutarla contra randy_ai.py. Para ejecutar dos ais uno contra el otro, escriba "python othello_gui.py (inserte el nombre del archivo ai).py (inserte el nombre del archivo).py" en la terminal mac o escriba "run othello_gui.py (inserte el nombre del archivo ai).py (inserte el nombre del archivo).py "y asegúrese de estar en el directorio correcto. Además, mira mi video para conocer los pasos exactos.

Paso 8: ¡Es hora de hacer que la IA luche

¡Ahora consigue un grupo de tus amigos informáticos y haz que diseñen su propia IA! Entonces puedes hacer una competencia y hacer que tu IA se enfrente. Con suerte, incluso si no pudo construir su propia IA, pudo comprender cómo funciona el algoritmo minimax. Si tiene alguna pregunta, no dude en publicar cualquier pregunta en los comentarios a continuación.