Deep blue es un software de Ajedrez el cual trabaja sobre un sistema de propósito especial (special purpose) y paralelismo masivo que utiliza un computador de alto rendimiento IBM RS/6000 SP de 32 nodos. Este computador posee el procesador Power Two Super Chip (P2SC).

Cada nodo del IBM RS/6000 SP utiliza una tarjeta microcanal la cual contiene 8 procesadores VLSI dedicados de Ajedrez, totalizando 256 procesadores trabajando en paralelo.

El software utilizado esta escrito en C y se corre bajo el sistema operativo AIX

El resultado es un sistema altamente paralelo y escalable que es capaz de calcular entre 100 y 200 miles de millones de movidas en 3 minutos. Un humano en estado de concentración y a nivel de Gran Maestro de Ajedrez es capaz de calcular unas 3 posiciones por segundo (540 posiciones en 3 minutos)

El sistema no fue creado especialmente para sólo un juego de ajedrez, sino que a nivel de arquitectura se pretende obtener un computador que pueda realizar una enorme cantidad de cálculos por segundo en forma paralela. El tipo de cálculos que se puede realizar con este sistema no es optimizado, es decir no se paraleliza cada cálculo, sino que se pueden realizar varios cálculos en paralelo con la ayuda de procesadores dedicados que son más rápidos y que poseen su propia memoria local y además comparten una memoria global. La memoria local de cada procesador es de tamaño muy pequeño comparado con la memoria global del computador.
La arquitectura del sistema se puede resumir en la utilizacion de procesadores aceleradores de cálculos especiales paralelos combinados con un sistema multipropósito que los controla.

El Sistema RS/6000

El sistema RS/6000 SP entrega una gran escalabilidad que permite soportar muchas aplicaciones paralelas. El sistema es escalable desde 2 hasta 128 nodos del procesador (e incluso hasta 512 nodos en forma no comercial), los cuales pueden estar contenidos en múltiples frames. Un sólo frame puede contener desde 2 hasta 16 nodos. Los nodos pueden ser de tipo angosto o ancho, lo que determina el ancho de banda del acceso a los datos.

En el caso de Deep Blue, el procesador tiene 32 nodos cada uno conectado a 8 procesadores aceleradores de Ajedrez y los nodos son del tipo ancho.
Cada procesador conectado a un nodo del computador puede operar como un procesador independiente trabajando simultáneamente con los otros en un trabajo específico para acelerar el cálculo final. El elemento clave es entonces el subsistema de comunicación, el cual es llamado Scalable Power Parallel Switch, cuya responsabilidad es intercambiar mensajes simultáneamente entre los nodos para apoyar la aplicación paralela del usuario.

El switch de comunicación se diagrama en la siguiente figura optimizado para 32 nodos:



Para el caso de más nodos se puede utilizar un conjunto de switch intermedios entre los distintos frames o conjuntos de nodos:




Utilizando entonces el switch de comunicación, el procesador puede enviar mensajes a los procesadores conectados a los nodos. Cada procesador dedicado de Ajedrez recibe entonces una movida a partir del tablero que se encuentra en memoria global mediante un mensaje por el switch. Además recibe la profundidad y otros parámetros útiles (tiempo, dirección en memoria de la tabla de hashing para evitar repetición de movidas entre los procesadores, etc).

Cada nodo se conecta a la tarjeta microcanal utilizando un switch que permite detectar los errores en los mensajes. Esta tarjeta consta de diversas partes incluído un microprocesador PowerPC 601, como se observa en la figura :




Este switch se encarga de diversas tareas sobre el envío y recepción de mensajes y está optimizado para el uso de mensajes de gran tamaño. Para ello utiliza una cola FIFO y un microprocesador para detectar errores. El ancho de banda alcanzable gracias a este switch es de unos 150 Mb por segundo unidireccional y 300 Mb por segundo bi-direccional.

El Procesador de Ajedrez

Como ya se dijo, este procesador esta encargado de analizar cuán buena es una jugada a partir de un tablero y una movida. Para ello tiene lee una función de evaluación y utiliza fuerza bruta para encontrar el valor de esta función hasta la profundidad que alcance hasta que le llegue el mensaje de detener la búsqueda. Cuando termina de buscar, retorna el valor de la función para esa movida.

El procesador consta principalmente de un chip que posee más de un millón de transistores. En si interior tiene integrados 48 bloques de RAM y 3 bloques de ROM. os bloques de RAM se utilizan para almacenar los tableros que se vayan generando a medida que realiza la búsqueda y los bloques de ROM contienen información sobre finales de partidas.

No todos los bloques de RAM y ROM son del mismo tamaño. Por ejemplo el bloque de RAM más grande son de 1024 palabras de profundidad por 10 bits de ancho. Existe un bloque de ROM de mayor tamaño que posee 128000 palabras más un bit para cada una almacenando información booleana (triunfo/tablas) acerca de finales de Peón-Rey contra Rey.



Este procesador puede analizar entre 2 y 3 millones de posiciones del tablero de ajedrez por segundo. Considerando que el análisis de una posición consiste de unas 3000 instrucciones de máquina como promedio, entonces el procesador tendría una velocidad entre 6 y 9 mil millones de instrucciones por segundo.

En Deep Blue hay 256 de estos procesadores (8 por cada nodo).

Deep Blue

Deep Blue es un software que utiliza fuerza bruta para jugar ajedrez. Se utiliza fuerza bruta pues la idea del sistema es poder demostrar el uso masivo de paralelismo y su extensión a otras aplicaciones. No se pretende crear un software que sepa jugar Ajedrez sino un software que pueda aprovechar el paralelismo masivo para un problema complejo, como por ejemplo el ajedrez. Esto se contrapone con la tecnología desarrollada para crear procesadores dedicados de ajedrez, por lo tanto se puede deducir que el interés por el desarrollo de Deep Blue es puramente comercial.

Deep Blue es sólo una combinación de estrategias y rápidos cálculos en paralelo que permiten encontrar en forma muy precisa aquella movida que considera "mejor" dado que en promedio existen 20 posibles movidas en cada turno. Deep Blue utiliza Fuerza Bruta. Las movidas que analiza son escogidas selectivamente utilizando una estrategia modelada a prueba y error con la ayuda de varios Grandes Maestros de Ajedrez y algunos conceptos del juego. Una vez generada una jugada se analiza mediante una función de evaluación que mide cuán buena es una posición. Esta función se basa en 4 conceptos de Ajedrez: Material, Posición, Seguridad del Rey, y Tiempos.

La generación de movidas se hace por software en forma estratégica para cada procesador de Ajedrez y evalúa la posición rápidamente gracias a las características del procesador de Ajedrez. Posteriormente descarta o sigue profundizando según lo ordene el procesador principal. De esta forma puede evaluar 256 "ramas" o movidas en forma paralela.

Los procesadores de ajedrez son controlados por el procesador principal mediante el sistema de mensajes. La búsqueda se reduce entonces a un simple control lógico a nivel del procesador manejando variables como tiempo, mate cercano, etc.

---

27 de Noviembre de 1998