martes, 19 de junio de 2018

El paradigma del Factor de Bloqueo en COBOL

COBOL es muy considerado no solamente por su sencillez en la programación, sino también, y fundamentalmente, por la altísima performance de sus archivos indexados, tanto en escritura como en lectura. Como se sabe, los archivos indexados son indispensables para la rápida ubicación de registros, en forma lo más inmediata posible de estos, ya que para el usuario final no son admisibles las esperas de tiempos extensos (en algunos casos varios segundos) para recuperar la información necesaria. Entonces, los archivos indexados son insustituibles. Así se implementa hoy día, tanto en archivos ISAM y VSAM, como en bases de datos relaciones, y alguna más de otro tipo que para este informe no vienen al caso.

Antiguamente, cuando las únicas opciones eran la grabación de archivos en cintas magnéticas o discos duros de poca capacidad (no más de 5 MB), la considerción de ahorro de espacio era un parámetro siempre crítico a tener en cuenta. Sin embargo, hoy día, con discos que se establecen ya en terabytes frente a las antiguas velocidades de acceso, esto es despreciable; ahora los archivos solo se limitan a la capacidad de manipulación entregada por los lenguajes y no por el hardware. En virtud de esto, antiguamente, cuantas más opciones de ahorro de espacio en almacenamiento se lograra, era muy bien recibido. Por tanto, el "pegar" fìsicamente un registro a otro cuando se estaba grabando, era fundamental, sin desperdicio de espacio. Para ello, por ejemplo, COBOL incluía (e incluye) lo que se conoce como Factor de Bloqueo (FB); esto es, considerando que el tamaño del sector (también llamado "bloque", y no confundir con "clúster", que es un conjunto de sectores contiguos), una clásula que permite "pegar" los registros en un mismo sector. Esto se logra, por parte del programador, dividiendo el tamaño del bloque de Windows (que puede ser 512, 1024, 2048 o 4096 bytes por bloque, dependiendo de la FAT de Windows) entre la cantidad de bytes del registro.

Por ejemplo, si el bloque (o sector) de Windows fuera de 1024 KB, y el tamaño del registro del archivo es de 10 bytes, la cuenta daría 102,4 registros en el bloque, donde esa fracción de 4 se perdería, pero es desestimable pero no inútil, ya que sería utilizada por alguna otra aplicación distinta (Excel, etc.) si es que es suficiente para alojar algo.

Hoy día, con los descomunales tamaños de los discos duros, cuando se graba un registro, es indiferente el ahorro de espacio. He intentado dejar esto en claro realizando un benchmark entre dos archivos con el mismo tamaño: un campo numérico de 10 bytes como clave primaria:

           Select OutputFile    assign to random, "OutputFile.BM"
                                organization is indexed
                                access mode  is dynamic
                                record key   is Of-Count
                                file status  is Fs-Gral.

           Select OutputFileBlk assign to random, "OutputFileBlk.BM"
                                organization is indexed
                                access mode  is dynamic
                                record key   is OfBlk-Count
                                file status  is Fs-Gral.

La declaración para el archivo sin FB de registros es la siguiente:

       Fd  OutputFile.
       01  Reg-OutputFile.
           03 Of-Count   pic 9(10).

Y esta es la declaración del archivo con FB, considerando un bloque de 1024 KB:

       Fd  OutputFileBlk block contains 102 records
                         record contains 10 characters
                         label record is standard.
       01  Reg-OutputFileBlk.
           03 OfBlk-Count pic 9(10).

La finalidad de este ejercicio es comprobar si Windows 10 da curso al FB. Como se comprobó con el benchmark, sí le da curso, pero sus resultados son, en principio (quedan más cosas para chequear, como el armado de la tabla de índices hash), algo indefinidos, pero se puede concluir que no vale la pena establecer un FB en los archivos. Veamos en estos ejemplos por qué.

En esta instancia, se grabaron 500.000 registros sin FB en un archivo, y los mismos con FB en el otro archivo. Los tamaños de los archivos quedaron de la siguiente manera:

500.000 registros s/FB

OutputFileBlk    10,108,928 MB    FB: 1024
OutputFile       10,264,576 MB    FB: 1024

Luego se aumentó el tamaño del bloque a 4096 bytes, dando por resultado 409 registros por bloque, y el resultado fue el siguiente:

500.000 registros c/FB

OutputFileBlk    17,199,104 MB    FB: 4096
OutputFile       10,264,576 MB    FB: 4096

Ahora veamos los tiempos de grabación y de lectura de cada archivo:

Grabacion 500.000 registros s/B inicia:    13:47:29:29
Fin grabacion s/B.....................:    13:50:28:53

La grabación de los 500.000 registros del archivo sin FB insumió 3 minutos.

Grabacion 500.000 registros c/B inicia:    13:50:28:53
Fin grabacion c/B.....................:    13:56:47:34

La grabación de los 500.000 registros del archivo con FB insumió más de 6 minutos.

Esto indica claramente que la "performance" entre uno y otro da por mejor al que no tiene FB, y esto se explica de la siguiente manera: Windows sí aplica el FB, pero ello le consume más tiempo a COBOL dado que tiene "que tomarse un tiempo" para establecer la estructura del árbol de índices, según donde vayan cayendo los registros en un disco particionado. Esto es, determinar en las páginas del índice el bloque y la posición del registro en el mismo (tarea nada sencilla, pero infalible en exactitud para COBOL). Cuando no establecemos FB, para Windows es mucho más sencillo, pues pone los registros donde puede y le tira a COBOL la información de dónde se encuentra el registro, y COBOL arma sin estrés el árbol-B.

Ahora veamos los tiempos de lectura de los 500.000 registros de esos archivos, en el mismo bechmark:

Inicio lectura s/B....................:    13:56:47:35
Fin lectura s/B.......................:    13:57:13:72  26"

Inicio lectura c/B....................:    13:57:13:72
Fin lectura c/B.......................:    13:57:38:87  25"

La diferencia es de apenas un segundo.

Ahora, la cosa cambia un poco cuando declaramos archivos con múltiples claves con duplicados. Veamos esta.

Select optional StkLinFac assign to random, NombreStkLinFac
                          organization is indexed
                          access mode  is dynamic
                          record key   is SLF-Clave01 = SLF-Fecha,  SLF-NroCli,   SLF-NroArt               with duplicates
                alternate record key   is SLF-Clave02 = SLF-NroCli, SLF-Fecha,    SLF-NroArt               with duplicates
                alternate record key   is SLF-Clave03 = SLF-NroArt, SLF-Fecha
                alternate record key   is SLF-Clave04 = SLF-Fecha,  SLF-NroArt                             with duplicates
                alternate record key   is SLF-Clave05 = SLF-Fecha,  SLF-Zona,     SLF-NroArt               with duplicates
                alternate record key   is SLF-Clave06 = SLF-Zona,   SLF-Fecha,    SLF-NroArt               with duplicates
                alternate record key   is SLF-Clave07 = SLF-Ramo,   SLF-Fecha,    SLF-NroArt               with duplicates
                alternate record key   is SLF-Clave08 = SLF-Fecha,  SLF-Ramo,     SLF-NroArt               with duplicates
                alternate record key   is SLF-Clave09 = SLF-Grupo,  SLF-SubGrupo, SLF-NroArt    SLF-Fecha  with duplicates
                alternate record key   is SLF-Clave10 = SLF-Fecha,  SLF-Grupo,    SLF-SubGrupo, SLF-NroArt with duplicates
                alternate record key   is SLF-Clave11 = SLF-TipDoc, SLF-NroDoc                             with duplicates
                file status  is We-StFile.

Como se observa, el archivo está dotado de once claves, de las cuales solo una es sin duplicado (SLF-Clave03); esto es particularmente importante porque el árbol-B está compuesto, y COBOL ahora sí debe preocuparse por una clave única y otras diez sin inconvenientes en introducirlas en la página del índice que corresponda; necesariamente, deberá emplear más tiempo en ello.

Se efectuó el mismo test, o sea, sobre 500.000 registros, y el resultado fue el siguiente:

Grabación 500.000 registros s/B inicia:    19:36:25:04
Fin grabación s/B.....................:    19:58:37:50   22' 13"

Grabación 500.000 registros c/B inicia:    19:58:37:50
Fin grabación s/B.....................:    20:15:28:02   17'  9"

Hasta acá, el test varía muy poco, pues hay apenas 5' de diferencia a favor del archivo con FB. Veamos los tiempos de lectura:

Inicio lectura s/B....................:    20:15:28:02
Fin lectura s/B.......................:    20:16:06:53    0' 32"

Inicio lectura c/B....................:    20:16:06:53
Fin lectura c/B.......................:    20:16:36:58    0' 30"

Ahora veamos los tamaños de ambos archivos:

BlkStkLinfac    112,054 KB
StkLinfac       112,926 KB

Como puede comprobarse, tampoco es trascendente la diferencia, y estamos mencionando un archivo de 500.000 registros, un número importante para un test. Se podría incluir archivos de mayores extensiones, como 2 GB, límite en RM/COBOL bajo Windows (ver página 119 en el manual "RM/COBOL User's Guide" por más información), pero se puede suponer que, estableciendo una proporcionalidad, los valores no cambiarían demasiado.

En principio, y a menos que surja otro estudio semejante, como conclusión final, no veo necesario que se establezca un FB en los archivos indexados, puesto que las diferencias no son para nada dramáticas.

viernes, 22 de septiembre de 2017

EL AJEDREZ DEL DEEP BLUE DE IBM
CHIPS DE CLASE GRAN MAESTRO


Feng-hsiung Hsu
IBM T.J. Watson - Research Center

Daniel Márquez Lisboa
Documentalista y traductor





Este white paper es una traducción textual de ideas del Ingeniero Fen-hsiung Hsu.
La mención «Gran Maestro» se corresponde a la siguiente definición:

«El título de Gran Maestro es otorgado por la FIDE a jugadores de ajedrez que alcanzan determinado nivel de excelencia. Aparte del título de Campeón Mundial, es el título más importante entre los jugadores de ajedrez.» - Wikipedia

El supercomputador Deep Blue de IBM, que le ganó al campeón mundial de ajedrez Garry Kasparov en 1997, empleó 480 chips personalizados de ajedrez. Este artículo describe la filosofía de diseño, la arquitectura general y el desempeño de estos chips de ajedrez, los cuales proveyeron el máximo poder computacional a Deep Blue.


Crear la primera computadora de ajedrez campeona del mundo pertenece a los desafíos de las máquinas más antiguas en cuanto a desafíos en informática. Cuando el Campeón Mundial de Ajedrez Garry Kasparov abandonó en la última partida de un juego a seis contra el superordenador Deep Blue de IBM el 11 de mayo de 1997, su pérdida marcó un logro de este objetivo.

La búsqueda de una «máquina de ajedrez» data a 1769 cuando el Turk —con un jugador humano escondido dentro — debutó en la corte australiana. El arribo de computadores electrónicos a fines de 1940 espoleó nuevas investigaciones en programas de ajedrez. Los tempranos programas enfatizaban el proceso de pensamiento del ajedrez de un humano. El programa Chess 4.51 a fines de los 70s demostró por primera vez que enfatizando en el hardware, la velocidad podría ser más fructífera. Belle2, una máquina con cableado especial de ajedrez de  Bell Laboratories, vino a ser el primer programa nacional maestro en los inicios de 1980. Continuando la misma tendencia, Cray Blitz3 corría sobre un supercomputador Cray, y Hitech4, otra máquina de propósito en ajedrez, llegaba al tope de los programas en los mediados de 1980.

Durante los próximos 10 años, las máquinas de ajedrez se basabarían en un generador de movimiento con mi diseño5 —ChipTest (1986-1987), Deep Thougth (1988-1991), y Deep Thouth II (1992-1995)— lugares reclamados como los mejores programas de ajedrez en el mundo. En 1998, el equipo de Deep Thougth ganó el segundo Fredkin Intermediate Prize para el nivel Gran Maestro para un rating de 2650 de la escala de la USFC por sobre 25 juegos consecutivos.

El debut de Deep Blue en 1996, en el primer match Kasparov-Deep Blue en Filadelfia, finalmente eclipsó al Deep Thought II. La versión de 1996 de Deep Blue usó un nuevo chip de ajedrez diseñado en el IBM Research a lo largo de tres años. Una importante revisión de este chip participó en la histórica revancha de 1997 entre Kasparov y Deep Blue. Este artículo se concentra principalmente en el chip revisado.

Descripción de la tarea y filosofía del diseño

Los buenos programadores de ajedrez prestan mucha atención a la velocidad de sus programas. Inicialmente, también enfatizamos la velocidad de búsqueda. Uno de mis objetivos originales cuando diseñamos Deep Thought, era ver lo que sucedería cuando una máquina de ajedrez clase-Belle se aceleró, digamos, mil veces más.

Resolver el «problema del ajedrez informático» implicaba ganar un partido contra el Campeón Mundial de Ajedrez humano bajo el control del tiempo de regulación. Los juegos tuvieron que jugarse a menos de tres minutos por jugada. Ambas condiciones —utilizando el control del tiempo de regulación lenta y ganando un partido— presentaban problemas.

Bajo controles de tiempo más rápidos, es mucho más fácil para una computadora vencer a los GM de ajedrez. Un ordenador primero derrotó a un GM en 1977 en un juego blitz, donde los jugadores tienen cinco minutos cada uno para todo el juego. Tomó 11 años antes de que una computadora fuese finalmente GM en un juego de la regulación. Más recientemente, en 1988, el jugador número dos clasificado, Vishwanathan Anand, perdió contra un programa de PC en blitz y juegos de tiempo corto por una puntuación de 1,5 a 4,5. Sin embargo, derrotó al mismo programa por una puntuación de 1,5 a 0,5. Incluso los GM de clase mundial tienen problemas para evitar errores en juegos rápidos.

La necesidad de vencer al Campeón del Mundo en un partido, introdujo dificultades adicionales.

Dos ejemplos demuestran el obstáculo de una computadora en encuentros en un partido contra un equipo bien preparado con oponente humano. En 1984, Cray Blitz jugó un match de cuatro partidas contra el internacional Maestro David Levy. A pesar existir fuerzas comparables, Levy explotó con éxito las debilidades informáticas, típicas de Cray Blitz, y ganó con una puntuación de 4-0. En 1996, Deep Blue lo fue incluso contra Kasparov después de cuatro juegos en el primer match. Kasparov marcó profundamente a Deep Blue, y ganó los dos restantes juegos fácilmente. Aparentemente, la velocidad de cálculo no fue suficiente.

¿Qué fue lo que causó los problemas para Cray Blitz y Deep Blue en los partidos de 1984 y 1996? Primero, jugaron con oponentes humanos adaptables. Los humanos aprenden. Las computadoras también «aprenden»,  pero no muy bien. En segundo lugar, Cray Blitz en 1984 y, en un grado mucho menor, Deep Blue en 1996, tenían serias lagunas en su comprensión del conocimiento del ajedrez, que un oponente humano podía simplemente explotar.

¿Qué contramedidas ayudarían? Nuestro equipo podría poner tanto conocimiento de ajedrez como fuese posible en el chip de ajedrez y reducir el número de graves deficiencias de conocimientos. Podríamos también, lo más fácil posible, cambiar el comportamiento de juego de chip de ajedrez. Esto se fusionaría en un solo mandato: integrar la máxima cantidad posible de software de conocimiento de ajedrez modificable en el chip de ajedrez. El nivel de integración tenía que ser el primero; la velocidad sería el segundo.

Las computadoras de ajedrez que optimizan sus programadores, les dicen que optimicen. A veces, este imperativo conduce al programa a mostrar un comportamiento extraño no visto en humanos porque las computadoras de juegos no tienen sentido común. Para corregir el comportamiento extraño, tienen que incluir conocimientos de ajedrez no cubiertos en los libros de ajedrez.

Para hacer frente a la computadora con las anteriormente desconocidas debilidades que aparecen en un partido, nosotros creamos los pesos asociados con las posiciones características ajustables individualmente desde el software. Este enfoque tiene una ventaja que no necesitaba saber cómo jugar bien ajedrez solo si una función de posición es importante. Un escape de hardware hatch añadido permitió un circuito externo, como un FPGA (field-programmable gate array) para reconocer nuevas características posicionales y modificar operaciones de hardware en los chips de ajedrez. En el match de 1997, no usamos el escape de hardware, pero cambiamos los pesos para las características posicionales entre las partidas.

La velocidad, aunque secundaria, siguió siendo importante. Teóricamente, podríamos aumentar la velocidad del chip dramáticamente utilizando una mejor tecnología y ejecución especulativa. El riesgo involucrado con una aplicación más rápida parecía demasiado en el tiempo limitado que teníamos antes del match de 1997.

Los chips de ajedrez en CMOS de 0,6 micras buscaron de 2 a 2,5 millones de posiciones de ajedrez por segundo por chip. Análisis de diseño recientes mostraron que la aceleración a cerca de 30 millones de posiciones por segundo era posible con un procesador de 0,35 micras y un nuevo diseño. Tal chip podría hacer posible derrotar al Campeón del Mundo de Ajedrez con un ordenador personal de escritorio o, incluso, un ordenador portátil. Con un procesador de 0,18 micras y con, digamos, cuatro procesadores de ajedrez por chip, nosotros podríamos construir un chip de ajedrez con mayor velocidad de cálculo sostenida en el Deep Blue de 1997.

Debido a la arquitectura del sistema de Deep Blue, no tuvimos que tener chips de ajedrez lo más rápidos posibles. Basamos el sistema de Deep Blue en un superordenador IBM RS/6000 SP, que se puede ver como una colección de procesadores IBM o estaciones de trabajo RS/6000 conectados a través de una red de conmutación de alta velocidad. Cada procesador en el sistema controlaba hasta 16 chips de ajedrez, distribuidos en dos tarjetas Micro-Channel con 8 chips de ajedrez en cada tarjeta. Dado que el superordenador RS/6000 SP podría en teoría tener hasta miles de procesadores, es que no nos enfrentamos a ninguna limitación seria en cuanto a velocidad del sistema. El Deep Blue de 1997 fue una máquina de 30 vías con 30 procesadores RS/6000 (y 480 chips de ajedrez). Hay al menos una RS/6000 SP con más de 4.000 procesadores. Si estuviéramos dispuestos a gastar dinero, podríamos construir una máquina de ajedrez más de cien veces más rápido que el Deep Blue de 1997, sin recurrir a chips de ajedrez más rápidos.

Los chips de ajedrez proporcionaron un enorme poder. En una computadora de uso general, el cálculo realizado por el chip de ajedrez, para una sola posición, requiere de hasta 40.000 instrucciones generales. De 2 a 2,5 millones de posiciones de ajedrez por segundo, un chip de ajedrez opera como el equivalente a una construcción de 100 mil millones de dólares por segundo de superordenador. Dado que esta era la velocidad adecuada, no me gasté mucho en optimizarla.

Arquitectura general

La caja «dentro de una máquina de ajedrez» describe los principios operativos básicos de un programa de ajedrez. Lo siguiente es el Deep Blue específico.

Configuración del sistema

La versión de 1997 de Deep Blue incluía 480 chips de ajedrez. Ya que cada chip podría buscar de 2 a 2,5 millones de posiciones de ajedrez, la velocidad de «garantizar- no-excederse» del sistema alcanzó alrededor de mil millones de posiciones de ajedrez por segundo o 40-tera operaciones. Esto supone que, en promedio, cada posición de ajedrez necesita 40.000 instrucciones generales de proceso. La velocidad sostenida alcanzó los 200 millones de posiciones de ajedrez por segundo, o alrededor de 8 teraflops. Más trabajo de software podría acelerar el sistema por un factor de dos a cuatro, pero decidimos aplicar en su lugar al software en el conocimiento del ajedrez.

La búsqueda se realiza en paralelo en dos niveles: una distribuida sobre la red de conmutación IBM RS/6000 SP, y la otra en un bus micro-canal dentro de un nodo de estación de trabajo. Para, digamos, una búsqueda de 12 capas, uno de los nodos de la estación de trabajo —trabajando como el maestro para el sistema completo— buscaría en los primeros cuatro stacks en software. (Una capa representa un movimiento por el otro jugador). Después de cuatro pliegues de la posición del juego actual, el número de posiciones aumenta unas mil veces. Todos los 30 nodos de las estaciones de trabajo, incluido el nodo maestro, buscan estas nuevas posiciones en software para cuatro stacks más. El número de posiciones aumenta otras mil veces. En este punto, los chips de ajedrez saltan y terminan los últimos cuatro stacks de la búsqueda de la búsqueda, incluida la búsqueda por quiescencia.

Particionando la búsqueda en el software (de dos-niveles), la búsqueda de software y la búsqueda de hardware permiten una gran flexibilidad de diseño, aún manteniendo la velocidad de búsqueda. El software manejó menos del uno por ciento del total de posiciones, pero controló alrededor de dos tercios de la profundidad de búsqueda. La parte de búsqueda del software puede ser arbitrariamente selectiva, sin ralentizar el sistema.

Las 8 capas de búsqueda de software realizadas en el RS/6000 SP incluían muchas extensiones de búsqueda complicadas, que ampliaban la búsqueda a lo largo de las líneas que el ordenador consideraba forzadoras.

Algunas pruebas experimentales sugirieron que la fuerza de juego aumentaría significativamente si las extensiones de búsqueda llegaran hasta la búsqueda de quiescencia.

La implementación de las extensiones de búsqueda completa del software en el chip de ajedrez parecía una propuesta demasiado arriesgada, dada la limitación de tiempo de diseño. Durante el match de 1997, la búsqueda del software se extendió a alrededor de 40 capas a lo largo de las líneas de forzamiento, aunque la búsqueda no extendida alcanzó solo alrededor de 12 capas.

Descripción del chip

Cada chip de ajedrez funciona como una máquina de ajedrez de pleno derecho. Escribir un programa de ajedrez en silicio ofrece posibilidades de diseño no disponibles en un diseño basado en software. En particular, requirió reexaminar la complejidad del tiempo de los algoritmos. Un algoritmo inaceptable en un diseño de software podría funcionar perfectamente en hardware. El algoritmo podría ser trivialmente paralelizable en hardware sin la penalización de un área significativa, o el factor de escala de tiempo podría caer desde el tiempo de ciclo de instrucción a un retardo de compuerta simple.

Voy a explicar algunos ejemplos de estos algoritmos específicos de hardware a medida que se presenten.

El chip de ajedrez se divide en cuatro partes: el generador de movimiento, el stack inteligente, la función de evaluación, y el control de búsqueda. El stack de movimiento inteligente se divide además en otro stack de movimiento regular, y un detector de repetición. La Figura 1 muestra el diagrama de bloques del chip de ajedrez, junto con las conexiones entre los bloques. La foto del molde del chip de ajedrez aparece en la Figura 2.
(Continúa luego del siguiente apartado)


Dentro de una máquina de ajedrez

Los programas de ajedrez de hoy y las máquinas de ajedrez, siguen el diseño básico que Claude Shannon6 esbozó en 1949. El artículo de Slate y Atkin sobre Chess 4.51 dio un ejemplo clásico de los refinamientos desarrollados hasta finales de los setenta, y su artículo sigue siendo relevante hoy en día. Todos los autómatas modernos son clones de Chess 4.5 de una forma u otra.

El diseño básico de Shannon utiliza una búsqueda de minimax para decidir qué movimiento jugar. El diseño asume la existencia de una función de evaluación que asigna un valor numérico a una posición de ajedrez. Además, suponga que asigna este valor numérico desde el punto de vista del jugador de la computadora. La función de evaluación más simple puede devolver +1 si el equipo gana, 0 si la posición es un empate y -1 si el equipo pierde. Si tenemos suficiente potencia computacional, la función de evaluación simple {+1, 0, -1}, en combinación con la búsqueda minimax, basta para computar el mejor movimiento. Simplemente buscamos todos los movimientos posibles para ambos lados hasta llegar a posiciones con resultados conocidos.

Para una posición con el jugador de la computadora para jugar y con todos los resultados de las posiciones de los childs conocidos, el valor de la posición sería simplemente {valores máximos de posiciones de los childs}. Así que si una de las posiciones de los childs es una victoria (+1) para la computadora, la posición es también un triunfo (+1) para la computadora. Para una posición con el oponente de la computadora a jugar, el valor de la posición es min {valores de las posiciones de los childs}. Si una de las posiciones de los childs es una pérdida (-1) para la computadora, la posición es también una pérdida (-1) para el equipo, ya que el oponente escogería el mejor resultado. Mediante la copia de seguridad del valor de acuerdo con esta regla minimax, eventualmente se conocen los valores para todas las posiciones después de los posibles primeros movimientos del ordenador. La computadora simplemente jugará el movimiento que lleva al valor máximo de copia de seguridad, para efectivamente «resolver»el juego.

Shannon observó que, en realidad, el ajedrez era demasiado complicado para resolver de esta manera. Propuso limitar el número de movimientos desde la posición actual que el ordenador puede buscar, en lugar de buscar todo el camino hasta posiciones con resultados conocidos. Este límite podría depender del tiempo y la potencia computacional disponible. Con este límite artificial, la simple función de evaluación {+1, 0, -1} ya no funcionó, ya que las posiciones alcanzadas probablemente no tienen resultados conocidos. Shannon propuso usar una función de evaluación heurística: respaldar los valores heurísticos con las reglas minimax, luego elegir el movimiento basado en los valores heurísticos minimaxed. La función de evaluación heurística para una posición podría basarse en una estimación de la probabilidad de ganar, dibujar o perder el juego desde esa posición. Los programas de ajedrez usualmente basan la función de evaluación aproximadamente en cuánto delante o detrás de la computadora se ha conseguido en unidades de peones o centésimas de un peón.

El esquema básico de Shannon se divide naturalmente en tres componentes. Son el generador de movimiento que genera los movimientos de ajedrez y permite que la búsqueda avance en el tiempo, la función de evaluación que calcula los valores de las posiciones futuras y el control de búsqueda que retrocede en el tiempo y respalda los valores futuros a la posición actual. El chip de ajedrez Deep Blue agregó un stack de movimientos inteligentes para detectar cuando se repite la posición de ajedrez.

Gracias a Chess 4.5, se habían producido varios desarrollos importantes. Dos demostraron ser particularmente importantes en el diseño de un generador de movimiento de ajedrez de hardware: la búsqueda de quietud, y el algoritmo de poda alfa-beta.

También llamada búsqueda de captura en su forma más simple, la búsqueda de quietud extiende la búsqueda más allá del límite original establecido por el esquema de Shannon. Para una búsqueda de captura, el lado a mover obtiene la opción de hacer movimientos de captura para ganar material, así como simplemente aceptar la posición como es. Si el lado móvil selecciona la opción de captura, el oponente tiene la opción de hacer sus propias capturas, así como la aceptación de la nueva posición como es. La búsqueda de captura (Figura A) puede continuar durante muchos movimientos hasta que un lado se queda sin capturas o hasta que un lado decide tomar la posición tal cual.

                                            Figura A. La búsqueda de captura se realiza más allá de la profundidad de búsqueda 
                                           normal, hasta que un lado se queda sin capturas o un lado decide aceptar la posición.

Además de capturar movimientos, la búsqueda de quiescencia más general puede incluir otros tipos de movimientos de forzamiento, digamos, comprobando movimientos.

La búsqueda de quiescencia tiene un gran impacto en el rendimiento de un programa de ajedrez. Una medición7 temprana mostró que un programa con búsqueda de quiescencia coincidía con un programa sin búsqueda de quietud, pero buscando cuatro capas (dos movimientos cada una para blanco y negro) más profundas. La búsqueda de quiescencia generalmente aumenta el número de posiciones buscadas a la misma profundidad sólo de dos a cuatro veces. Cuatro pliegues más de la búsqueda, por otra parte, aumentan generalmente el número de posiciones por hasta mil veces. No es de extrañar que todos los programas modernos de ajedrez usen algún tipo de búsqueda de quiescencia.

Un programa con búsqueda de quiescencia generalmente gasta al menos la mitad de su tiempo de cálculo allí. Por lo tanto, la velocidad de cálculo para la búsqueda de quiescencia resulta fundamental para los ordenadores de ajedrez de alto rendimiento. Todos los generadores de movimiento de ajedrez de hardware exitosos pueden generar al menos los movimientos de captura rápidamente. Los chips de ajedrez de Deep Blue también pueden generar otros movimientos de forzamiento.

El algoritmo de poda alfa-beta apareció varios años después de la propuesta de Shannon. En realidad, los jugadores humanos han utilizado el algoritmo alfa-beta o sus variantes implícitamente para las edades.

El algoritmo alfa-beta se basa en la observación de que realmente no necesitamos mirar todas las respuestas de un oponente a nuestros malos movimientos, solo necesitamos una refutación. Si el mal movimiento pone en peligro a la Reina, solo necesitamos saber que nuestro oponente puede capturar a la Reina en el siguiente movimiento. Sin embargo, para determinar una refutación válida, debemos examinar todas nuestras respuestas a ella. En el ejemplo de la reina colgada, tendríamos que examinar todas nuestras respuestas a la captura de la Reina para asegurarnos de que nuestro oponente realmente gane a la Reina sin una penalización adecuada.

El mismo principio de refutación se aplica a los movimientos negativos del oponente, que también sólo necesitan una refutación cada uno. Esta idea de refutaciones  conduce a un árbol de búsqueda óptimo (ver Figura B).

                                                                               Figura B. Árbol de búsqueda óptimo.

El árbol de búsqueda crece de arriba abajo y de izquierda a derecha. Un árbol de búsqueda óptimo ordena los movimientos mejor-primero, por lo que el primer movimiento buscado para una posición dada es también el mejor movimiento o al menos un movimiento de refutación para esa posición. En la figura, la rama más a la izquierda del árbol de búsqueda también representa la variación principal -la línea hipotética donde ambos lados juegan los mejores movimientos-. Por lo tanto, debemos examinar todas las respuestas a ellos, no hay refutación a un mejor movimiento. Por otra parte, todos los movimientos del hermano a un movimiento de la variación principal son inferiores y tienen por lo menos una refutación que debemos examinar.

Una línea de refutación muestra el patrón repetido de un nivel de árbol con una refutación seguida de un nivel de árbol de todas las respuestas. Este es el patrón de crecimiento característico de un árbol de búsqueda alfa-beta. El algoritmo permite que una búsqueda del programa de ajedrez baje aproximadamente el doble de la profundidad alcanzable con una búsqueda de minimax cuando el orden de movimiento está cerca de la primera ordenada.

Para un programa que busca cerca de 40 mil millones de posiciones para cada movimiento -como lo hizo el Deep Blue de 1997- el algoritmo alfa-beta aumenta la velocidad de búsqueda en hasta 40 mil millones de veces. Esta aceleración, sin embargo, depende fuertemente de la calidad del pedido de movimiento. En orden de peor-movimiento inicial, el algoritmo alfa-beta busca un árbol del mismo tamaño que el árbol de búsqueda minimax. Obviamente, el generador de movimiento de hardware tendría que proporcionar una aproximación decente de la primera orden en cualquier sistema de juego de alto rendimiento de ajedrez.

Otro desarrollo que no se suele citar, pero, según mi leal saber y entender, descrito por Slate y Atkin, 1 fue una evaluación perezosa. Chess 4.5 evitó calcular toda la función de evaluación cuando el balance de material se desvió demasiado del valor esperado. Por ejemplo, si alguna de las partes ha perdido a una Reina mientras esperamos que la posición sea pareja, claramente no hay razón para una evaluación completa. La función de evaluación normal, al menos en el caso de Chess 4.5, no podría llevar la función de evaluación a un punto cercano al par.

Los chips de ajedrez de Deep Blue usan un esquema de evaluación perezoso más elaborado, que desactiva esta evaluación perezosa cuando ocurre una posición inusual. En particular, si el número de piezas en el tablero cae demasiado bajo, a veces se podría sacar una posición incluso con un lado encima de una pieza completa. Una búsqueda profunda de la fuerza bruta tiene un alto porcentaje de posiciones de hoja fuera de balance como una consecuencia directa de buscar todos los movimientos, que naturalmente incluyen algunos movimientos escandalosamente malos de cualquier lado. Típicamente, para una búsqueda de la fuerza bruta de 12 capas, el 60% al 90% de las posiciones están apagadas cuando hay más de un peón. La evaluación perezosa puede así ser bastante efectiva.

A la izquierda en la Figura C hay un árbol para una búsqueda de tres capas desde la posición de apertura. Después de tres capas, la búsqueda alcanza una posición de hoja, y entra en la región de búsqueda de quietud. Algunos programas de ajedrez restringen la búsqueda de quietud a los movimientos de captura solamente. Deep Blue incluye comprobar los movimientos, y comprobar los movimientos de evasión en su búsqueda de quietud bajo ciertas condiciones. Esto significó agregar circuitos especiales para generar tales movimientos rápidamente

                                                           Figura C. Algoritmo de búsqueda básico de un chip de ajedrez: 
                                                      árbol de búsqueda (izquierda), diagrama de flujo (derecha).

El diagrama de flujo en el lado derecho de la Figura C da una vista simplificada del procesamiento realizado para cada posición de ajedrez buscada. Entrando en una posición de ajedrez después de hacer un movimiento, la máquina de ajedrez procesa dos caminos paralelos: generación de movimiento y evaluación de decisión.

El camino de la izquierda -el camino de la generación del movimiento- comprueba primero la legalidad del movimiento más reciente del oponente comprobando si podemos capturar al Rey del oponente. Si es así, el último movimiento que el oponente hizo es ilegal, y debemos salir de la posición y volver a la posición de padre. Si el último movimiento es legal, comenzamos el proceso de generación de movimiento. Si no podemos encontrar un movimiento (no existen movimientos legales o, en el caso de búsqueda de quietud, no existen movimientos de forzamiento adecuados), regresamos a la posición de padre, posiblemente con cualquier puntuación que proporcione la función de evaluación. Si tenemos un movimiento, y la función de evaluación dice que no podemos salir todavía, continuamos la búsqueda al siguiente nivel.

El camino correcto maneja las decisiones de evaluación. Al entrar en la posición, primero verificamos si se trata de una posición de hoja (generalmente comprobando si hemos alcanzado suficiente profundidad de búsqueda). Si no, no necesitamos hacer la función de evaluación, y nos fusionamos con la ruta de generación de movimiento. Si hemos alcanzado una posición de la hoja, hacemos una evaluación rápida, lo que da una estimación rápida y sucia de la puntuación de posición. Si nos gusta esta estimación, la tomamos y salimos de la posición (con una terminación temprana de la ruta de generación de movimiento). Si esta estimación se ve muy mal para nosotros, nos fusionamos con el camino de generación de movimiento, con la esperanza de encontrar algún movimiento forzoso que gane algo para nosotros. Si esta estimación no parece ni buena ni mala, calculamos la evaluación lenta para encontrar la evaluación completa de la posición. Si la evaluación completa nos satisface, podemos cortar la búsqueda y volver a la posición de padre. De lo contrario, si el generador de movimiento dice que existe un movimiento forzoso adecuado que podría ganar algo para nosotros, buscamos hacia adelante.

(Continúa)
El tiempo de ciclo del chip está entre 40 y 50 nanosegundos en un límite de manejo de potencia de tres micrones de 0,6 micras del micro canal para una placa de ocho chips. El chip incluye aproximadamente 1,5 millones de transistores, y el dado mide 1,4 cm '1,4 cm.

                                                                               
                                       Figura 1. Diagrama de bloques del chip de ajedrez.

                                                          Figura 2. Foto del chip de ajedrez.

Generador de movimientos

El generador de movimiento, una matriz 8x8 de lógica combinacional, aparece en la foto de matriz como el bloque en la parte superior derecha. Una máquina finitistate cableada controla la generación de movimiento. El generador de movimiento es más complicado que el generador de movimiento utilizado en Deep Thought,5,8, 9 que no puede generar la comprobación o el control de la evasión se mueve directamente. El nuevo generador de movimiento puede generar captura, comprobación y comprobación de movimientos de evasión directamente. El generador de movimiento utilizado en los chips de ajedrez para el Deep Blue de 1997 también podría generar movimientos de ataque. Esta adición de 1997 apoya la poda del hardware de movimientos irrelevantes del ajedrez en las últimas capas de posiciones inmediatamente antes de la búsqueda de la quiescencia. El algoritmo básico de generación de movimiento es el mismo que en el generador de movimiento de la Belle10.

La matriz lógica combinatoria es efectivamente un tablero de ajedrez de silicio. Cada célula de la matriz tiene cuatro componentes principales: un transmisor de detección de víctimas, un transmisor de detección de atacantes, un receptor y un árbitro distribuido. Cada celda contiene un registro de piezas de cuatro bits que registra el tipo y el color de la pieza en el cuadrado correspondiente del tablero de ajedrez.

                                        Figura 3. El transmisor hallazgo-víctima. WTM: blanco para 
                                 moverse, OP: operación, DIR mux: dirección multiplexor.

Cuando está activado, el transmisor de víctima de búsqueda (ver Figura 3) irradia señales de ataque apropiadas para la pieza residente. Si el cuadrado está vacante, las señales de ataque entrantes de una pieza de ataque en forma de rayo (un Alfil, una Torre, o una Reina) pasan a través de la celda. Los cuadrados de tercer nivel tienen circuitos adicionales para manejar los movimientos de Peón de dos cuadrados. Al comienzo de una secuencia típica de generación de movimiento, se ejecuta un ciclo de búsqueda-víctima, y todas las piezas del lado móvil irradian señales de ataque.

Las señales de ataque radiadas llegan entonces al receptor en la Figura 4, y se realiza una votación para encontrar a la víctima más valorada. Aunque el receptor tiene varias operaciones, por ahora, asumen que determina si alguna pieza de color opuesto ataca la pieza residente. En caso afirmativo, el receptor establece una señal de prioridad basada en el tipo de pieza. Puesto que queremos encontrar víctimas, la prioridad se eleva para las piezas de mayor valor, con la Reina como más alta, luego la Torre, el Alfil, el Caballo, el Peón y la casilla vacía, en orden descendente. El Rey no puede convertirse en una víctima, ya que entonces la posición es ilegal.

Las señales de prioridad de todos los escaques van luego al árbitro distribuido, o a la red de arbitraje de la Figura 4, para encontrar la víctima de mayor valor a capturar. Para las víctimas con la misma prioridad de pieza, la prioridad cuadrada adicional rompe el empate.

Los receptores de todas las casillas detectan entonces si una señal de ataque inverso entrante coincide con el tipo de pieza residente. Si la pieza residente es un atacante apropiado, el sistema establece una señal de prioridad. Puesto que queremos utilizar primero al atacante con el valor más bajo, la prioridad toma orden inverso, con el peón teniendo la prioridad más alta. Las señales de prioridad pasan a través de la red de arbitraje y, con la víctima y el atacante computados, tenemos el movimiento.

Usted puede haber notado que el generador de movimiento, como se describe, calcula todos los movimientos implícitamente, a pesar de que genera solo un movimiento. En software, consideraríamos esto inaceptable. Una implementación de hardware calcula todos los movimientos en paralelo y no incurre en ninguna penalización de tiempo.

                                           Figura 4. El receptor.

Esta discusión se sostiene para el primer movimiento generado de una nueva posición. Generar los otros movimientos desde una posición parcialmente buscada requiere enmascarar los movimientos buscados.

En el anterior diseño de Belle, un stack de desactivación de 2 bits enmascara las casillas ya buscadas. Un bit del stack de la inhabilitación enmascara las casillas del atacante buscado para una víctima dada. El otro bit enmascara a las víctimas de la búsqueda en forma completa. Esta parte del diseño de Belle se basa en una traducción directa de una implementación de software, donde el enmascaramiento de bits resulta eficiente. Un diseño basado en VLSI, sin embargo, ofrece una nueva alternativa. En los generadores de movimiento de ajedrez de Deep Think y de Deep Blue, el último movimiento buscado desde la posición se utiliza para calcular la máscara de desactivación de dos bits. El último movimiento buscado nos dice los niveles de prioridad de la última pieza víctima y de la última pieza atacante. Podemos usar un decodificador modificado para enmascarar casillas con el mismo tipo de pieza residente, pero con menor prioridad. En el software, el costo de recalcular la máscara excede el costo de recuperarla. Pero en hardware, lo contrario es cierto. El stack de desactivación necesita decodificadores para funcionar de todos modos. El decodificador modificado funciona a una velocidad comparable a la de los decodificadores de stack deshabilitado, y ocupa menos espacio. Este método evita el uso de stack deshabilitado, que probablemente necesite tener al menos 64 niveles de profundidad.

                              Figura 5. El transmisor de encontrar-atacante.
                                  
El generador de movimiento de Deep Blue soporta otros modos de generación de movimiento. Al generar los movimientos de control, activa todos los transmisores de hallar-víctima, así como el transmisor del hallar-atacante del rey contrario. Cuando ambos conjuntos de señales coinciden en la misma casilla, tenemos una casilla en la cual hay una pieza que puede chequear al Rey. Cuando las señales de rayos se alinean correctamente en un cuadrado con una pieza que pertenece al lado móvil, la pieza puede dar controles descubiertos cuando se mueve. Un modo especial de generación de movimiento genera movimientos de evasión de cheques. Otro modo genera movimientos utilizados en la poda de movimiento del hardware.

                                                    Figura 6. Evaluación rápida.

Este último modo costaría demasiado en una implementación de software pura. El generador de movimiento también detecta piezas colgadas y mide la fuerza de los jaques. Podemos habilitar extensiones de búsqueda de hardware simples en el primer nivel de búsqueda de quietud, y las utilizamos en la versión de Deep Blue de 1997. El generador de movimiento tiene alrededor de 52.400 puertas.

                                     Figura 7. Tabla de colocación de piezas. Attk = atacante

Función de evaluación

La función de evaluación completa contiene alrededor de 66.000 puertas, sin incluir las RAM y las ROM. En la foto de la figura 2, todos los sub-bloques a la derecha del generador de movimiento pertenecen a la función de evaluación. Los sub-bloques inferiores proporcionan una evaluación rápida. Los sub-bloques superiores, la matriz de evaluación sistólica, las RAM de evaluación alineada y la lógica de posvaluación en fila, calculan una evaluación lenta.

La evaluación rápida, que calcula en un solo ciclo, contiene todos los términos de evaluación importantes fácilmente calculados con valores altos. La evaluación lenta escanea el tablero de ajedrez de una columna (archivo) a la vez sistólica. La evaluación lenta tiene una latencia de tres ciclos por columna y toma once ciclos para computar, dadas las ocho columnas del tablero de ajedrez. La partición de la función de evaluación en una evaluación rápida y lenta resultó necesaria para adaptar el diseño a un solo chip. Afortunadamente, rara vez se necesita una evaluación lenta.

La evaluación rápida contiene cuatro partes, como se muestra en la Figura 6: la tabla de colocación de piezas, la matriz de Rey y Peón, la lógica de fin de juego, las ROM, y el control de fase de juego. La tabla de colocación de piezas calcula la evaluación incremental de una posición basada en los valores promedio de las piezas en sus casillas residentes. La tabla de colocación de piezas usa realmente tres RAM, como se muestra en la Figura 7. El bloque de control de fase de juego contiene un registro de recuento de piezas que cuenta el número de piezas de cada tipo que queda en el tablero para cada jugador. Para cada tipo de pieza, el sistema también mantiene un registro XORed de ubicación de piezas. El registro de posición de pieza contiene la ubicación exacta de una pieza de un tipo particular si solo queda una pieza del tipo correcto. El registro de recuento de piezas controla las RAM de control de fase de juego.

Las RAM de control de fase de juego producen varios valores de control. Uno de los valores de control es simplemente un bono o penalización, que se agregará a la evaluación basada en el material que queda en el tablero. Las combinaciones de piezas buenas obtienen un ligero incremento en la evaluación. Los otros valores de control son multiplicadores dependientes de la fase de juego para otros pesos de evaluación. El valor de control de fase de juego más importante, la relevancia seguridad-del-Rey, le dice al chip de ajedrez la importancia de la seguridad del Rey. Otro valor de control de fase de juego indica al chip de ajedrez cómo ajustar la penalización para la estructura de peón mala y la bonificación para los peones pasados.

La matriz de Rey y Peón detecta principalmente la condición de «peón-puede-correr», donde el Rey ya no puede ponerse al día con el peón pasado del oponente. Esto significa que el Peón pasado efectivamente se convierte en una Reina si no queda otra pieza, suponiendo que ningún otro Peón puede ganar la carrera de peones. La matriz de Rey y Peón reconoce otras características de fin de juego, incluyendo algunas condiciones especiales de Torre-versus-peones-pasados, y la presencia de peones pasados ampliamente separados que pueden adelantarse al Rey.
La lógica de fin-de-juego y el bloque de ROMs reconocen principalmente las condiciones inusuales de fin-de-juego que conducen a las terminaciones en empates. Este bloque contiene lógica aleatoria para detectar ciertas terminaciones simples que son muy probables. Este bloque también reconoce algunos dibujos simples de la fortaleza. La Figura 8 muestra la interfaz ROM de fin de juego para las cuatro ROMs de final de juego. El ROM más grande es el Rey-y-Peón contra el ROM del Rey, que dice si la posición representa una victoria para el lado del Peón.

                                        Figura 8. ROM de la interface fin-de-juego.

La evaluación lenta constituye el elemento más complicado en el chip, ocupando cerca de la mitad de su núcleo. A profundidades muy poco profundas, aproximadamente la mitad de las posiciones buscadas requieren una evaluación lenta, pero a profundidades de búsqueda realistas, el porcentaje cae a alrededor del 15 por ciento. Como se muestra en la Figura 9, la evaluación lenta tiene una tubería de tres etapas, comenzando con una matriz sistólica de 8x1 que se ejecuta durante ocho ciclos, un ciclo por archivo. A continuación se encuentran las RAMs síncronas de 40 más, seguidas de un árbol de adición que acumula los resultados. El controlador puede detener la secuencia de evaluación lenta sobre la marcha para reducir el consumo de energía.

       Figura 9. El flujo principal de evaluación lenta.

La evaluación lenta calcula los valores para los conceptos del ajedrez, tales como control de casilla, clavadas, rayos X, seguridad del Rey, estructura de empeño, peones pasados, control de rayos, puestos avanzados, Peón mayoritario, Torre en la 7ma línea, bloqueo, restricción, desarrollo, y así sucesivamente. Esta función de evaluación del ajedrez probablemente es más complicada que cualquier cosa descrita en la literatura de ajedrez de computadoras. Por ejemplo, mire la evaluación de seguridad del Rey: antes del castillo del Rey (la estructura de piezas defensivas a su alrededor), el sistema calcula tres evaluaciones de seguridad para este: una para el enroque del lado del Rey, otra para el enroque del lado de la reina, y el valor base para permanecer en el centro. Cada una de estas evaluaciones de seguridad del Rey toman en cuenta los tipos de piezas que atacan, la solidez del refugio del Rey, la presencia de peones atacantes, el complejo de colores a su alrededor, la casilla, el control de rayos alrededor del Rey, etc. La evaluación de seguridad final del monarca es una combinación lineal ponderada de las tres evaluaciones de su seguridad. Los pesos utilizados en la combinación lineal se basan en lo fácil que es evaluar el castillo, así como la clasificación de seguridad relativa de los tres destinos para el Rey.

El stack de movimiento inteligente

Es stack de movimientos inteligentes no existe en la versión anterior del chip de ajedrez. El chip antiguo contiene un stack de movimiento regular, pero no el detector de repetición. El detector de repetición contiene un amortiguador circular de 32 entradas de las últimas 32 capas de movimientos. Usando un algoritmo de memoria de hardware de dirección de contenido 8, el detector de repetición mantiene el número de piezas desplazadas en cada una de las últimas 32 posiciones con respecto a la posición actual del tablero. Cuando el número de piezas desplazadas es igual a cero, tenemos una posición repetida.

El detector de repetición detecta realmente más que una simple repetición. Si hay solo una pieza desplazada, también detecta si hay un movimiento que podría llevar a la repetición, o cerca de la repetición. Si el movimiento es legal, el equipo al que lo toca mover puede al menos reclamar un empate.

El detector de repetición implementado tiene una complejidad temporal de O (n), cuando n es la profundidad del buffer circular de repetición. El software por lo general implementa la detección de repetición probando una tabla hash, lo que da una complejidad de tiempo de O(1). La gran diferencia aquí es que la constante de tiempo para el detector de repetición de hardware es igual al retardo de puerta en lugar del tiempo de ciclo de instrucción. Además, los detectores normales de repetición de software no pueden decirnos que una posición está a punto de repetirse. El detector de repetición utiliza cerca de 20.000 puertas.

Control de búsqueda

El control de búsqueda no implementa realmente el algoritmo regular de búsqueda alfa-beta.11 En su lugar, implementa una búsqueda de alfa-beta del algoritmo de ventana mínima.12 Esto elimina la necesidad de un stack de valores. Una búsqueda alfa-beta regular mantiene dos variables temporales, a y b, en un stack de valores. La búsqueda de ventana mínima, relativamente nueva, solo puede decirnos si la posición buscada es mejor o peor que un valor de prueba único. En la búsqueda normal de alfa-beta, para los movimientos no es lo mejor, solo necesitamos saber si son mejores o peores (refutados entonces) que el mejor movimiento actual, precisamente la misma función proporcionada por la búsqueda mínima de ventanas. Por supuesto, cuando el nuevo movimiento es mejor que el mejor movimiento actual, es posible que tengamos que investigar el nuevo movimiento. Podemos usar una búsqueda de alfa-beta regular o repetir la búsqueda de ventana mínima varias veces, elevando el valor de la prueba ligeramente cada vez. La búsqueda basada en la eficiencia, basada en ventanas mínimas, parece ser aproximadamente la misma que la búsqueda normal de alfa-beta.

El control de búsqueda contiene una ruta de datos de 16 bits y tres máquinas de estado que controlan secciones de la ruta de datos. Dos de las máquinas de estado también controlan indirectamente el generador de movimiento. La ruta de datos utiliza múltiples sumadores / sustractores en cascada para calcular los indicadores condicionales que el algoritmo de búsqueda necesita en tan pocos ciclos como sea posible.

Una función de control de búsqueda inusual, un filtro digital de paso bajo, estima la función de evaluación lenta. La última evaluación lenta observada sirve como entrada al filtro de paso bajo. Este filtro nos da el componente de baja frecuencia de la función de evaluación lenta a medida que avanza la búsqueda. Puesto que la función de evaluación lenta no cambia drásticamente para posiciones estrechamente relacionadas, su componente de baja frecuencia ofrece una estimación decente. Sin esta estimación, tendríamos que ampliar la ventana utilizada para determinar si se debe calcular la función de evaluación lenta. En consecuencia, la velocidad de búsqueda sufriría.

A nivel de sistema, el chip aparece como un dispositivo de 2 bits con un espacio de direcciones de 17 bits. Escribir en algunas de las direcciones inicia una búsqueda desde la posición actual en el chip, generalmente para cuatro o cinco capas más allá de la profundidad de búsqueda del software. Esto libera el procesador host para realizar las tareas domésticas o iniciar una búsqueda en otro chip.

Desempeño

Hemos utilizado los chips de ajedrez en varias configuraciones del sistema, desde un solo chip hasta múltiples chips que se ejecutan en una sola estación de trabajo (Deep Blue Jr.) y finalmente en Deep Blue. Los juegos más tempranos, a principios de 1997, usaron un único chip que funcionaba a una velocidad de reloj del 70% y una eficiencia de una décima a la quinta como resultado de un error de hardware. Esto redujo el chip de 7% a 14% de su velocidad regular, o aproximadamente la misma velocidad de búsqueda que el programa de ajedrez comercial más rápido en un PC Pentium Pro 180 MHz. Dos de los principales programas comerciales, que se ejecutan en el Pentium Pro PC, sirvieron como oponentes en las primeras sesiones de depuración de fichas. De los diez juegos jugados, el programa de un solo chip los ganó todos. Esto da alrededor de un nivel de confianza del 95% que un solo chip, incluso a velocidad reducida, era por lo menos 200 puntos más fuerte que los programas de ajedrez comerciales en juegos de máquina contra máquina.

Jugamos otros treinta juegos con la versión single-chip o Deep Blue Jr. contra los programas comerciales de ajedrez. De los cuarenta juegos totales, el chip de ajedrez perdió dos puntos y anotó el 95 por ciento contra los programas de PC. Esto sitúa el rendimiento de 300 a 500 puntos de clasificación por encima de los programas de PC, dependiendo de la fórmula de clasificación utilizada. Esta calificación no tiene nada que ver con la fuerza de juego real, ya que el examen superficial mostró serias debilidades de posición en los programas comerciales que los sistemas de chess-chip explotaron repetidamente.

Los juegos más interesantes enfrentaron a Deep Blue Jr. contra los Grandes Maestros que trabajaban en el proyecto. Las calificaciones promedio de los estos Grandes Maestros estaban en los 2500, altos puntajes en la escala internacional. Deep Blue Jr. anotó mejor que una relación de tres a uno contra ellos, lo que lo situó en más de 2700, o entre los diez mejores jugadores en el mundo.

La versión de 1997 de Deep Blue sólo jugó seis partidos, todos contra Kasparov. Deep Blue ganó el partido por la puntuación de 3,5 a 2,5. Kasparov estaba clasificado alrededor de 2815, lo que colocó el rendimiento de Deep Blue en alrededor de 2875. Sin embargo, no pudimos tomar esta clasificación demasiado en serio debido a la pequeña muestra de tamaño.
. . .

Estoy formando una start-up independiente para crear un nuevo chip de ajedrez para los consumidores. Este nuevo chip podría hacer posible que una máquina de escritorio derrotara al Campeón del Mundo en un partido formal ya en el año 2000. Más adelante, las habilidades usadas para crear a Deep Blue podrían ser usadas para conquistar otros juegos. Uno de los principales candidatos es el juego japonés de shogi, que tiene mayor complejidad computacional, pero también características similares. El difícil juego de Go, o Wei-chi, sin embargo, podría estar aún más allá del alcance de una computadora en un futuro próximo.

Agradecimientos

Doy las gracias a Murray S. Campbell y Arthur J. Hoane por su ayuda en la ejecución de la simulación de chips. El gran maestro Joel Benjamin proporcionó información útil sobre las maneras de mejorar la función de evaluación del chip de ajedrez.

Feng-hsiung Hsu es investigador en el IBM T.J. Watson Research Center. Sus actuales intereses técnicos incluyen sistemas paralelos, arquitecturas de propósito especial, circuitos VLSI, sistemas reprogramables, algoritmos de hardware, shogi de computadora y «cosas más simples que una máquina de ajedrez». Hsu recibió su doctorado en ciencias de la computación de la Carnegie Mellon University en 1989 y su licenciatura en ingeniería eléctrica de la Universidad Nacional de Taiwán en 1980.

Los lectores pueden ponerse en contacto con Hsu en IBM T.J. Watson Research Centre, MS 27: 233, PO Box 218, Yorktown Heights, NY 10598; e-mail fhh@watson.ibm.com, o en fhh@cs.cmu.edu.

Referencias

1.
D.J. Slate and L.R. Atkin, “Chess 4.5–the Northwestern University Chess Program,” Chess Skill in Man and Machine, P.W. Frey, ed., Springer-Verlag, 1977, pp. 82–118.

7.
J.J. Gillogly, Performance Analysis of the Technology Chess Program, PhD thesis, Carnegie Mellon Univ., 1978.
2.
J.H. Gondon and Ken Thompson Belle, Chess Skill in Man and Machine, 2nd. ed., P.W. Frey, ed., Springer-Verlag, 1983, pp. 201–210.
8.
F.-h. Hsu, Large-Scale Parallelization of Alpha-Beta Search: An Algorithmic and Architectural Study, PhD thesis, Carnegie Mellon Univ., Computer Science Dept., Feb. 1990.

3.
R.M. Hyatt, “Parallel Chess on the Cray xmp/48,” Int’l Computer Chess Assoc. J., 1985, pp. 90–99.
9.
F. Hsu et al., “Deep Thought,” Computers, Chess, and Cognition, T.A. Marsland and J.Schaeffer, eds., Springer-Verlag, 1990, pp. 55–78.

4.
C. Ebeling, All the Right Moves: A VLSI Architecture for Chess, PhD thesis, Carnegie Mellon Univ., Computer Sci. Dept., Pittsburgh, Apr. 1986.

10.
J.H. Condon and K. Thompson, “Belle Chess
Hardware,” Advances in Computer Chess 3, Pergamon Press, Oxford, England, 1982, pp. 45–54.
5.
F.-h. Hsu, “A Two Million Moves/sec CMOS Single-Chip Chess Move Generator,” 1987 ISSCC Digest Technical Papers, Feb. 1987, p. 278.

11.
D.E. Knuth and R.W. Moore, “An Analysis of Alpha-Beta Pruning,” Artificial Intelligence,
Vol. 6, 1975, pp. 293–326.
6.
C.E. Shannon, “Programming a Computer for Playing Chess,” Philosophical Magazine, Vol. 41, 1950, pp. 256–275.
12.
J. Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, Reading, Mass., 1984.


FIN DEL DOCUMENTO ORIGINAL


Notas del documentalista

A continuación, una serie de reseñas acerca de la serie de super computadoras modelos «Deep» de IBM, sus creadores y su equipo.

Nota biográfica

Feng-Hsiung Hsu es un científico informático y el autor del libro Detrás de Deep Blue: Construyendo la computadora que derrotó al campeón del ajedrez del mundo. Su trabajo condujo a la creación de la computadora del ajedrez del pensamiento profundo, que condujo al primer juego de ajedrez que jugaba el ordenador para derrotar a los Grandmasters en juego del torneo y el primer alcanzar una calificación certificada del nivel de Grandmaster.

Hsu fue el arquitecto y el diseñador principal de la computadora de ajedrez Deep Blue de IBM. Recibió el Premio Mephisto de 1990 por su tesis doctoral y también el Premio Grace Murray Hopper de ACM de 1991 por sus contribuciones en arquitectura y algoritmos para máquinas de ajedrez.

El equipo

·         Deep Blue. Dos torres de aluminio azul oscuro de 1,96 metros de alto, 0,8 de ancho, 1,0 de profundidad, y 0,7 toneladas de peso cada una, vencieron al Campeón del Mundo, creadas y dirigidas por este equipo.

·         Feng-Hsiung Hsu. Creativo de hardware que es considerado en Estados Unidos por una suerte de gurú del ramo. A mediados de 1999 abandonó IBM y le compró los derechos del chip de ajedrez.

·         Murray Campbell. Se ocupaba de los aspectos críticos de la función numérica, es decir, de asignar valores numéricos a factores tales como la estructura de peones o la movilidad circunstancial de las piezas, con base en los cuales DB hace una evaluación general de la posición.

·         Joe Hoane. Especialista en multiprocesadores, era el encargado de optimizar y sincronizar el trabajo de los 256 procesadores.

·         Jerry Brody. Vivía en el laboratorio, y responde por los problemas cotidianos que se presentasen en el hardware. Era el médico de cabecera de Deep Blue.

·         Chung-Jen Tan. Experto en el diseño de máquinas para sistemas paralelos altamente escalares y jefe del equipo.

·         Joel Benjamin. Como ninguno de los anteriores es un jugador aceptable de ajedrez, contrataron al Gran Maestro FIDE Joel Benjamin, joven ajedrecista neoyorquino, que hizo las veces de sparring de Deep Blue, señalando sus falencias y colaborando en el difícil asunto de la evaluación de las posiciones. En la única partida que jugaron en un torneo en el pasado, Benjamin y Kasparov hicieron tablas.



El equipo responsable de Deep Blue posa en mayo de 1997. Desde la izquierda: Chung-Jen Tan, Jerry Brody, Joel Benjamin, Murray Campbell, Joseph Hoane y Fen-hsiung Hsu (sentado). No se conoce si la foto es anterior o posterior al match, pero esa es la sala donde se efectuó el encuentro.



La humanidad en problemas. La investigación realizada el documentalista en 2007 acerca del match de mayo de 1997. Fue publicada por NetGate Magazine en tres volúmenes consecutivos con una tirada de cinco mil ejemplares.

Game over: Kasparov and the machine. Fue la película en tono dramático que inspiró al documentalista de este documento (quien siguió al match en vivo) a iniciar la investigación del caso. No se pudo comprobar hasta ahora, pero puede suponerse que existieron maniobras oscuras de IBM que desestabilizaron a Garry Kasparov en el encuentro.