Original article: A step-by-step guide to building a simple chess AI
Exploremos algunos conceptos básicos que nos ayudarán a crear una IA de ajedrez sencilla:
- move-generation
- board evaluation
- minimax
- and alpha beta pruning.
En cada paso, mejoraremos nuestro algoritmo con una de estas técnicas de programación de ajedrez probadas con el tiempo. Demostraré cómo afecta cada una de ellas al estilo de juego del algoritmo.
Puedes consultar el algoritmo final de IA aquí, en GitHub.
Paso 1: Generación de movimientos y visualización del tablero
Usaremos la librería chess.js para la generación de movimientos, y chessboard.js para visualizar el tablero. La librería de generación de movimientos básicamente implementa todas las reglas del ajedrez. Basándonos en esto, podemos calcular todos los movimientos legales para un estado dado del tablero.
El uso de estas bibliotecas nos ayudará a centrarnos solo en la tarea más interesante: crear el algoritmo que encuentre la mejor jugada.
Empezaremos creando una función que simplemente devuelva una jugada aleatoria de entre todas las posibles:
Aunque este algoritmo no es un jugador de ajedrez muy sólido, es un buen punto de partida, ya que podemos jugar contra él:
Paso 2: Evaluación de la posición
Ahora vamos a intentar comprender qué bando es más fuerte en una posición determinada. La forma más sencilla de conseguirlo es contar la fuerza relativa de las piezas en el tablero utilizando la siguiente tabla:
Con la función de evaluación, somos capaces de crear un algoritmo que elige el movimiento que da la evaluación más alta:
La única mejora tangible es que ahora nuestro algoritmo capturará una pieza si puede.
Paso 3: Árbol de búsqueda utilizando Minimax
A continuación vamos a crear un árbol de búsqueda a partir del cual el algoritmo pueda elegir la mejor jugada. Esto se hace mediante el algoritmo Minimax.
En este algoritmo, el árbol recursivo de todos los movimientos posibles se explora hasta una profundidad determinada, y la posición se evalúa en las "hojas" finales del árbol.
Después de eso, devolvemos el menor o el mayor valor del hijo al nodo padre, dependiendo de si es un blanco o un negro para mover. (Es decir, tratamos de minimizar o maximizar el resultado en cada nivel).
Con minimax en su lugar, nuestro algoritmo está empezando a entender algunas tácticas básicas del ajedrez:
La eficacia del algoritmo minimax se basa en gran medida en la profundidad de búsqueda que podamos alcanzar. Esto es algo que mejoraremos en el siguiente paso.
Paso 4: Poda alfa-beta
La poda alfa-beta es un método de optimización del algoritmo minimax que nos permite descartar algunas ramas del árbol de búsqueda. Esto nos ayuda a evaluar el árbol de búsqueda minimax mucho más profundamente, utilizando los mismos recursos.
La poda alfa-beta se basa en la situación en la que podemos dejar de evaluar una parte del árbol de búsqueda si encontramos un movimiento que conduce a una situación peor que un movimiento descubierto anteriormente.
La poda alfa-beta no influye en el resultado del algoritmo minimax, sólo lo hace más rápido.
El algoritmo alfa-beta también es más eficiente si visitamos primero los caminos que conducen a buenas jugadas.
Con alfa-beta, obtenemos una mejora significativa del algoritmo minimax, como se muestra en el siguiente ejemplo:
Sigue este enlace para probar la versión alfa-beta mejorada de la IA de ajedrez.
Paso 5: Mejora de la función de evaluación
La función de evaluación inicial es bastante ingenua, ya que sólo contamos el material que se encuentra en el tablero. Para mejorarla, añadimos a la evaluación un factor que tiene en cuenta la posición de las piezas. Por ejemplo, un caballo en el centro del tablero es mejor (porque tiene más opciones y, por tanto, es más activo) que un caballo en el borde del tablero.
Utilizaremos una versión ligeramente ajustada de las tablas pieza-cuadrado que se describen originalmente en chess-programming-wiki.
Con la siguiente mejora, empezamos a conseguir un algoritmo que juega algo de ajedrez "decente", al menos desde el punto de vista de un jugador ocasional:
Conclusiones
El punto fuerte de un algoritmo de ajedrez sencillo es que no comete errores estúpidos. Dicho esto, le sigue faltando comprensión estratégica.
Con los métodos que he introducido aquí, hemos sido capaces de programar un algoritmo de juego de ajedrez que puede jugar al ajedrez básico. La "parte IA" (excluyendo la generación de jugadas) del algoritmo final tiene sólo 200 líneas de código, lo que significa que los conceptos básicos son bastante sencillos de implementar. Puede consultar la versión final en GitHub.
Otras mejoras que podríamos introducir en el algoritmo serían, por ejemplo:
- move-ordering
- generación de movimientos más rápidos
- y la evaluación específica de los objetivos finales.
Si quieres aprender más, echa un vistazo a la wiki de programación de ajedrez. Es un recurso útil para explorar más allá de estos conceptos básicos que he introducido aquí.
Gracias por leerme.