Next: Comparación de Avances en
Up: Otros avances desarrollados
Previous: Bases de Datos de
  Índice General
En cada movimiento un programa de ajedrez debe tomar una
importante decisión: ¿Cuanto tiempo asignar al análisis de la
posición? Posiciones de fácil determinación requieren un menor
tiempo que aquellas que son de difícil decisión o cálculo. Por
supuesto, decidir qué es una posición de "fácil determinación" y
una de "difícil determinación" es un problema, así como el
determinar qué es "poco" y "mucho" tiempo!. Afortunadamente se
han desarrollado buenos algoritmos para tomar estas decisiones.
Robert Hyatt describe como CRAY BLITZ administra su tiempo en su
paper publicado en 1984 [51].
Las partidas son generalmente jugadas bajo dos tipos de control
de tiempo. Lo más convencional son 2 horas para las primeras 40
jugadas y luego 1 hora para cada 20. Esto entrega un promedio de
3 minutos de reflexión por jugada. Al principio de cada
movimiento el programa determina el número de movimientos para
llegar al control de tiempo, digamos N, y el tiempo restante
para el control T. El cociente N/T entrega el tiempo base B
permitido para ese movimiento. Un tiempo máximo es definido para
el movimiento, típicamente 4B si bien esto debe ser ajustado en
las cercanías del control. El programa inicia entonces su
búsqueda de profundidad iterativa. Luego de buscar en un tiempo
B/2 el programa decide cuánto más buscar tomando en
consideración los scores obtenidos para cada variante. Si éstos
indican que la computadora tiene un movimiento fácil como una
recaptura o promoción la búsqueda finaliza. Esto salva una magnitud de tiempo B/2
para el siguiente movimiento. Si el programa decide continuar
entonces lo hace hasta llegar al limite de tiempo B, donde
nuevamente se realiza la decisión de cuánto más buscar. En este
momento, la máquina se detiene si el score de la variante
principal no ha sido cambiado en la búsqueda. Si ha cambiado,
indicando problemas en el horizonte, entonces el programa
continúa hasta el límite de tiempo 2B. Al llegar ahora a ese
límite el programa debe nuevamente decidir cuánto más buscar. En
este momento él termina la búsqueda a menos que se encuentre en
una situación muy inferior. La búsqueda siempre termina al llegar
al límite máximo 4B.
Los últimos encuentros entre humanos y computadoras han impuesto
un límite de tiempo fijo para toda la partida. Por ejemplo los
matches entre Kasparov y DeepBlue se jugaron al límite de 1 hora y
30 minutos para toda la partida. Esto hace que el algoritmo
descrito anteriormente sea más complejo dado que no es claro
cuánto durará la partida. Algunos programas asumen que el partido
durará otros 30 movimientos con lo cual imponen N = 30. Las
computadoras están programadas para "pensar" durante el tiempo
de su oponente. Apuestan a que éste realizará el movimiento
predecido en la variante principal y calculan la futura réplica.
Si la réplica del oponente es la esperada la máquina puede salvar
tiempo respondiendo en forma inmediata o bien continuar la
búsqueda. Si no, simplemente reinicia la búsqueda. Los mejores
programas adivinan el movimiento de su oponente con una
probabilidad del 50% con lo cual logran una ganancia de tiempo
similar. Esto es equivalente a correr un programa en una máquina
con 50% de mayor capacidad.
Next: Comparación de Avances en
Up: Otros avances desarrollados
Previous: Bases de Datos de
  Índice General
Santiago de Chile, Julio 2003