Desarrollo de Técnicas de Inteligencia Artificial para Jugar Ajedrez por Computadora



Desarrollo de Técnicas de Inteligencia Artificial para Jugar Ajedrez por Computadora

Eduardo Vázquez Fernández
 

Texto completo de la Tesis     

 



Resumen

 

Básicamente, un motor de ajedrez está compuesto de tres partes: un generador de movimientos, un algoritmo de búsqueda de la variante principal y una función de evaluación. En este trabajo diseñamos e implementamos un motor de ajedrez agregando conocimiento a la función de evaluación a través de técnicas de inteligencia artificial como lo son los algoritmos evolutivos y/o las redes neuronales. La investigación versa sobre tres contribuciones principales. En la primera, proponemos una arquitectura de redes neuronales para obtener los valores posicionales de las piezas de ajedrez. Con esta propuesta, nuestro motor de ajedrez alcanzó una calificación de 2178 puntos en el sistema de medida empleado por la Federación Internacional de Ajedrez. En la segunda contribución, proponemos un algoritmo evolutivo con un mecanismo de selección basado en juegos de grandes maestros para ajustar el conjunto básico de pesos del motor de ajedrez. Finalmente, en la tercera contribución, usamos dos pasos para llevar a cabo el ajuste de pesos. En el primero, realizamos la búsqueda de exploración a través del algoritmo evolutivo previo, pero tomando en cuenta un mayor número de pesos (de cinco a veintiocho). Con este cambio obtuvimos un incremento en la calificación de nuestro motor de ajedrez de 1463 a 2205 puntos. En el segundo paso, usamos el método de Hooke-Jeeves para continuar ajustando los pesos del mejor jugador virtual obtenido en el paso anterior. Usando este algoritmo como un buscador local, logramos incrementar la calificación de 2205 a 2425 puntos.

 

Abstract

Basically, a chess engine is composed of a move generator, a search algorithm of the principal variation and an evaluation function. In this work, we designed and implemented a chess engine by adding knowledge to the evaluation function through artificial intelligence techniques. The research had three main contributions. In the first, we proposed a neural network architecture to obtain the positional values of chess pieces in a way analogous to human chess players. With this proposal, our chess engine reached a rating of 2178 points. In the second contribution, we report an evolutionary algorithm which has a selection mechanism that favors virtual players that are able to “visualize” (or match) more moves from those registered in a database of chess grandmaster games. This information is used to adjust the basic weights set of the evaluation function of the chess engine. This proposal does not attempt to increase level of play in our chess engine, but instead aims to deduce the known values from chess theory for this basic weights set. Finally, in the third contribution of this work, we used two steps to carry out the weights adjustment of our chess engine. In the first step, we performed an exploration search through the previous evolutionary algorithm, but now we adjust a larger number of weights (from five to twenty eight).With this change, we obtained an increase in the rating of the chess engine from 1463 to 2205 points. In the second step, we used the Hooke-Jeeves algorithm to continue the weights adjustment for the best virtual player obtained in the previous step. Using this algorithm as a local search engine, we increased the rating of our chess engine from 2205 to 2425 points.