Ciencias de la Computación (plan 1994) 2014-1

Optativas, Seminario de Inteligencia Artificial

Seminario de ajedrez por computadora

El objetivo de este seminario es entender los avances que ha habido en el campo del ajedrez por computadora, sus técnicas, los algoritmos, las limitaciones, etc. Para ello se realizarán una serie de lecturas de los artículos más relevantes. Se buscará además, en la medida de lo posible, desarrollar herramientas computarizadas que sean útiles para el ajedrecista. No necesariamente se tienen que escribir programas que jueguen al ajedrez. Se pueden crear programas para llevar análisis, para encontrar jaque mates en N jugadas, para valorar posiciones, para hallar patrones específicos de posiciones importantes dentro del juego, etc. El siguiente temario es un bosquejo de lo que puede darse, pero desde luego, no abarca todas las posibilidades

Introducción

• Chess (por A. Turing)
• Programming a computer for playing chess (por C. E. Shannon)
• The Chess Machine: an example of dealing with a complex task by adaptation (A. Newell)

Programas de ajedrez famosos

• Belle (Bell Labs. Ken Thompson)
• A chess playingt program for the IBM 7090 (A. Kotkov)
• The Greenblatt Chess Program (R.D. Greenblatt)
• Chess 4.5 (L. Atkin y D. Slate)
• Cray Blitz (Robert Hyatt)
• Evaluación de las posiciones

Búsquedas con técnicas de árboles

• Tree searching and tree pruning techniques (J. Birmingham y P. Kent)
• Some methods of controlling the tree search in chess programs (Adelson)
• The heuristic chess and the game of chess (L.R. Harris)
• The minimax search (D. Michie)

Análisis del ajedrez

• Secuencia de fases (De Groot)
• Skill in chess (Simon y Chase)
• Decision making and computers (Botvinnik)
• A chess mating combination program (G.W. Baylor)

Cómo escribir un programa de ajedrez

• Computer chess tutorial (Whaland)
• Using patterns and plans in chess (Wilkins)

Técnicas avanzadas

• Some ideas for chess compiler (MRB Clarke)
• CHEOPS: A chess oriented processing system (Greenblatt)
• Patrones en Ajedrez

El final

• Chess pawn endgames (Church)
• Tablas de finales de Thompson
• Tablas de finales de Nalimov

Bibliografía:

• Chess Skill in Man and Machine (Peter Frey)
• How Computers Play Chess (David Levy)
• Computer Chess and Long Range Planning (Mijail Botvinnik)
• The Chess Computer HandBook (David Levy)

Prácticas sugeridas

Prácticas del seminario de inteligencia artificial (ajedrez por computadora)

Creación de los siguientes programas:

1. un sistema para generar diagramas de ajedrez (como aparecen en los libros). El sistema debe generar imágenes JPG o bien el diagrama para ser usado con los tipos de letra Truetype (TTF) que tienen piezas de ajedrez. Se les proporcionan dichos fonts.

2. Un programa que pueda leer archivos PGN (Portable Game Notation), que es el formato universalmente aceptado para describir partidas de ajedrez

3. Un programa que genere una base de partidas y que el usuario pueda ver en un tablero electrónico cada partida si lo desea

4. Una calculadora de rating (Elo), que es la medida de la fuerza ajedrecística. Diseñado e inventado por Arpad Elo, el sistema se usa a nivel mundial para clasificar a los jugadores por su fuerza ajedrecística.

5. Un programa que genere ejercicios de táctica, con sus respectivas soluciones. Aquí se trata de hacer un intérprete de comandos en un lenguaje adecuado para seguir instrucciones en un tablero de ajedrez. El lenguaje de guiones, script, permite crear posiciones, preguntarle al usario por la respuesta, poner flechas y señales de colores de acuerdo a las jugadas que el usuario realice en el tablero electrónico. Se puede añadir calificaciones (o cálculo del rating) para efectos de medir el progreso.

6. Un programa que permita entrenarse en la modalidad del ajedrez a la ciega. La intención es que el ajedrecista pueda practicar partidas en tableros vacíos, en donde solamente se le dan las jugadas y en donde hay que llevar en la mente el tablero. El ajedrecista puede en cualquier momento ver si en su mente la partida va como en realidad se está desarrollando.

7. Escribir un programa que juegue al ajedrez como lo hacía Sargon, un programa de los años 80s para las computadoras de 8 bits. Existe en la web la referencia completa de cada rutina escrita en ensamblador x86 y existe una versión en javascript que bien podría usarse para desarrollar un programa elemental en este sentido.

8. Generar una base de datos de todas las partidas que se han jugado, posición por posición, en los últimos quinientos años de ajedrez. Hay alrededor de 5 millones de partidas registradas y se pretende que el usuario busque cualquier posición que pudiese haber dado en cada movimiento de cada partida. Obviamente se haría con un subconjunto de los cinco millones de partidas.

9. Un programa que genere un sistema de tarjetas bibliográficas para alimentar posiciones de ajedrez. Se sugiere que dicho tarjetero funcione a través de la web, para que así se puedan dar de alta los usuarios y se genere una base de información ajedrecística a nivel mundial y global.