Tutorial IA Damas Python Parte 2 - Implementación (Minimax)
Contenido
- Introducción
- Preparación del código
- Implementación del algoritmo MiniMax
- Evaluación de las posiciones
- Obtención de los posibles movimientos
- Dibujo de los movimientos considerados
- Ejecución del programa
- Conclusiones
Artículo
Introducción
¡Hola a todos! Bienvenidos a la segunda parte del Tutorial de IA de las damas. En este video, vamos a implementar el algoritmo MiniMax. Pero primero, asegurémonos de que todos tengan el código configurado. Por favor, vayan a la descripción y descarguen todo el código. Como ejemplo, les mostraré rápidamente cómo funciona todo esto, pero si quieren ver cómo construir todo este código desde cero, ya realicé una serie anterior en la que lo explico detalladamente. Por supuesto, si están interesados únicamente en la IA, solo descarguen el código y seguiremos desde allí. Ahora bien, cuando descarguen el código, verán que hay un archivo principal main.py
, una carpeta llamada checkers
y una carpeta llamada assets
. El archivo main.py
es donde se juega el juego en términos de la interfaz de usuario. Aquí podemos seleccionar ciertas piezas y moverlas, entre otras cosas. Ahora, vamos a modificar algunas partes del código. Primero, les explicaré cómo funciona main.py
. Es bastante sencillo. Aquí hay un bucle principal del juego que verifica si alguien ha ganado. Si es así, imprime quién es el ganador y finaliza el juego. Lo primero que vamos a hacer aquí es establecer run
en False
, lo que significa que vamos a salir del juego. Esta es la primera edición que podemos hacer en la línea 27. Si alguien ha ganado el juego, vamos a salir. Lo siguiente que vemos aquí es Game.select
, game.update
y game.draw
. Estas son clases que representan el estado del juego y la lógica del juego. A través de estas clases, podemos seleccionar piezas, moverlas, etc. ¡Eso es todo! Esto es básicamente cómo se juegan las damas. Ahora vamos a modificar algunas partes de este código.
Preparación del código
La primera modificación que vamos a hacer es agregar un método evaluate
en la clase Board
en el archivo board.py
. Básicamente, este método nos dará una puntuación para el estado actual del tablero. Vamos a hacerlo de una manera muy simple. Simplemente restaremos la cantidad de piezas rojas a la cantidad de piezas blancas. De esta manera, si hay más piezas blancas, la puntuación será positiva, y si hay más piezas rojas, la puntuación será negativa. Sin embargo, también queremos incentivar a nuestra IA a convertirse en una Dama. Esto significa que si hay más Dama rojas y blancas, también queremos tenerlo en cuenta en la puntuación final. Entonces, vamos a agregar esto al método evaluate
:
def evaluate(self):
score = self.white_left - self.red_left
score += 0.5 * self.white_kings - 0.5 * self.red_kings
return score
Básicamente, estamos sumando la mitad de la cantidad de Dama blanca y restándole la mitad de la cantidad de Dama roja. Esto hará que nuestra IA tenga más incentivos para convertirse en una Dama y, en general, mejorará su rendimiento.
Luego, vamos a modificar el archivo algorithm.py
. Aquí es donde vamos a implementar el algoritmo MiniMax. Pero primero, vamos a importar todas las dependencias necesarias y establecer las constantes de color que vamos a utilizar.
from copy import deepcopy
import pygame as pg
# Constantes de color
ROJO = (255, 0, 0)
BLANCO = (255, 255, 255)
Implementación del algoritmo MiniMax
Ahora, vamos a implementar la función mini_max
. Esta será nuestra función principal que utilizará el algoritmo MiniMax para determinar el mejor movimiento a realizar. Aquí está la estructura básica de la función:
def mini_max(position, depth, max_player, game):
if depth == 0 or position.winner() is not None:
return position.evaluate(), position
if max_player:
max_evaluation = float('-inf')
best_move = None
for move in get_all_moves(position, WHITE, game):
evaluation = mini_max(move, depth - 1, False, game)[0]
max_evaluation = max(max_evaluation, evaluation)
if max_evaluation == evaluation:
best_move = move
return max_evaluation, best_move
else:
min_evaluation = float('inf')
best_move = None
for move in get_all_moves(position, RED, game):
evaluation = mini_max(move, depth - 1, True, game)[0]
min_evaluation = min(min_evaluation, evaluation)
if min_evaluation == evaluation:
best_move = move
return min_evaluation, best_move
Vamos a desglosar cómo funciona esto. Primero, verificamos si hemos alcanzado la profundidad deseada o si alguien ha ganado el juego. Si es así, devolvemos la evaluación de esa posición. Luego, verificamos si estamos maximizando o minimizando el valor. Si estamos maximizando, iteramos a través de todos los movimientos posibles y llamamos a mini_max
recursivamente con el movimiento y disminuyendo la profundidad en 1. Almacenamos el valor máximo y el mejor movimiento.
Si estamos minimizando, hacemos lo mismo pero buscamos el valor mínimo. Finalmente, devolvemos la mejor evaluación y el mejor movimiento.
Evaluación de las posiciones
Vamos a implementar el método evaluate
en la clase Board
del archivo board.py
. Este método evaluará una posición y devolverá su puntuación. Primero, vamos a importar las constantes de color.
from constantes import ROJO, BLANCO