Fundamentos de IA para el ajedrez

Abstract

El presente trabajo tiene como objetivo la introducción y desarrollo de los fundamentos teóricos de algunas técnicas clásicas y actuales de la IA aplicadas a la generación de jugadores automáticos de Ajedrez. Se aborda en el primer capítulo el desarrollo histórico de esta disciplina, abarcando desde los primeros jugadores automáticos de Turing y Shannon hasta los actuales Stockfish y AlphaZero, pasando por el creciente desarrollo de mejora del rendimiento de los jugadores automáticos hasta alcanzar la victoria frente al campeón del mundo humano de ajedrez, como fue el caso de IBM Deep Blue. Mostraremos también los problemas asociados al objetivo de poder evaluar de manera correcta una posición para obtener la mejor jugada posible, y daremos una primera aproximación de las soluciones parciales encontradas. En el segundo capítulo, desarrollamos los conceptos básicos sobre juegos finitos que son base para todo el trabajo realizado en los capítulos 3 y 4. Además, describimos las hipótesis sobre los juegos que vamos a considerar y damos un resultado sobre la determinación de los mismos. Situados en el contexto en que se ha desarrollado toda una línea de trabajo en busca de algoritmos cada vez más eficaces, hemos decidido enfocar este trabajo en el estudio de algunos de los más importantes: el algoritmo Minimax con poda α-β en el capítulo 3, y el Árbol de Búsqueda Monte Carlo en el capítulo 4. Ambos capítulos tratan de manera general los algoritmos y desarrollan los conceptos que fundamentan el buen rendimiento de los mismos. Se realiza, además, un análisis de sus virtudes y debilidades. En el capítulo 3 se trata con profundidad la técnica de reducción del número de jugadas que analizar, mientras que el capítulo 4 contrasta con el anterior en la filosofía de búsqueda y evaluación de las distintas jugadas posibles. Tras los resultados aportados en estos dos capítulos, el capítulo 5 particulariza todos los conceptos anteriores al juego del Ajedrez. Damos ejemplos prácticos donde mostramos las virtudes y debilidades de los distintos algoritmos, así como la forma en la que los algoritmos evalúan las posiciones y realizan las búsquedas de jugadas. La particularización al ajedrez realizada en el capítulo 5 nos da paso de manera natural a la implementación de los algoritmos estudiados en los capítulos 3 y 4. La implementación es realizada en el lenguaje Python si bien es posible desarrollarla en muchos otros lenguajes de programación. Por último, realizamos un análisis global del trabajo realizado y estudiamos una posible línea de trabajo futuro que continuaría de manera natural hacia las técnicas recientes de Deep Learning y el trabajo actual en jugadores automáticos de ajedrez.

The present work has a clear goal: the introduction and development of the theoretical basis and some of the classical and modern techniques in AI applied to the generation of computer chess players. We start with an historical development of this discipline from Turing and Shannon’s first computer chess players to recent computer chess players such as Stockfish or AlphaZero with a mandatory stop on IBM Deep Blue, the first computer chess player that won a match against the World Chess Champion Garry Kasparov. Problems like accurate evaluation are shown and we give a glimpse of some partial solutions. During the second chapter, we present basic concepts about finite games. This is a basic chapter that is necessary to understand all the work done in chapters 3 and 4. Besides, we describe hypothesis about the games we are dealing with and we prove a result of determination. After that, we have decided to focus on two algorithms: minimax with α-β pruning (chapter 3) and Monte Carlo Tree Search (chapter 4). Both chapters describe the algorithms and their performance. We also compare strenghts and weaknesses between them. After these two central chapters, we apply all the general concepts we already know to the game of chess. We present practical examples where we show strengths and weaknesess and, also, we give some clues to understand how these algorithms search for the best possible move. This application takes us to the next natural step: the implementation of the two algorithms studied. The implementation is done using Python software but may be done in plenty of different programming languages. To conclude, we sum up all the work done with a global analysis and we study a possible line of future work using Machine Learning techniques applied to computer chess players.