por Lauri Hartikka
Exploremos algunos conceptos básicos que nos ayudarán a crear una IA de ajedrez simple:
- generación de movimientos
- evaluación del tablero
- minimax
- y poda alfa beta.
En cada paso, mejoraremos nuestro algoritmo con una de estas técnicas de programación de ajedrez probadas por el tiempo. Demostraré cómo afecta cada uno al estilo de juego del algoritmo.
Puedes ver el algoritmo de IA final aquí en GitHub.
Paso 1: Generación de movimientos y visualización del tablero
Usaremos el ajedrez.biblioteca js para generación de movimientos y tablero de ajedrez.js para visualizar el tablero. La biblioteca 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 de junta dado.
El uso de estas bibliotecas nos ayudará a centrarnos solo en la tarea más interesante: crear el algoritmo que encuentre el mejor movimiento.
Comenzaremos creando una función que solo devuelve un movimiento aleatorio de todos los movimientos posibles:
Aunque este algoritmo no es un jugador de ajedrez muy sólido, es un buen punto de partida, ya que en realidad podemos jugar contra él:
Paso 2 : Evaluación de posición
Ahora intentemos entender qué lado es más fuerte en una posición determinada. La forma más sencilla de lograr esto es contar la fuerza relativa de las piezas en el tablero utilizando la siguiente tabla:
Con la función de evaluación, podemos crear un algoritmo que elige el movimiento que da la evaluación más alta:
La única mejora tangible es que nuestro algoritmo ahora capturará una pieza si puede.
Paso 3: Árbol de búsqueda usando Minimax
A continuación vamos a crear un árbol de búsqueda del que el algoritmo puede elegir el mejor movimiento. Esto se hace utilizando el algoritmo Minimax.
En este algoritmo, el árbol recursivo de todos los movimientos posibles se explora a una profundidad dada, y la posición se evalúa en las «hojas» finales del árbol.
Después de eso, devolvemos el valor más pequeño o más grande del hijo al nodo padre, dependiendo de si se trata de un nodo blanco o 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 comprender algunas tácticas básicas del ajedrez:
La efectividad del algoritmo minimax se basa en gran medida en la profundidad de búsqueda que podemos lograr. 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 ignorar algunas ramas en el árbol de búsqueda. Esto nos ayuda a evaluar el árbol de búsqueda minimax mucho más a fondo, mientras usamos 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, solo lo hace más rápido.
El algoritmo alfa-beta también es más eficiente si visitamos primero los caminos que conducen a buenos movimientos.
Con alfa-beta, obtenemos un impulso significativo al algoritmo minimax, como se muestra en el siguiente ejemplo:
Siga este enlace para probar la versión mejorada alfa-beta de la IA de ajedrez.
Paso 5: Función de evaluación mejorada
La función de evaluación inicial es bastante ingenua, ya que solo contamos el material que se encuentra en el tablero. Para mejorar esto, 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 lo tanto, es más activo) que un caballo en el borde del tablero.
Usaremos una versión ligeramente ajustada de tablas cuadradas de piezas que se describen originalmente en el wiki de programación de ajedrez.
Con la siguiente mejora, comenzamos a obtener un algoritmo que juega un ajedrez «decente», al menos desde el punto de vista de un jugador casual:
Conclusiones
La fuerza de una simple jugando al ajedrez-algoritmo es que no cometer errores estúpidos. Dicho esto, todavía le falta entendimiento estratégico.
Con los métodos que he introducido aquí, hemos sido capaces de programar un algoritmo de juego de ajedrez que puede jugar ajedrez básico. La «parte de IA» (excluida la generación de movimientos) del algoritmo final es de solo 200 líneas de código, lo que significa que los conceptos básicos son bastante simples de implementar. Puedes ver la versión final en GitHub.
Algunas mejoras adicionales que podríamos hacer al algoritmo serían, por ejemplo:
- orden de movimientos
- generación de movimientos más rápida
- y evaluación específica al final del juego.
