Next: Técnicas de Búsqueda
Up: Avances en Software
Previous: Avances en Software
  Índice General
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.
Las característica principal de estos generadores a nivel de
Hardware es el poder caracterizar a las casillas de origen y
destino mediante transmisores y receptores respectivamente, para
luego generar mediante un árbol de prioridades los movimientos
ordenados de acuerdo a criterios de capturas, jaques, etc.
[38]. La principal ventaja entre el generador de
movimientos de DeepBlue y BELLE es que el primero solucionó el
problema de generar en primer orden los movimientos de jaque.
En la actualidad la utilización de mapas de bits es
prácticamente universal en todos los programas de ajedrez. Las
mejoras se ven principalmente en los tipos de mapas generados de
acuerdo al tipo de movimientos buscados (reglas de mapas de bits).
El principal desarrollo en este tema es a nivel de hardware en
donde los avances se han visto en el orden de jugadas entregado en
la generación de los movimientos. En el último año se han
desarrollado también tarjetas de hardware específicas para
implementación en computadoras personales (Field Programable Gate
Arrays) las cuales han sido utilizadas en forma experimental.
Next: Técnicas de Búsqueda
Up: Avances en Software
Previous: Avances en Software
  Índice General
Santiago de Chile, Julio 2003