A primera vista, los dos problemas que se mencionaron antes no tienen solución, pero se pueden imaginar maneras de darle la vuelta al problema. Comenzando por el árbol de análisis, si se quieren evaluar todas las posibles posiciones, bajando 12 niveles en el juego como lo hacía Deep Blue, se necesita evaluar cada posición un millón de veces más rápido, cosa que con la tecnología actual no es posible. ¿Qué opciones se tienen, qué se puede hacer para no evaluar todas las posiciones?
Por supuesto, es necesario recortar el árbol de análisis, decidir lo antes posible cuáles de las ramas en el árbol prometen un mejor futuro y cortar las demás. Los juegos de ajedrez utilizan una técnica de búsqueda conocida como alfa-beta, que hace justo eso, suspende la evaluación de un movimiento en cuanto es notorio que hay otros que son mejores. Por ejemplo, supóngase que un movimiento nos lleva a una posición en la que existe posibilidad de ganar el juego; si luego se evalúa otro movimiento en el que el enemigo puede empatar, se suspende la evaluación y se elimina el movimiento de nuestras opciones.
Alfa-beta permite recortar el espacio de búsqueda en un factor de raíz cuadrada del número de posiciones. En este caso, si se quiere evaluar hasta 12 movimientos en el futuro, entonces en lugar de las 3812 posiciones de fuerza bruta, sólo se deben evaluar 4 × 109 o cuatro mil millones de posiciones.
Con eso se acorta el número de posiciones, pero sigue siendo un árbol muy grande. Se puede recurrir a otra técnica de búsqueda que se llama recorte de movimiento nulo, donde lo que se hace es imaginar que se deja pasar un turno y permitir que el contrincante mueva dos veces seguidas. Si después de este tipo de ventaja, una posición sigue siendo buena para nosotros, se puede suspender la búsqueda, porque se ha encontrado un punto de quiebre, un punto donde es posible recortar la rama de evaluación.
Utilizando una mezcla entre alfa-beta y el recorte de movimiento nulo de manera recursiva, se puede lograr un ahorro estimado de la raíz cuadrada de los movimientos. Con esto, con un equipo de cómputo como Deep Blue se pueden evaluar hasta 12 niveles en el juego de go. Por supuesto, esto no incluye la evaluación compleja de cada posición, pero es un avance.
Curiosamente, el autor del algoritmo de recorte de movimiento nulo, Murray Campbell, fue uno de los miembros clave del equipo que construyó Deep Blue, pero no utilizó esta técnica para el ajedrez porque sus reglas impiden los movimientos nulos o pasar, pero esto no sucede en el go, donde sí es válido realizar un movimiento nulo.
Optimizar la evaluación de una posición en go también es posible utilizando una técnica muy socorrida en los sistemas de cómputo, la memoria caché, en la que se puede almacenar la evaluación de una fracción del juego y sólo cuando sea necesario, por ejemplo porque se agregaron piedras a esa región o una región contigua, se vuelve a evaluar esa sección.
Hoy día, con la tecnología actual de microprocesadores, es posible en teoría construir una computadora en un solo chip, que sea 100 veces más rápida que los 480 procesadores de Deep Blue. Más aún, si se instalaran 480 de estas poderosas computadoras en una arquitectura paralela, sería 100 veces más rápida. La ley de Moore, que dice que el número de transistores que se pueden integrar en un circuito crece exponencialmente y se duplica cada dos años, soporta la idea de que dentro de 10 años más se logrará otro incremento de 100 veces.
En resumen, la esperanza de diversos expertos es que durante el siguiente decenio será posible construir una computadora que pueda buscar más de tres billones de posiciones por segundo, aproximadamente un millón de veces más rápida que Deep Blue y, por supuesto, que esta computadora podrá jugar go al más alto nivel y ganarle a cualquier humano.
Curiosidades
Existen varios métodos para generar números aleatorios en una computadora. Pero, realmente no son aleatorios, son seudoaleatorios porque responden a una función y parecen tener comportamiento de números aleatorios. La función generalmente se llama RAND.
