Tradujimos para usted un artículo de Lauri Hartikka sobre la creación de la IA más simple para el ajedrez. Fue escrito en 2017, pero los principios básicos siguieron siendo los mismos. Todos los archivos que usó Lori también están disponibles.
La inteligencia artificial simple que puede jugar al ajedrez se puede crear sobre la base de cuatro conceptos:
- 1. mudanza;
- 2. Evaluación de la junta;
- 3. Minimax ;
- 4. Recorte alfa beta . En cada etapa de trabajo con el algoritmo, se utilizará uno de ellos, esto mejorará gradualmente las capacidades de juego de la IA.
Skillbox recomienda: El curso en línea aplicado de Python Data Analyst .
Le recordamos: para todos los lectores de "Habr": un descuento de 10.000 rublos al registrarse en cualquier curso de Skillbox con el código de promoción "Habr".
El código fuente listo para usar se puede encontrar en
GitHub .
Etapa 1. Visualización de un tablero de ajedrez con la generación de movimientos.
En este punto, utilizaremos las bibliotecas
chess.js para generar movimientos y
chessboard.js para representar el tablero de ajedrez. La biblioteca, que es responsable de la generación de movimientos, le permite aplicar todas las reglas de ajedrez, para que podamos calcular cada acción para un arreglo específico de piezas.
Cuando haces clic en la imagen, se abrirá en resolución completa.
Trabajar con estas bibliotecas le permite concentrarse en la tarea principal: buscar y crear un algoritmo que le permita encontrar el movimiento óptimo. Comenzamos el trabajo escribiendo una función que devuelve un movimiento aleatorio de una lista de todos los posibles.
var calculateBestMove =function(game) {
A pesar de que el algoritmo no es un jugador de ajedrez ideal, esto será suficiente para la mayoría de los jugadores de su nivel.
El negro se mueve al azar. (
fuente y juego en línea )
Etapa 2. Evaluación de posición
Ahora descubramos qué lado tiene la ventaja en esta o aquella posición. La forma más fácil es calcular la fuerza relativa de las piezas en el tablero, esto se puede hacer usando la tabla.
Usando la función de evaluación, tenemos la oportunidad de crear un algoritmo que selecciona el movimiento con la calificación máxima.
var calculateBestMove = function (game) { var newGameMoves = game.ugly_moves(); var bestMove = null;
En principio, el nivel es el mismo, pero el algoritmo ya puede tomar la figura de otra persona cuando existe tal oportunidad.
Las negras tuvieron la oportunidad de tomar piezas blancas. (Las fuentes y el juego están
aquí ).
Etapa 3. Árbol de búsqueda con minimax
Después de eso creamos un árbol de búsqueda. Ahora el programa puede elegir el mejor movimiento. Esto se hace usando el algoritmo minimax.
Aquí se analiza un árbol recursivo con la visualización de todos los movimientos posibles a una profundidad dada. La posición es estimada por las hojas de nuestro árbol.
A continuación, devolvemos el valor mínimo o máximo del elemento secundario al nodo primario. Todo depende de qué lado está calculando mal actualmente. En otras palabras, el resultado se maximiza o minimiza en cada nivel.
Aquí, b2-c3 es el mejor movimiento para las blancas, ya que se asegura de que el jugador llegue a la posición con un puntaje de -50.
var minimax = function (depth, game, isMaximisingPlayer) { if (depth === 0) { return -evaluateBoard(game.board()); } var newGameMoves = game.ugly_moves(); if (isMaximisingPlayer) { var bestMove = -9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } else { var bestMove = 9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } };
Con el algoritmo minimax, nuestra IA ya ha comenzado a comprender las tácticas básicas del ajedrez.
Minimax con una profundidad de 2 (Fuentes y el juego
aquí )
Vale la pena señalar que la eficiencia del algoritmo minimax aumenta con la profundidad de la búsqueda. El siguiente paso es responsable de esto.
Etapa 4. Recorte Alfa Beta
Este es un método de optimización del algoritmo minimax que permite ignorar algunas ramas en el árbol de búsqueda. Y esto le permite aumentar la profundidad de búsqueda, gastando la misma cantidad de recursos.
El recorte alfa beta se basa en una situación en la que podemos dejar de evaluar una rama en particular si se descubre que un nuevo movimiento conducirá a una situación peor que la que vimos al evaluar la anterior.
La optimización no afecta el resultado de minimax, pero todo comienza a funcionar más rápido.
Este algoritmo es mucho más eficiente si primero verifica los caminos que conducen a buenos movimientos.
La imagen muestra movimientos que se vuelven innecesarios cuando se utiliza el recorte alfa beta.
Como puede ver, con el recorte alfa-beta, minimax está optimizado y de manera muy significativa.
El número de posiciones que desea evaluar en el caso de una búsqueda con una profundidad de 4 y la posición inicial, que se muestra arriba. (fuente y juego están disponibles
aquí )
Paso 5. Función de evaluación mejorada
La función de evaluación inicial es bastante simple, porque simplemente cuenta los puntos de las piezas en el tablero. Para optimizarlo, puede tener en cuenta la posición de las figuras. Por ejemplo, si coloca el caballo en el centro del tablero, entonces se vuelve más costoso: el rango de movimientos disponibles para esta pieza se expandirá.
En este punto, trabajaremos con una versión ligeramente modificada de las tablas cuadradas descritas originalmente en la
wiki de Programación de ajedrez .
Y ahora nuestro algoritmo ya está jugando bastante bien, por supuesto, en comparación con el jugador promedio.
Las fuentes y el juego están disponibles
aquí.Conclusión
La ventaja del algoritmo propuesto es que no comete errores muy estúpidos. Por supuesto, la estrategia aquí difícilmente se puede llamar perfecta, pero no obstante.
La implementación de nuestro algoritmo es de solo 200 líneas de código, por lo que los principios básicos son bastante simples. La versión final del programa puede ser <a href= target
github.com/lhartikk/simple-chess-ai'> vista en GitHub.
Se pueden agregar otros módulos al algoritmo, que incluyen:
Puede encontrar más información sobre algoritmos de ajedrez en la
Wiki de programación de ajedrez .
Skillbox recomienda: