Next: Generador de Movimientos
Up: Hardware
Previous: Hardware Dedicado
  Índice General
El tiempo es un factor necesario de considerar en la práctica de
ajedrez de torneo. Los cálculos de movimientos, decisiones y
análisis deben realizarse dentro del ritmo de juego considerado
en la partida, lo cual hace del ajedrez una disciplina
en que quien sepa tomar la mejor decisión en los límites de
tiempo establecidos sea quien tenga las mayores chance de
victoria.
El problema del factor tiempo fue el incentivo por el cual el
enfoque principal del desarrollo de los programas fue el aumentar
la velocidad de cada proceso involucrado en la decisión por un
movimiento; generación de movimientos, búsqueda y evaluación. Dada
la limitancia de tiempo y la gran cantidad de cálculos a realizar,
mientras mayor velocidad de cálculo y mientras más ahorro de
análisis de variantes entonces mayor cantidad de jugadas se podrán
calcular y una mejor decisión respecto al movimiento a realzar
podrá ser tomada. En el caso particular del ajedrez la
"explosion" de cantidad de movimientos generados ya en pocos
niveles de profundidad hacía imposible tener cálculos precisos.
Mientras más bajamos en profundidad más tiempo es requerido en
calcular todos los movimientos del nivel en que nos encontramos,
lo cual hará que en la búsqueda requiramos cada vez más tiempo
para calcular las posibilidades de cada movimiento. Por ejemplo,
si suponemos un programa que logra calcular 100 posiciones por
segundo, a una tasa de 20 movimientos posibles por cada posición
(una estimación promedio y bastante optimista) obtendríamos una
gráfica de Profundidad v/s Tiempo como la de la figura
.
Figura:
Gráfica de Profundidad v/s Tiempo para un programa de
capacidad de cálculo
de 100 posiciones por segundo y estimación de
20 movimientos por posición
Podríamos suponer que si se dispusiera de un tiempo infinito
probablemente cualquier máquina podría descubrir el mejor
movimiento a pesar de tener muy baja capacidad de procesamiento,
pero acá hay un punto interesante a considerar y que es la
relación de la capacidad de memoria con el proceso de búsqueda en
profundidad. De nada serviría contar con mucho tiempo si carecemos
de la memoria suficiente para poder mantener guardados los
millones de nodos generados ya en un quinto nivel de profundidad.
En este caso, la búsqueda debería "ahorrar" la mayor cantidad de
nodos mantenidos en memoria con tal de poder almacenar sólo la
información relevante. Para este caso lo más apropiado sería
realizar búsquedas iterativas que tengan en consideración la
limitancia física de memoria, y a este respecto una idea
interesante han sido las propuestas de algoritmos de búsqueda como
el A* o más recientemente el B* [34] ambos con
profundidades iterativas y capacidad de memoria limitada.
Next: Generador de Movimientos
Up: Hardware
Previous: Hardware Dedicado
  Índice General
Santiago de Chile, Julio 2003