El problema del Tiempo

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.