Download INTELIGENCIA ARTIFICIAL Y MOTORES DE - PCyTI

INTELIGENCIA ARTIFICIAL Y MOTORES DE AJEDREZ
Responsable de la propuesta:
Dr. John Goddard Close (Departamento de Ingeniería Eléctrica, UAM Iztapalapa).
Perfil deseable del alumno:
• Conocimientos generales de conceptos de Inteligencia Artificial.
• Conocimientos básicos de Ajedrez.
• Conocimientos de programación en C y enfocada a objetos.
Presentación del contexto e identificación de la problemática
Los juegos, como ajedrez y damas, han tenido importancia en el desarrollo de la Inteligencia
Artificial. Turing diseñó el primer algoritmo para jugar ajedrez, como ejemplo de lo que una
computadora podría realizar, y en 1950, Shannon introdujo ideas fundamentales tales como
funciones de evaluación y el algoritmo minimax en el mismo contexto de ajedrez. Posteriormente,
a partir de los 1950s, Samuel fue un pionero en Aprendizaje Maquinal aplicado a juegos. Con el
primer congreso de Inteligencia Artificial en 1956, se pensó M que en diez años habría un programa
capaz de ganar a un campeón mundial. Sin embargo, el problema resultó mucho más complicado.
En este proyecto, se propone reexaminar el juego de ajedrez por computadora, inicialmente
estudiando los motores de ajedrez, MA, (en ingles, Chess Engines).
En un sentido estricto, el motor de ajedrez es el módulo que calcula, a partir del estado del tablero
y de algún protocolo de decisión, las mejores jugadas y elije una de ellas como tirada siguiente. Una
interfaz de ajedrez tomará la salida del CE para presentarla al usuario. Para la comunicación entre el
módulo del motor y el módulo de presentación, hay dos protocolos ampliamente utilizados de
comunicación: el XBOARD y la reciente Interfaz de Ajedrez Universal (UCI).
Los MA actuales
Uno de los mayores programas de ajedrez gratuitos es el proyecto de código abierto Crafty por
Robert Hyatt. Otro motor robusto de ajedrez es el programa Fruit, el cual en el Campeonato
Mundial de Ajedrez por computadora en 2005 obtuvo el segundo lugar. Hasta la versión 2.1 Fruit
estaba disponible bajo una licencia de código abierto, el cual tenía un performance casi como
Glaurung 2.1. Una versión preliminar del programa Zappa, el cual ganó la Copa del Mundo de 2005,
es accesible como software libre en Internet.
Para este proyecto se propone el estudio de dos MA:
 Tom Kerrigan's Simple Chess Program (TSCP) [1]. El cual es un pequeño MA escrito en 1997,
cuya función es demostrar las bases de la programación de los motores de ajedrez.
 Stockfish [2]. Es un MA cuyo desempeño se asemeja a motores comerciales como Rybka 4 y
Houdini 2, incluso se presume como el motor de ajedrez más poderoso de código libre en el
mundo [3].
Las partes principales de un programa de ajedrez son el generador de movimiento, la función de
evaluación y una parte del programa para controlar la búsqueda y la selección de la próxima tirada.
A partir de la posición actual (tablero actual) de partida, el motor realiza una búsqueda en
profundidad iterativa. En cada iteración se llevan a cabo varias tiradas consecutivas posibles del
jugador y del adversario, se evalúan las posiciones alcanzadas (hojas del árbol de búsqueda) con la
función de evaluación, y la base de estos valores de hoja son evaluados los nodos internos del árbol
de búsqueda de acuerdo con el principio minimax. Una de las características más distintivas de los
programas de ajedrez es el tipo de representación en el consejo interno, que hacen uso de todos
los demás componentes del programa.
Objetivos del proyecto de investigación
Objetivo general
El objetivo general del proyecto es encontrar métodos adecuados para los Motores de Ajedrez
mediante la aplicación de técnicas de inteligencia artificial.
Objetivos específicos
• Estudiar y entender los dos MA propuestos.
• Evaluación del desempeño de distintas técnicas de inteligencia artificial en el contexto de los
MA.
• Desarrollo e implementación de algún protocolo híbrido basado en técnicas de inteligencia
artificial para usar como MA.
Metodología propuesta
• Estudio de los MA propuestos y los métodos usados en ellos.
• Estudio de algunos algorítmos heurísticos que han sido aplicados para automáticamente
mejorar el desempeño de juegos, como ajedrez.
• Desarrollo y aplicación de algorítmos de inteligencia artificial para obtener un MA propio.
• Comparación del MA propio con otros MA.
Resultados esperados
• Implementación de los algoritmos seleccionados.
• Posible mejora de alguno de los algoritmos estudiados.
• Participación en competencias de MA’s organizadas por terceros.
• Posible publicación de un artículo en una revista o congreso nacional o internacional.
Bibliografía inicial
 David N. L. Levy, Monty Newborn, How Computers Play Chess, Ishi Press, 2009.
 Monty Newborn, Monroe Newborn, Beyond Deep Blue, Springer, 2011.
 Advances in Computer Games: 12th International Conference, ACG 2009, Pamplona, Spain, May
11-13, 2009, Revised Papers, Springer, 2010.
 Genetic Programming: 7th European Conference, EuroGP 2004, Coimbra, Portugal, April 5-7,
2004, Proceedings, Volumen 7 ,Springer, 2004.
 B. Boskvic, J.Brest, A.Zamuda, S.Greiner, V.Zumer History mechanism supported differential
evolution for chess evaluation function tuning, Soft Comput. 15:667-683, 2011.
Websites
1. Tom Kerrigan's Simple Chess Program (TSCP). http://www.tckerrigan.com/Chess/TSCP
2. Stockfish Powerful Open Source Chess Engine. http://stockfishchess.org
3. Computer Chess Rating Lists. http://www.computerchess.org.uk/ccrl/4040/
Calendarización de actividades
Se proponen las actividades y resultados esperados en cada trimestre.
Trimestre
Actividades
Resultados
1
Estudio de los dos MA de código abierto y
los métodos usados en ellos.
Protocolo de la Idónea Comunicación de
Resultados: Estado del Arte.
2
Estudio y desarrollo de técnicas de
inteligencia artificial aplicadas a los MA.
Presentación del desarrollo del protocolo del
CE en formato de artículo.
3
Implementación de técnicas de inteligencia
artificial a un MA propio. Análisis y
comparación del protocolo desarrollado
respecto a los protocolos actuales de
código abierto.
Primer borrador de la Idónea Comunicación de
Resultados.
4
Redacción de la versión final.
Entrega de la versión final de la Idónea
Comunicación de Resultados y defensa oral del
trabajo de investigación ante un jurado
especializado.
Infraestructura necesaria y disponible
 Computadora.
 Software especializado.
 Datos especializados.
Lugar de realización
Laboratorio del Habla, UAM Iztapalapa.