Motor de Juego de Ajedrez Alessandro v1.0 Chess Engine Alessandro v1.0

Rubiel Alejandro González Labarta 1*, Martha Acosta Alvarez 2

1

Universidad de las Ciencias informáticas, Cuba, km 5 ½ carretera San Antonio de los Baños, Rpto. Torrens, Boyero, Habana (email: [email protected] ) 2 Universidad de las Ciencias informáticas, Cuba, km 5 ½ carretera San Antonio de los Baños, Rpto. Torrens, Boyero, Habana (email: [email protected] ) *

Autor para correspondencia: [email protected]

Resumen En las últimas décadas el análisis ajedrecístico ha encontrado un complemento imprescindible en el uso de la computación como soporte para la realización de tareas cada vez más arduas y complejas, y ampliando los horizontes del juego más allá de la intuición y del razonamiento humano. En este contexto los motores de juego de ajedrez ocupan un lugar privilegiado en el proceso de enseñanza aprendizaje, en el ciclo de entrenamiento deportivo, o el simple entretenimiento. Por otra parte, desde el comienzo del nuevo siglo, con la revolución tecnológica experimentada por la sociedad a nivel global, ha habido un auge en la creación de motores de ajedrez, que ha derivado en el surgimiento de abundantes torneos para medir fuerzas entre jugadores virtuales, haciéndose casi tan populares como los que enfrentan a jugadores en vivo, a la vieja usanza. A pesar de ser Cuba una potencia ajedrecística, carecía de esta clase de software que representara el potencial de los trebejos antillanos a nivel internacional. Por tal motivo el grupo de desarrollo de soluciones informáticas Proteus GDI se planteó la creación de un motor de juego de ajedrez robusto, adaptable y multiplataforma, obteniendo como resultado la primera versión de Alessandro, que ha superado las expectativas, convirtiéndose en uno de los motores de ajedrez más sólidos de Latinoamérica. Alessandro v1.0 es el primer motor desarrollado en Cuba y representa un hito en la integración de experiencia deportiva de alto nivel con la aplicación de resultados científicos en campos como la inteligencia artificial. Palabras clave: motor de juego de ajedrez 1, matemática aplicada 2, inteligencia artificial 3, Alessandro v1.0 4, ajedrez por computadora 5

1

Abstract On last decades the chess analysis has found an indispensable complement in the use of the computers like support for the realization of tasks each time more arduous and complex, and enlarging the horizons of the game beyond intuition and of the human reasoning. In this context chess engines conquer a prime site in the process of teaching learning, in the cycle of sports training, or the simple entertainment. On the other hand, from the beginning of the new century, with the technological revolution of our society to global level, there has been a prosperity in the creation of chess engines, that he has drifted in the surging of abundant tournaments to measure forces between virtual players, becoming almost as popular like the ones that confront real players, to the old usage. In spite of being Cuba a chess potency, lacked this kind of software that represents the international potential of chess in our country. For such motive the group of development of information-technology solutions Proteus GDI proposed the creation of a robust chess engine, adaptable and multi-platform, getting as a result Alessandro's first version, which it has turned up trumps, becoming more solid one of chess engines in Latin America. Alessandro v1.0 is the first engine developed in Cuba and represents a milestone in the integration of sports high-level experience with the application of scientific results in fields like artificial intelligence. Keywords: chess engine 1, applied mathematics 2, artificial intelligence 3, Alessandro v1.0 4, computers chess 5

Introducción Un motor de ajedrez es un programa que sabe jugar ajedrez y que implementa un lenguaje de comunicación que le permite hablar con otros programas. El principal objetivo de esta investigación consiste en la creación de un motor de ajedrez de elevado nivel de juego, aplicable a diferentes ramas como la educación, el entrenamiento deportivo de carácter profesional o la simple diversión y que sea capaz de lograr una adecuada integración tanto con las plataformas visuales existentes como con los sistemas operativos más populares en la actualidad. Se expondrán una serie de temáticas introductorias al tema, además de una breve panorámica acerca del panorama internacional en cuanto a motores de ajedrez se refiere. Posteriormente se hace exposición de las herramientas, métodos, medios, técnicas, algoritmos y otros usados durante el proceso investigativo y de creación del chess engine en cuestión, y finalmente se muestras los resultados a nivel de software y durante el proceso de validación de la aplicación. En el siglo XVIII empezó a difundirse la idea de crear una computadora capaz de jugar al ajedrez. En el año 1769, un jugador de ajedrez autómata llamado El Turco se hizo famoso antes de que se descubriera que era un engaño. El español Leonardo Torres y Quevedo construyó, en 1912, un autómata capaz de jugar al ajedrez, llamado El Ajedrecista. Después de aquellos sucesos, el tema del ajedrez mecánico no se volvió a mencionar y cayó en el olvido, hasta la aparición de la computadora en la década de los 50. Desde entonces, los aficionados del ajedrez y de la ingeniería informática han construido máquinas y programas que juegan al ajedrez.

2

Actualmente, las computadoras de ajedrez están disponibles a precios accesibles, y existen numerosos programas que pueden jugar al ajedrez en cualquier ordenador personal y derrotar a jugadores profesionales bajo condiciones de torneo, mientras que algunos de entre los mejores programas comerciales de ajedrez, como Shredder, Fritz, Rybka o Fruit, han vencido a muchos jugadores de calibre y varios campeones del mundo en tiempos de control muy cortos y partidas relámpago. Existen varias causas que motivaron la existencia del ajedrez computarizado, como el entretenimiento propio (pudiendo permitir que los jugadores practiquen y se diviertan cuando no hay ningún oponente disponible), también como herramienta o soporte de análisis, para competiciones entre computadoras de ajedrez, y como investigación o abastecimiento del conocimiento humano. Sin embargo, y a pesar de la sorpresa de muchos, el ajedrez nos ha enseñado muy poco en lo referente a la construcción de máquinas que proporcionen inteligencia humana, o hacer cualquier otra cosa que no sea jugar prodigiosamente al ajedrez. El funcionamiento de los programas de ajedrez consiste, esencialmente, en explorar un número muy elevado de posibles futuros movimientos y aplicarles una función de evaluación al resultado, e idear nuevos enfoques y estrategias de juego. Las tácticas basadas en la fuerza bruta son prácticamente inútiles para la mayoría de problemas que han afrontado los investigadores de la inteligencia artificial (IA). El estilo de juego de un programa de ajedrez se diferencia en gran medida del estilo de juego humano, ya que la elección del movimiento a jugar es totalmente distinta. En algunos juegos de estrategia, las computadoras suelen vencer fácilmente la gran mayoría de partidas, mientras que en otros, los principiantes vencen a las máquinas sin mayor esfuerzo. En el ajedrez, el resultado de la fusión de las habilidades de los expertos, con los programas de ajedrez, es mayor que el de cualquiera de los dos a solas.

Materiales y métodos o Metodología computacional Alessandro v1.0 fue creado usando la metodología de desarrollo de software SCRUM, y está en el lenguaje de programación C++, usando la plataforma Qt Creator como Entorno de Desarrollo Integrado (IDE) y el Qt Framework como soporte a las diversas tecnologías integradas en la aplicación. SCRUM: es un marco de trabajo para la gestión y desarrollo de software basada en un proceso iterativo e incremental utilizado comúnmente en entornos basados en el desarrollo ágil de software. Qt Framework: es una biblioteca multiplataforma ampliamente usada para desarrollar aplicaciones con una interfaz gráfica de usuario así como también para el desarrollo de programas sin interfaz gráfica como herramientas para la línea de comandos y consolas para servidores. Utiliza el lenguaje de programación C++ de forma nativa, y funciona con independencia del sistema operativo sobre el que esté ejecutándose el código, y tiene un amplio soporte. Qt Creator: es un IDE creado por Trolltech para el desarrollo de aplicaciones con las bibliotecas Qt Framework, requiriendo su versión 4.x. Los sistemas operativos que soporta en forma oficial son:

3

 GNU/Linux 2.6.x, para versiones de 32 y 64 bits con Qt 4.x instalado.  Mac OS X 10.4 o superior, requiriendo Qt 4.x  Windows XP y superiores, requiriendo el compilador MinGW y Qt 4.4.3 para MinGW.

Arquitectura El primer artículo sobre el tema fue escrito por Claude Shannon1, y publicado en 1950, antes de la existencia de una computadora que jugara al ajedrez, y predijo acertadamente las dos posibles principales formas de búsqueda de cualquier programa, a las que nombró de 'Tipo A', y de 'Tipo B'. Los programas 'Tipo A', más rudimentarios, utilizarían una búsqueda basada en la "fuerza bruta", los cuales examinarían todas posibles posiciones de cada rama del árbol de movimientos usando el algoritmo minimax. Shannon creyó que esto sería muy poco práctico por dos razones: 

Primero, con aproximadamente 30 movimientos posibles en una posición típica de medio juego, Shannon predijo que buscando las 302 (más de 700.000.000) posiciones contenidas en los primeros tres movimientos (de ambos bandos, lo que son 6 plies), tardaría aproximadamente 16 minutos, incluso en el caso "muy optimista" que el programa evaluara un millón de posiciones por segundo. Después de esta conjetura, se tardó alrededor de 40 años para conseguir esa velocidad.



Segundo, se ignoraba el problema de la latencia, ya que el programa trata de evaluar la posición resultante después de todo el intercambio de piezas ocurrido durante todos esos movimientos al final de cada rama del árbol. Los programas de 'Tipo A' funcionan así, pero el inconveniente es que se incrementa enormemente el número de posiciones necesarias para el análisis, y de este modo el programa se ralentizaba todavía más.

En vez de este gastar la potencia de proceso examinando movimientos malos o triviales, Shannon sugirió que a los programas tipo B utilizarían una especie de "inteligencia artificial estratégica" para solucionar estos problemas en los que únicamente se analizarían solo las mejores jugadas de cada posición, algo parecido a lo que hacen los jugadores humanos. Esto permitiría al programa analizar las líneas significantes de manera más profunda en un tiempo razonable. Adriaan de Groot entrevistó a varios jugadores de ajedrez de varios niveles y su conclusión fue que tanto los grandes maestros como los principiantes calculan aproximadamente cuarenta o cincuenta posiciones antes de decidir que jugada mover. Lo que realmente diferencia a jugadores expertos de jugadores mediocres es la habilidad del reconocimiento de patrones, que se va adquiriendo con la experiencia. Esto permite analizar más profundamente las mejores líneas y no perder el tiempo con otras peores. Una prueba de ello es que los jugadores de ajedrez recuerdan muchas de las posiciones jugadas en anteriores partidas y aprenden de la experiencia, sin embargo, las computadoras no lo tienen tan fácil.

4

El problema de los programas 'Tipo B' es que se confía demasiado en que el programa puede decidir qué movimientos son suficientemente buenos para ser dignos de consideración en cualquier posición, siendo un problema mucho más grave que en programas 'Tipo A' con un hardware de gran velocidad. En 1973, la Universidad de Northwestern, encargada de la creación de programas de Tipo B, dejó de programarlos, pasando al bando de los programas de Tipo A. Fue la creadora de una varios de programas de ajedrez que ganaron los primeros tres torneos ACM Computer Chess Championships (1970-1972). El programa de Tipo A resultante fue "Chess 4.0", ganador del torneo ACM durante 5 años seguidos, además de inaugurar uno de los campeonatos más importantes, el World Computer Chess Championship (WCCC). Una de las razones por las que realizaron el cambio fue porque encontraban a los programas de Tipo B poco estimulantes durante los torneos, ya que es muy difícil predecir lo que van a mover, y mucho menos el por qué. Otra razón fue que en los programas de Tipo A era mucho más fácil detectar los fallos del programa y depurarlos, y lograron hacer de él un programa lo suficientemente rápido: en el tiempo que solían tomar para decidir los movimientos que eran dignos de ser buscados, era posible únicamente buscar todos ellos. De hecho, Chess 4.0 estableció un paradigma que era y continúa utilizándose en todos los programas de ajedrez actuales. Los programas tipo Chess 4.0 ganaban por la simple razón que sus programas simplemente jugaban un mejor ajedrez. Tales programas no intentaban imitar los procesos de pensamiento humanos, pero confiaban completamente en búsquedas alfa-beta y Negascout. Muchos de tales programas (incluyendo todos los programas actuales) también incluyen una parte selectiva bastante limitada de la búsqueda basada en búsquedas latentes y normalmente extensiones y podado (particularmente podado de movimientos nulos desde los años 1990) que eran lanzadas basadas en ciertas condiciones en un intento de eliminar o reducir los movimientos malos obvios (históricos de movimientos) o investigar nodos interesantes (p.ej. comprobación de extensiones, peones pasados en la séptima fila, etc). Sin embargo, los lanzamientos de extensión y poda tienen que utilizarse con mucho cuidado. Si se sobrextiende el programa gastan demasiado tiempo analizando posiciones sin interés. Si se poda demasiado, hay riesgos de cortar nodos interesantes. Los programas de ajedrez difieren en términos de cómo y qué tipos de reglas de poda y extensión se utilizan así como de la función de evaluación. Se cree que algunos programas son más selectivos que otros (por ejemplo Deep Blue se sabe que es menos selectivo que muchos programas comerciales porque podía permitirse hacer más búsquedas completas), pero todos tienen una base de búsquedas como fundamento y todos tienen componente selectivos (búsqueda-Q, poda/extensiones). Aunque tales adiciones significa que el programa realmente no examinaría cada nodo dentro de la profundidad de búsqueda (de tal manera que no sería realmente fuerza bruta en ese sentido), los extraños errores debidos a estas búsquedas selectivas se encuentra que consumen en tiempo extra que es ahorrado debido a que se podría aumentar la profundidad. De esa manera los programas de ajedrez pueden obtener lo mejor de ambos mundos. Además, el desarrollo y los avances tecnológicos hicieron que el sistema de fuerza bruta continuara en alza y se intensificara mucho más en los años 90. El resultado ha sido la creación de programas mucho más sólidos, con una IA

5

táctica realmente asombrosa, programas mucho más exactos sin apenas errores, y conducidos hacia el límite de su profundidad de búsqueda. Esto ha producido resultados extraordinarios, por lo menos en lo referente al ajedrez, dejando que las computadoras hagan lo que mejor saben hacer, calcular, en vez de intentar emular la inteligencia y conocimiento humanos. En 1997, Deep Blue, una computadora de Tipo A, derrotó al Campeón del Mundo Garry Kasparov, siendo la primera vez que una computadora derrotara al campeón del mundo en tiempos de control de torneo. Sin embargo, a finales de los años 1990, los programadores empezaron a preferir los programas de Tipo B, y empezaron a sustituir a los de Tipo A. En 1998 se publica Rebel 10, un programa comercial de Tipo B, quien derrotó a Viswanathan Anand por 5-3, y se proclamó el segundo motor de ajedrez más fuerte del mundo aquel año. Cabe decir que de las cuatro partidas de ajedrez rápido (tiempo de control: 5 min + 5 s por jugada) que se jugaron, Rebel ganó 3 de ellas, en las dos partidas semirrápidas, quedaron 1.5-0.5 a favor de Rebel, y en la partida con tiempo de control más largo (40/2:00, 1 hora), fue Anand quien venció. De esto se puede deducir que las computadoras juegan mejor que los humanos en tiempos de control más rápidos, pero que la fuerza de los jugadores se mide con tiempos de control más largos, donde Anand demostró que los humanos siguen siendo mejores.3 A principios del Siglo XXI surgieron nuevos programas de ajedrez comerciales, como Deep Junior, o Fritz, quienes lograron empatar a los campeones del mundo Garry Kasparov y Vladímir Krámnik. En el 2005, Hydra, una computadora de ajedrez del Tipo B, derrotó al mejor jugador británico y séptimo mejor clasificado del mundo, Michael Adams, en un encuentro de seis partidas con un contundente resultado: 5.5 - 0.5 a favor de Hydra.4

La Novedad: En Alessandro v1.0 se combinan los programas Tipo A con los Tipo B aprovechando las fortalezas que brinda cada uno, la imitación de los procesos del pensamiento humano de los primeros y la intención de aprovechar las capacidades de cómputo de los ordenadores del segundo. Con tales intenciones se hace uso de un conjunto de algoritmos propios de la IA que aseguran incrementar exponencialmente la fuerza de juego del motor. Algoritmo Minimax: En teoría de juegos, Minimax es un método de decisión para minimizar la pérdida máxima esperada en juegos con adversario y con información perfecta. Minimax es un algoritmo recursivo. Su funcionamiento puede resumirse como elegir el mejor movimiento para ti mismo suponiendo que tu contrincante escogerá el peor para ti.

6

Figura 1. Algoritmo Minimax.

Poda alfa beta: es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy utilizada en programas de juegos entre adversarios como el ajedrez. El problema de la búsqueda Minimax es que el número de estados a explorar es exponencial al número de movimientos. Partiendo de este hecho, la técnica de poda alfa-beta trata de eliminar partes grandes del árbol, aplicándolo a un árbol Minimax estándar, de forma que se devuelva el mismo movimiento que devolvería este, gracias a que la poda de dichas ramas no influye en la decisión final.

Figura 2. Poda alpha-beta. 

En Pseudocódigo: función alfabeta(nodo, profundidad, α, β) si nodo es un nodo terminal o profundidad = 0 devolver el valor heurístico del nodo para cada hijo de nodo α := max(α, -alfabeta(hijo, profundidad-1, -β, -α)) si β≤α break devolver α (* Llamada inicial *) alfabeta(origen, profundidad, -infinito, +infinito)

7

Negascout: es una variante del algoritmo Minimax, es un algoritmo que combina la relación matemática del Negamax y el uso de ventana nula. También llamado "búsqueda de la variante principal" este algoritmo puede ofrecer rendimientos incluso mayores a la poda alfa-beta si los nodos se encuentran correctamente ordenados. Al igual que alfa-beta, negascout es un algoritmo de búsqueda direccional para calcular el valor minimax de un nodo en un árbol. La mejora del algoritmo negascout sobre el algoritmo alfa-beta es que el primero no examinará un nodo que el segundo podaría. 

En Pseudocódigo: int negascout(nodo, profundidad, α, β) { if (esTernimal(nodo) || profundidad==0) return valorHeuristico(nodo); b = β; // la ventana inicial es (-β, -α) foreach nodoHijo a = -negascout (hijo, profundidad-1, -b, -α); if (a>α) α = a; if (α>=β) return α; //Corte Beta if (α>=b) //comprueba si fallo la ventana nula α = -negascout(hijo, profundidad-1, -β, -α); búsqueda completa if (α>=β) return α; //Corte Beta b = α+1; //Crea nuava ventana nula return α; }

//Nueva

Otros algoritmos empleados son el de poda del movimiento nulo y búsquedas latentes, facilitado este último por una estructura de almacenamiento en forma de histórico de movimientos que hace posible su efectividad. Inteligencia Artificial (IA o AI): Es la característica más importante que se le atribuye a un motor al lado de la representación de modelos. La IA provee de estímulo al juego. Es crítico en la parte de la forma de juego (game play). La inteligencia artificial de determinado juego puede tornarse muy compleja, primero se debe definir la línea base del comportamiento de los elementos implicados en el juego. Es un sistema de reglas para las acciones que responden (o inician) y que el jugador debe responder. Game play Emergente (Forma de Juego Emergente): Consiste en programar al AI con un conjunto de reglas que le permitan la aplicación adherir situaciones que el programador no previera.

Resultados y discusión Tablas de finales Las computadoras, desde sus inicios, analizaban completamente las posiciones de los finales. Las bases de datos de finales10 están generadas por adelantado usando el análisis retrospectivo, empezando con posiciones donde el

8

resultado final es conocido (por ejemplo en posiciones donde un bando ha ganado por jaque mate), y analizar qué movimientos han conducido a la combinación final de piezas. Ken Thompson, más conocido por ser uno de los creadores del sistema operativo UNIX, fue uno de los pioneros en este tema. Durante mucho tiempo, los programas de ajedrez tuvieron graves problemas al jugar los finales, y eran muy débiles en dicho tramo de la partida, debido a la necesidad de una alta profundidad de búsqueda. Con distintos programas de alto nivel fueron incapaces de vencer en posiciones que cualquier humano de nivel intermedio sería capaz de ganar. A veces, los resultados de los análisis de las computadoras sorprenden a las personas. En 1977, Belle, la máquina de ajedrez de Ken Thompson, usando la tabla de finales KQKR, logró empatar una posición, en teoría perdida, de Rey y Torre contra Rey y Dama, contra varios jugadores norteamericanos profesionales. Muchos Grandes Maestros rehusaron jugar contra la computadora en los finales de dama contra torre, pero Walter Browne aceptó el desafío. En la partida se produjo un final de dama contra torre, donde la dama podía ganar en treinta movimientos, con un juego perfecto. Browne disponía de dos horas y media para jugar cincuenta movimientos. Después de cuarenta y cinco movimientos, Browne aceptó las tablas, siendo incapaz de forzar el mate o ganar la torre en los siguientes cinco movimientos. En la posición final, Browne estaba todavía a diecisiete movimientos de conseguir el jaque mate, pero no muy lejos de capturar la torre. Browne analizó el final, y jugó contra la computadora una semana más tarde. Esta vez, capturó la torre en el movimiento cincuenta, finalizando con una posición ganadora. Los avances en las tablas de finales de Ken Thompson, produjeron que a principios de los años 80, se cambiara la regla de los cincuenta movimientos, al demostrar que ciertos finales necesitaban más de cincuenta movimientos para poder vencer, como el final de rey, torre y alfil, contra rey y torre. Con el paso del tiempo se han ido publicando otros formatos de bases de datos de finales, incluyendo la base de datos Edward, la base de datos De Koning (publicada en 2002) y las Bases de Datos Nalimov, que es el formato más utilizado en la actualidad, soportado por la mayoría de los programas de ajedrez como Shredder y Fritz. Casi todos los finales de seis o menos de seis piezas, y varios de siete piezas, han sido analizados por completo. Las bases de datos se crean almacenando en la memoria valores de las posiciones, y usando estos resultados para podar los finales de los árboles de búsqueda si surgieran de nuevo. Aunque el número de posibles partidas después de que un número de movimientos aumente exponencialmente con el número de jugadas, el número de las posibles posiciones con unas pocas piezas es exponencial solamente en el número de piezas - y eficazmente limitado, sin embargo algunas jugadas de los finales son analizadas. El tener que recordar el valor de todas las posiciones obtenidas con anterioridad significa que el factor limitante para resolver finales se reduce simplemente a la cantidad de memoria disponible en el ordenador. Es por ello que mientras los tamaños de las memorias de los ordenadores continúen aumentando, no hay razón para creer que los finales de elevada complejidad no continúen resolviéndose. Una computadora que usa estas bases de datos va, al alcanzar la posición en ellas, a poder jugar perfectamente, e inmediatamente determinar si la posición acaba en victoria, derrota, o tablas. El conocimiento de si la posición acaba

9

en victoria, derrota, o tablas, también es útil de antemano, puesto que puede ayudar a la computadora a evadir o encaminarse hacia dichas posiciones dependiendo de la situación. Las tablas de finales tomaron gran importancia en 1999, cuando Kasparov jugó una partida de exhibición en Internet contra el Resto del Mundo, en la cual hubo cierta polémica.5 En dicha partida llegaron a un final de siete piezas, Reina y Peón, cuando el Resto del Mundo intentaba conseguir unas tablas. Eugene Nalimov colaboró generando el final de seis piezas cuando ambos bandos tenían dos Reinas, lo cual ayudó en gran medida al análisis.

Algunos elementos técnicos Los desarrolladores de sistemas de computadoras de ajedrez tienen que decidir varias cuestiones de implementación fundamentales. Estas son: 

Representación del tablero: cómo se representa una posición simple en estructuras de datos.



Técnicas de búsqueda: cómo identificar los posibles movimientos y seleccionar los más prometedores para examinarlos posteriormente.



Evaluación de hojas: cómo evaluar el valor de una posición del tablero, si no se hace una búsqueda posterior.

Los programadores también necesitan decidir si utilizarán bases de datos de finales u otras optimizaciones y a menudo implementar estándares de ajedrez comunes de facto. Representación del tablero La estructura de datos utilizada para representar cada posición de ajedrez es clave para el rendimiento de la generación de movimientos y la evaluación de posiciones. Los métodos incluyen el almacenamiento de las piezas en un array, las posiciones de las piezas en una lista ("lista de piezas"), colecciones de conjuntos de bits para la localización de piezas y posiciones codificadas con codificación Huffman para compactar el almacenamiento a largo plazo. Técnicas de búsqueda Los programas de ordenador de ajedrez consideran los movimientos como un árbol de juego. En teoría, examinan todos los movimientos y entonces todos los contra-movimientos a éstos y después todos sus respectivos contramovimientos, y así sucesivamente, donde cada movimiento individual se llama "hebra" o "ply". Esta evaluación continúa hasta que llega a una "hoja" final que es evaluada. Sin embargo, una implementación simplista de esta técnica nunca se terminaría en una cantidad de tiempo práctica, como consecuencia de esto se han ideado varios métodos para aumentar la velocidad de búsqueda para buenos movimientos. Evaluación de hojas Para muchas posiciones de ajedrez, los ordenadores no pueden considerar todas las posibles posiciones. En vez de ello, tienen que seguir unas cuantas hebras y entonces evaluar la posición final en el tablero. El algoritmo que evalúa

10

las posiciones finales se denomina función de evaluación y estos algoritmos frecuentemente son enormemente diferentes entre los distintos programas de ajedrez. Las funciones de evaluación típicamente evalúan posiciones en centésimas de peón y consideran el valor del material junto con otros factores que afectan la fuerza de cada bando. Cuando se cuenta el material de ambos bandos, los valores típicos para piezas son 1 punto para un peón, 3 puntos para los caballos y los alfiles, 5 puntos para las torres y 9 puntos para una dama. Por convención, una evaluación positiva favorece a las blancas y una negativa a las negras. Al rey algunas veces se le da un valor arbitrario alto como 200 puntos (artículo de Claude Shannon) o 1.000.000 de puntos (programa de la URSS de 1961) para asegurar que un mate sobrepasa al resto de factores. Las funciones de evaluación tienen en cuenta muchos factores, como la estructura de peones, la pareja de alfiles, la centralización de las piezas, etc. También se suele considerar la protección del rey, así como la fase en la que se encuentra la partida (apertura, medio juego o final). Utilizando bases de datos de finales Algunos operadores de computadoras de ajedrez han apuntado que las bases de datos de finales tienen el potencial de debilitar el rendimiento en computadoras de ajedrez si se utilizan incorrectamente. Como algunas posiciones son analizadas como victorias forzadas por un bando, el programa evitará las posiciones del bando perdedor a toda costa. Sin embargo, muchos finales sólo son forzados con un juego muy preciso, donde incluso un ligero error produciría un resultado diferente. Consecuentemente, muchas máquinas modernas jugarán muchos finales suficientemente bien para sus propios intereses. Un síntoma de este problema es que los ordenadores pueden abandonar demasiado pronto porque ven que están siendo forzados en una posición que está perdida teóricamente (aunque pueden estar a treinta o más movimientos del final de la partida y a muchos oponentes humanos les costaría mucho ganar en ese tiempo). Esta observación sólo es relevante cuando un programa de ordenador está en una situación donde tiene que elegir entre dos movimientos perdedores, uno de los cuales de hecho es más difícil para el oponente, pero condice a una posición en la base de datos con un valor conocido y es incluso de mucha menor importancia. Las bases de datos de Nalimov no consideran la regla de los cincuenta movimientos, en la que una partida donde pase cincuenta movimientos sin una captura o sin mover un peón pueda ser reclamada como tablas por un jugador. Esto da como resultado una base de datos que devuelve resultados como "Mate forzado en 66 movimientos" en algunas posiciones que serían tablas debido a la regla de los cincuenta movimientos. Sin embargo, una máquina correctamente programada conoce la regla de los cincuenta movimientos y en ningún caso utilizando una base de datos de finales elegiría el movimiento que conduciría a la victoria más rápida (incluso si sobrepasara la regla de los cincuenta movimientos con un juego perfecto). Si jugando con un oponente no se utiliza una base de datos de finales, tales elecciones darían buenas oportunidades de victoria dentro de la regla de los cincuenta movimientos. Una razón para esto es que si las reglas del ajedrez cambiaran otra vez, dando más tiempo para ganar tales posiciones, no sería necesario regenerar todas las bases de datos. También sería muy fácil para el programa utilizar las bases de datos para notar y tener en cuenta esta 'característica'.

11

Las bases de datos de Nalimov, que utilizan el estado del arte de las técnicas de compresión, necesitan 7.05 GB de espacio en disco duro para todos los finales de cinco piezas. Para cubrir todos los finales de seis piezas necesita aproximadamente 1.2 terabyte. Se estima que las bases de datos de siete piezas necesitarán más capacidad de almacenamiento de la que estará disponible en el futuro previsible. Es sorprendente, pero fácilmente comprobable, que sin una base de datos de finales incluso computadoras de ajedrez más fuertes puedan fallar a la hora de encontrar un plan ganador incluso en finales con seis o menos piezas, cuando necesitan más movimientos que el horizonte de cálculo para conseguir un jaque mate, una ganancia de material o el avance de un peón. Muchos finales necesitan más movimientos que su horizonte de cálculo. Otras optimizaciones Muchas otras optimizaciones se pueden utilizar para realizar programas de ajedrez más fuertes. Por ejemplo, las tablas de transposiciones se utilizan para grabar posiciones que ya han sido evaluadas, para evitar recalcularlas. Las tablas de refutación almacenan movimientos clave que "refutan" lo que parece ser un buen movimiento, éstas se utilizaron por primera vez en las variantes (ya que un movimiento que refuta una posición es probable que refute otra). Los libros de aperturas ayudan a los programas de computadoras dando las aperturas comunes que son consideradas buenas (y buenos caminos contra las aperturas más pobres). Por supuesto, con hardware de más velocidad y procesadores adicionales se puede mejorar la capacidad de los programas de ajedrez y algunos sistemas (como Deep Blue) utilizan hardware especializado en ajedrez en vez de únicamente implementaciones software. Estándares Los programas de ajedrez para computadoras normalmente soportan varios estándares comunes de facto. Casi todos los programas actuales pueden leer y escribir movimientos de ajedrez en el formato PGN y pueden leer y escribir posiciones individuales en formato FEN. Los antiguos programas de ajedrez frecuentemente sólo comprenden la notación algebraica larga, pero los usuarios actuales esperan que los programas de ajedrez comprenda la notación algebraica convencional. Muchos programas de computadora de ajedrez se dividen en un motor (que calcula el mejor movimiento de la posición actual) y una interfaz de usuario. Muchos motores están separados del interfaz de usuario y las dos partes se comunican entre sí utilizando un protocolo de comunicación público. El protocolo más popular es el protocolo Xboard/Winboard Communication. Otro protocolo abierto de comunicación de ajedrez alternativo es el Universal Chess Interface. Dividiendo los programas de ajedrez en estas dos piezas, los desarrolladores sólo tienen que programar el interfaz de usuario o el motor, sin la necesidad de escribir ambas partes del programa. Fuerza de juego contra velocidad de proceso Se ha estimado que al doblar la velocidad de computación se gana aproximadamente entre cincuenta y setenta puntos de Elo en fuerza de juego.

12

Sin embargo, esto se aplica principalmente a matches entre computadoras y no a matches entre computadoras y humanos, donde este incremento sería bastante menor.

Figura 3. Diagrama de paquetes y módulos del Chess Engine Alessandro v1.0

Figura 4. Rating ELO de Enero 2014 según CCRL6.

Conclusiones Con la realización del motor de juego Alessandro v1.0 vio la luz el primer motor de juego de ajedrez creado en Cuba, un software libre que sirve de apoyo al proceso de enseñanza-aprendizaje, además de posibilitar su uso para el entrenamiento de alto nivel de los usuarios y la participación del motor en torneos internacionales en representación

13

de Cuba, demostrando la fuerza histórica del ajedrez en la Isla. Entre los principales logros de Alessandro v1.0 pueden notarse los buenos resultados en los torneos en que ha participado, la capacidad de integración con las diferentes plataformas y protocolos de comunicación visual existentes para programas de ajedrez, y la independencia del sistema operativo sobre el que se encuentre corriendo la aplicación. Se incorporaron novedades significativas en la arquitectura del engine, partiendo de la conjugación de elementos de simulación del pensamiento humano y aprovechamiento de las potencialidades de los dispositivos informáticos, que contribuyeron a elevar de manera sustancial el nivel de juego frente a humanos y máquinas. Finalmente se incorporaron al software una serie de optimizaciones que zanjaron deficiencias presentadas por la aplicación en sus versiones anteriores.

Referencias 1. What is a Game Engine? Tomado de GameCareerGuide.com 2.

Shannon, Claude E. (1950), "Programación de una Computadora para Jugar al Ajedrez", Philosophical Magazine, vol. Ser.7, Vol. 41, no. 314

3. Rebel vs Anand. http://www.rebel.nl/anand.htm 4. Hydra vs Michael Adams. http://www.chessposter.com/spanish/grandes_juegos/hydra_adams_e/hydra_vs_adams_e.htm 5. Kasparov vs. El Resto del Mundo – Polémica. http://www.elmundo.es/1999/10/22/sociedad/22N0127.html 6. Rating ELO de Enero 2014 según CCRL (http://computerchess.org.uk/ccrl/4040/rating_list_all.html)

Bibliografía 1 S. Akl, D. Barnard and R. Doran: The Design, Analysis and Implementation of a Parallel Alpha-Beta Algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-4, (2), (1982) 192-203. 2. J. H. Condon and K. Thompson: Belle Chess Hardware, Advances in Computer Chess III, Pergamon Press, (1972) 44-54. 3. C. Donninger: Null move and Deep Search: selective-search heuristics for obtuse chess programs ICCA Journal, Vol. 16, No. 3, (1993) 137-143. 4. C. Donninger and U. Lorenz: The Chess Monster Hydra, Univesitat Paderborn, Faculty of Computer Science, Electrical Engineering and Mathematics, Paderborn, Germany, www.hydrachess.com, 2004. 5. R. Feldmann, B. Monieni, P. Mysliwietz and O. Vornberger: Distributed game tree search, in Parallel algorithms for machine intelligence and pattern recog-

14

nition, 1990. 6. R. Finkel and J. Fishburn: Parallelism in Alpha-Beta Search, Artificial Intelligence (1982) 89-106. The Method of the Chess Search Algorithms Parallelization ... 187 7. P.W. Fray: An introduction to Computer Chess. Chess Skill in Man and Machine, Texts and monographs in computer science, Springer-Verlag, New York, N.Y. , 1977. 8. R. Hyatt: A High-Performance Parallel Algorithm to Search Depth-First Game Trees, Ph.D. Dissertation, University of Alabama at Birmingham, 1988. 9. R. Hyatt, A. Gower and H. Nelson: Cray Blitz, Advances in Computer Chess 4, Pergammon Press (1986) 8-18. 10. R. Hyatt, H. Nelson and A. Gower: Cray Blitz - 1984 Chess Champion, Telematics and Informatics (2) (4), Pergammon Press Ltd. (1986) 299-305. 11. R. Hyatt, B. Suter and H. Nelson: A Parallel Alpha/Beta Tree Searching Algorithm, Parallel Computing 10 (1989) 299-308. 12. F.H. Hsu, T.S. Anatharaman, M. Campbell and A. Nowatzyk: Deep Thought, Computers, Chess and Cognition, chapter 5, Springer Verlag (1990) 55-78. 13. F.H. Hsu: IBM’s Deep Blue Chess Grandmaster Chips, IEEE Micro 19(2), (1999) 70-80. 14. D. Knuth and R. Moore: An Analysis of Alpha-Beta Pruning, Artificial Intelligence 6 (1975) 293-326. 15. B. Kuszmaul: Synchronized MIMD Computing, Ph.D. Thesis, MIT, 1994. 16. T. Marsland and M. Campbell: Parallel Search of Strongly Ordered Game Trees, ACM Computing Surveys (4) (1982) 533-551. 17. T. Marsland and M. Campbell: Methods for Parallel Search of Game Trees, Proceedings of the 1981 International Joint Conference on Artificial Intelligence, 1981. 18. T. Marsland, M. Campbell and A. Rivera: Parallel Search of Game Trees, Technical Report TR 80-7, Computing Science Department, University of Alberta, Edmonton, 1980. 19. T. Marsland, M. Olafsson and J. Schaeffer: Multiprocessor Tree-Search Experiments, Advances in Computer Chess 4, Pergammon Press (1986) 37-51.

15