+Chess Bot
Una guía paso a paso para construir una IA de ajedrez simple
Por Lauri Hartikka
https://www.freecodecamp.org/news/simple-chess-ai-step-by-step-1d55a9266977
Traduccion Google translator
Exploremos algunos conceptos básicos que nos
ayudarán a crear una IA de ajedrez sencilla:
• Generación de movimientos
• Evaluación de la Junta Directiva
• Minimax
• y poda alfa beta.
En cada paso, mejoraremos nuestro algoritmo con una de estas
técnicas de programación de ajedrez probadas en
el tiempo. Demostraré cómo cada uno afecta el
estilo de juego del algoritmo.
Puedes ver el algoritmo final de IA aquí en GitHub.
Paso 1: Generación de movimientos y
visualización de tableros.
Usaremos la biblioteca chess.js para la
generación de movimientos y chessboard.js para
visualizar el tablero. La biblioteca de
generación de jugadas implementa básicamente
todas las reglas del ajedrez. Basándonos en
esto, podemos calcular todos los movimientos
legales para un estado determinado del tablero.
Una visualización de la función de generación de
movimientos. La posición inicial se utiliza como
entrada y la salida son todos los movimientos
posibles desde esa posición.
El uso de estas librerías nos ayudará a
centrarnos solo en la tarea más interesante:
crear el algoritmo que encuentre la mejor
jugada.
Comenzaremos creando una función que simplemente
devuelva un movimiento aleatorio de todos los
movimientos posibles:
Aunque este algoritmo no es un ajedrecista muy
sólido, es un buen punto de partida, ya que
podemos jugar contra él:
_Black Juega movimientos aleatorios. Se puede
reproducir en
https://jsfiddle.net/lhartikk/m14epfwb/
Paso 2 : Evaluación de la posición
Ahora tratemos de entender qué lado es más
fuerte en una determinada posición. La forma más
sencilla de conseguirlo es contar la fuerza
relativa de las piezas del tablero utilizando la
siguiente tabla:
Con la función de evaluación, podemos crear un
algoritmo que elija el movimiento que da la
evaluación más alta:
La única mejora tangible es que nuestro
algoritmo ahora capturará una pieza si puede.
_Black juega con la ayuda de la sencilla función
de evaluación. Se puede reproducir en
https://jsfiddle.net/lhartikk/m5q6fgtb/1/
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 la
mejor jugada. Esto se hace mediante el algoritmo
Minimax.
En este algoritmo, se explora el árbol recursivo
de todos los movimientos posibles a una
profundidad determinada, 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 el más grande del nodo secundario al nodo
principal, dependiendo de si es blanco o negro
para mover. (Es decir, tratamos de minimizar o
maximizar el resultado en cada nivel).
Una visualización del algoritmo minimax en una
posición artificial. La mejor jugada para las
blancas es b2-c3, porque podemos garantizar que
podemos llegar a una posición en la que la
evaluación sea -50
Con minimax en su lugar, nuestro algoritmo está
comenzando a comprender algunas tácticas básicas
del ajedrez:
_Minimax con nivel de profundidad 2. Se puede
reproducir en:
https://jsfiddle.net/k96eoq0q/1
La efectividad del algoritmo minimax se basa en
gran medida en la profundidad de búsqueda que
podamos 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 descartar
algunas ramas en el árbol de búsqueda. Esto nos
ayuda a evaluar el árbol de búsqueda minimax
mucho más profundo, 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 aquellos caminos que
conducen a buenos movimientos.
Las posiciones no necesitamos explorar si se
utiliza la poda alfa-beta y se visita el árbol
en el orden descrito.
Con alpha-beta, obtenemos un impulso
significativo al algoritmo minimax, como se
muestra en el siguiente ejemplo:
El número de posiciones que se requieren evaluar
si queremos realizar una búsqueda con
profundidad de 4 y la posición "raíz" es la que
se muestra.
Siga este enlace para probar la versión mejorada
alfa-beta 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 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 las
tablas de piezas cuadradas que se describen
originalmente en la wiki de programación de
ajedrez.
Las tablas cuadradas visualizadas.
Podemos disminuir o aumentar la evaluación,
dependiendo de la ubicación de la pieza.
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:
_Improved evaluación y poda alfa-beta con
profundidad de búsqueda de 3.
Se puede reproducir en: https://jsfiddle.net/q76uzxwe/1
Conclusiones
La fuerza de incluso un simple algoritmo de
juego de ajedrez es que no comete errores
estúpidos. Dicho esto, todavía carece de
comprensión estratégica.
Con los métodos que presenté aquí, hemos sido
capaces de programar un algoritmo de juego de
ajedrez que puede jugar al 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 consultar la versión final
en GitHub.
Algunas mejoras adicionales que podríamos hacer
al algoritmo serían, por ejemplo:
• Ordenamiento de movimientos
• Generación de movimientos más rápida
• y la evaluación específica del final del
juego.
Si quieres saber 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 presenté aquí.
¡Gracias por leer!
