miércoles, 2 de febrero de 2011

ADELANTOS EN SOFWARE Y HARWARE

Avances de Hardware

Procesadores de mayor velocidad

La velocidad de unidades de procesamiento se ha incrementado dramáticamente debido principalmente a la evolución de la tecnología de semiconductores. Las computadoras han progresado desde ejecutar aproximadamente 10.000 instrucciones por segundo (en la época de los primeros programas) a aproximadamente 1.000.000.000 en la actualidad. El aumento de velocidad ha sido del orden de magnitud de 100.000 veces. Imaginemos comparativamente si la velocidad de transporte hubiese aumentado en esa magnitud durante el mismo periodo de tiempo. Los aviones volarían a 100.000.000 millas por hora; un viaje al sol tomaría cerca de 1 hora de vuelo y un viaje a la estrella más cercana, Alpha Centauri, la cual está a 4,5 años luz de distancia, tomaría cerca de sólo 70 años.

Capacidad de Memoria

Memorias de mayor capacidad son el resultado de la rápida evolución en tecnología de semiconductores. Los primeros programas de ajedrez corrían en máquinas que utilizaban memorias de base magnética. A inicios de 1970 aparecen las memorias realizadas en base a semiconductores utilizadas en la serie de computadoras IBM 370. Así como la velocidad de los computadores se incrementó en un factor de aproximadamente 100.000, la capacidad de memoria creció en una proporción similar. Este hecho es particularmente importante en programas que utilizan tablas de transposición. A medida que aumenta la velocidad de la computadora memorias de capacidad proporcionalmente mayor son necesarias para mantener la cantidad extra de posiciones que son buscadas.

Tamaño de Palabras

El tamaño de palabras de bits ha logrado crecimientos bastante importantes sobretodo a nivel de pequeñas computadoras. Los procesadores Intel 80386 y 80486 están basados en palabras de 32 bits. En el otro extremo se utilizaron palabras de largo 64 bits, diseñadas especialmente para máquinas de ajedrez dado que el tablero, para buena fortuna de los programas ajedrecistas, posee exactamente 64 casillas. Palabras de largo aún mayor significaría que una mayor cantidad de información puede trasladarse dentro de la computadora en un ciclo de reloj pero su implementación es algo que involucra mucho costo. No es probable el que en el futuro las computadoras usen palabras de tamaño mayor a los 64 bits, pero se puede predecir que tendrán mayor capacidad de flexibilidad en la manipulación de palabras de rango 1 a 64 bits.

Computadoras de menor tamaño

Computadoras que en alguna ocasión ocupaban una pieza completa ahora ocupan sólo un escritorio siendo considerablemente más poderosas que las anteriores. Las unidades de proceso de las primeras computadoras de ajedrez ocupaban varias cabinas de tubos de vacío ocupando grandes volúmenes. Los microprocesadores de hoy en día ocupan menos de una pulgada siendo mucho mas poderosos.

Hardware Dedicado

El hardware de propósito especial para máquinas que jugasen ajedrez apareció por vez primera a mediados de los 70 iniciando un rápido proceso de sofisticación y mejoras. El primero de estos sistemas fue diseñado utilizando componentes que podrían ser clasificados como circuitos integrados de mediana escala. Cada chip estaba constituido por 10 a 100 componentes lógicas. Los circuitos más recientes han sido diseñados con tecnología VLSI. Uno de los ejemplos más populares fue el diseño de la computadora Deep Thought, la cual tanto en su generador de movimientos y función de evaluación poseían componentes a nivel de Hardware.
El programa OSTRICH fue el primero en participar en una competencia oficial de computadoras utilizando esta tecnología. Cinco computadoras serie Data General 16-bit Nova estaban conectadas mediante un paquete de comunicación de alta velocidad. En años subsiguientes 8 computadoras DG fueron utilizadas logrando un incremento de la velocidad de cálculo en un orden 5. Otros programas famosos que utilizaron multiproceso fueron CRAYBLITZ (1983 y 1984, procesador CRAY X-MP, 2 y 4 procesadores), CHESS CHALLENGER (1986, 20 microprocesadores 8086) y Deep Thought (1989, 3 procesadores de tecnología SUN y VLSI). DeepBlue para su match contra Kasparov utilizó un total de 2 frames RS6000 SP albergando 15 computadoras RS/6000 cada uno. Cada nodo contenía dos circuitos de ajedrez con 8 procesadores cada uno, lo que otorga en total 8x2x15x2 = 480 procesadores en el sistema completo.
Avances en Software SOFWARE 

Generador de Movimientos

La forma inicial de programar un generador de movimientos fue el generar mediante fórmulas matemáticas los movimientos legales de cada pieza sobre el tablero, obteniendo todas las posibilidades con tal de entregárselas como una lista al software de búsqueda. Esta propuesta fue mencionada por vez primera en el paper de Shannon [68] y se aplicó a prácticamente todos los programas de la época.

La idea inicial fue el que el programa generara sólo los mejores movimientos con tal de reducir drásticamente el árbol de variantes (estrategia "B", según la nomenclatura dada por Shannon) pero los resultados distaron de ser positivos puesto que el problema principal relacionado con este proceso fue que en las búsquedas en profundidad esta forma de generar los movimientos tomaba un tiempo excesivo, lo cual hacía muy lento el proceso global, motivo por el cual se buscaron otras formas de programar la generación de movidas en base a operaciones que la computadora pudiese realizar más rápidamente.

Sólo hasta principios de 1970 (gracias a la presencia de hardware y ambientes de desarrollo de mayor capacidad) se utilizó la técnica de los mapas de bits (bit-boards)la cual significó un gran avance en este proceso del juego de la máquina dado que se redujo la complejidad de operaciones a aquellas que son básicas para la máquina. A pesar de este avance, era clara la necesidad de implementar fuera del software esta función del programa, dado que la necesidad de hacer búsquedas más rápidas y profundas se basaba en un generador de alta velocidad, cosa que era muy difícil lograr a nivel de hardware.

Las mejoras en esta función del programa vinieron principalmente del lado del desarrollo de hardware específico para la generación de movimientos. En 1977 el programa "Belle" fue el primero en utilizar circuitos digitales para la generación de movimientos logrando aumentar su velocidad de búsqueda de 200 a 160.000 posiciones por segundo. El generador utilizado en Belle sirvió como punto de partida para máquinas más poderosas. El computador que derrotó a Kasparov en 1997, DeepBlue, tenía 30 procesadores IBM RS-6000 SP acoplados a 480 chips. Esta máquina fue capaz de lograr velocidades computacionales de 200 millones de posiciones por segundo.

Técnicas de Búsqueda

Las técnicas de búsqueda en el ajedrez han sido probablemente la parte más desarrollada en términos de investigación para la mejora de algoritmos dentro del proceso del juego. Es acá en donde el programa realiza el mayor esfuerzo en recolectar información suficiente para decidir por un movimiento.

Los algoritmos desarrollados para este fin han sido variados. La primera propuesta, presentada por Shannon, fue la búsqueda por fuerza bruta a profundidad fija, examinando todas las continuaciones posibles hasta cierto límite de movimientos. Esta búsqueda se realizaría mediante el algoritmo Minimax.

Hasta principios de los 70 los programas de ajedrez seguían basándose en los modelos de Shannon para realizar su proceso de búsqueda. Hasta ese momento el diseño de programas de ajedrez se focalizaba principalmente en el orden de los movimientos con tal de lograr la mejor "poda" de variantes: jaques, capturas, "movidas asesinas", amenazas y avances de peones pasados. Categorizando los movimientos en distintos grupos mediante amenazas tácticas (de corto plazo) o estratégicas (de largo plazo) se podía asegurar el que las variantes "forzadas" serían analizadas primero. Esta técnica lograba generar cortes o reducciones en el árbol de búsqueda para aquellas variantes que se clasificaban como innecesarias de analizar.

Función de Evaluación

Las primeras propuestas de función de evaluación estaban orientadas a tener una evaluación estática de la posición basada fundamentalmente en el concepto de material. Rápidamente se captó que esta evaluación no era suficiente, considerando que en el ajedrez existen factores estructurales los cuales afectarán a largo plazo el curso de la partida, por lo cual es muy probable que el programa no encuentre las consecuencias de esta situación en su búsqueda en profundidad. Estos aspectos, denominados "Posicionales" debieron incluirse en la función de evaluación.

Los primeros programas incluyeron algunos parámetros posicionales básicos, los cuales tenían un peso importante en la evaluación de la posición pero no igualable al peso que poseía el factor de material. El problema entonces de dar un adecuado "peso" a cada parámetro de la función de evaluación, y en qué momento de la partida darlo a uno u otro parámetro constituía un problema denominado carencia de "conocimiento ajedrecístico" cuya solución estaba en captar las impresiones de los jugadores humanos "expertos" y asimilarlas en el programa.

La inclusión de un mayor "conocimiento ajedrecístico" en los programas fue logrado mediante el trabajo conjunto entre programadores y maestros de ajedrez. Desafortunadamente, costó bastante el poder combinar de manera eficiente una idea de función de evaluación lo más completa posible con la mayor cantidad de parámetros de medición, pero a la vez muy rápida en su capacidad de cálculo.

No hay comentarios:

Publicar un comentario