Cómo crear una IA que juega ajedrez (Algoritmo minimax + Poda alfa-beta)

Contenido

• Introducción
• Componentes de nuestro enfoque
• ¿Qué es una heurística?
• Función de evaluación de heurística
• El algoritmo minimax
• Mejoras con poda alfa-beta
• ¡A programar!
• Conclusión

Introducción

¡Hola a todos y bienvenidos al primer taller del trimestre! En este video, les mostraré cómo crear una inteligencia artificial (IA) que pueda jugar al ajedrez. Empecemos con una breve descripción general de lo que vamos a hacer.

Componentes de nuestro enfoque

Hay varias formas diferentes de hacer que una IA juegue al ajedrez, pero aquí destacaré dos componentes que necesitaremos para nuestra implementación particular.

¿Qué es una heurística?

Antes de profundizar en cómo funcionará nuestra IA, es importante entender qué es una heurística. Una heurística es una métrica que no garantiza resultados perfectos, pero que proporciona una aproximación útil. Un ejemplo de una heurística es el promedio de calificaciones (GPA). Cuando una universidad solicita tu GPA, realmente quieren saber si eres un buen estudiante. Como las universidades no tienen tiempo ni recursos para investigarte a fondo, confían en la aproximación imperfecta pero útil que es tu GPA. Volviendo al ajedrez, en lugar de aproximar qué tan buen estudiante es una persona para una universidad, queremos aproximar qué tan buena es una configuración de juego para un jugador dado.

Función de evaluación de heurística

Una posibilidad es usar una puntuación de material. En este caso, cada pieza tiene un peso y, para calcular la puntuación de material de un jugador, consideramos todas sus piezas en el tablero y sumamos sus pesos. Por ejemplo, dado el tablero en la parte inferior derecha, la puntuación para las blancas es de 950, ya que hay un rey que vale 900 y una torre que vale 50. La puntuación para las negras es de 1020, ya que hay un rey que vale 900, una reina que vale 90 y un caballo que vale 30. Ahora que tenemos nuestra heurística, escribamos la función de evaluación de heurística.

El algoritmo minimax

Descubramos cómo funciona el algoritmo minimax y luego escribamos el código necesario. El algoritmo minimax es un proceso que selecciona el movimiento que conduce al mejor estado de juego, después de considerar posibles movimientos futuros. Cubriremos exactamente cómo funciona este algoritmo pronto, pero primero asegurémonos de entender la función de evaluación de la heurística.

Mejoras con poda alfa-beta

Ahora es el momento de hablar sobre las mejoras de nuestra IA. El algoritmo minimax tal como está funciona técnicamente, pero puede mejorarse utilizando la poda alfa-beta. La poda alfa-beta mejora enormemente el rendimiento del algoritmo minimax al evitar explorar ramas innecesarias del árbol. Hay un excelente video sobre la poda alfa-beta de Sebastian Lague que enlazaré en la descripción, por si desean agregarla a su código.

¡A programar!

Voy a pasar rápidamente por el código, así que siéntanse libres de pausar el video para asegurarse de entenderlo todo. Aquí verificamos si se ha alcanzado el límite de profundidad (depth limit) o si el juego ha terminado. Si se cumple alguna de estas condiciones, evaluamos todos los estados del juego en el nivel más bajo para poder empezar a pasar los valores hacia arriba en el árbol. Luego obtenemos todos los movimientos disponibles en el tablero y inicializamos el mejor movimiento con un valor aleatorio. Si somos el jugador maximizador, después de cada movimiento evaluamos el estado del juego resultante y comprobamos si el valor es mayor que cualquiera de los que hemos visto anteriormente. Si es mayor, actualizamos las variables de evaluación máxima (max eval) y mejor movimiento (best move) en consecuencia. Por último, devolvemos la evaluación máxima junto con el mejor movimiento. Este segmento de código es básicamente idéntico al anterior, pero en este caso encontramos el valor mínimo en lugar del máximo.

Conclusión

¡Y eso es todo para este taller! Si has codificado todo correctamente, cuando ejecutes el programa podrás jugar contra la IA. Espero que hayan encontrado esto útil y sé que puede ser difícil entender todo esto de inmediato, así que no duden en enviarme un mensaje en Discord si tienen alguna pregunta. Podemos unirnos a un canal de voz y los guiaré en las partes con las que tengan dificultades. De todos modos, gracias por ver y espero verlos en el próximo video. ¡Cuídense!