Búsqueda

La herramienta de búsqueda de un programa de ajedrez tiene la misión de realizar un recorrido ordenado por el árbol de variantes a partir de una posición inicial (nodo raíz). Como ya hemos discutido en capítulos anteriores, la extensión del árbol de variantes es tal que sería imposible creer que un programa de computadora sería capaz de recorrerlo por completo. A pesar de esto, la capacidad de cálculo y almacenamiento de los computadores hacen que superen ampliamente al jugador "humano" en esta característica del juego del ajedrez (cálculo de variantes en profundidad) y a partir de esto es que los programadores han tratado de darle fuerza a los programas con búsquedas lo más profundas posible dentro del árbol de variantes.

A pesar de las mejoras que se han ido realizando sobre los años al motor de búsqueda, sobretodo en torno a la selectividad de las variantes a profundizar con tal de dar mayor velocidad (y profundidad) a la búsqueda, los jugadores humanos de buen nivel poseen la capacidad de discriminar rápidamente cuáles variantes analizar y cuáles no, característica que fue muy difícil de implementar en programas de ajedrez, tanto así que se optó por darle cabida al desarrollo de la búsqueda extensiva sobre el árbol de variantes, utilizada por los llamados programas de fuerza bruta, con tal de aprovechar la mayor capacidad y velocidad de los programas lo cual les aseguraba al menos no cometer errores de nivel de iniciado en el juego.

Los programas superaban entonces con creces a los humanos en el cálculo concreto de variantes hasta cierto nivel de profundidad, y a medida que iban mejorando el desarrollo de algoritmos y técnicas de poda la capacidad de "ver un movimiento más allá" iba creciendo. A nivel de jugadores humanos el tener un nivel mayor de profundidad de búsqueda equivale a calcular un movimiento extra en una secuencia de jugadas. Es decir, un programa que posee un nivel de profundidad extra por sobre su rival tendrá la capacidad de analizar en todas las variantes y durante todos los cálculos realizados durante cada jugada un movimiento por sobre su rival. Esto no pareciese ser mucho como para pensar en una diferencia importante entre un programa con profundidad B y otro con B+1, pero si llevamos esta diferencia al juego humano estamos hablando de una categoría de jugador por sobre otra, vale decir, un jugador que siempre ve un movimiento más que su rival y que en resumen tiene mayor información de lo que va a acontecer en cada secuencia de movimientos.

Respecto de esto se han realizado distintos experimentos entre programas con idéntica capacidad de hardware, la misma función de evaluación y motores de búsqueda similares, pero con diferencias en el nivel de profundidad. Uno de los experimentos más renombrados es el realizado en el programa BELLE por Thompson en 1983. Se definieron 6 programas distintos, P4, P5, ... ,P9. P4 busca con profundidad de 4 movimientos y a partir de acá realiza una búsqueda de posición estable. P5, P6, ... son programas similares que buscan con mayor profundidad en forma progresiva.

Los programas compitieron en un torneo todos contra todos (round-robin) a 20 rondas (cada programa jugaba 20 partidas contra cada otro de la competencia). Cada programa jugó con distintos colores a partir de 10 posiciones seleccionadas en forma aleatoria. Las posiciones fueron seleccionadas de la Enciclopedia de Aperturas de Ajedrez a partir del movimiento 10 y con una evaluación de posición igualada o bien con compensación. Cerca de 300 partidas fueron jugadas. Lamentablemente no se tiene referencia del tiempo de juego para las partidas. La performance de rating de cada programa fue determinada (en forma arbitraria) calculando el rating necesitado por un programa para tener como expectativa los puntos obtenidos. Los ratings fueron entonces iterados hasta que convergieron para cada programa. Los resultados se aprecian en la tabla

Lugar	Programa	P9	P8	P7	P6	P5	P4	PTS	performance
1	P9	-	14.5	16.0	18.5	20.0	20.0	89.0	2328
2	P8	5.5	-	15.0	18.5	19.5	20.0	78.5	2208
3	P7	4.0	5.0	-	16.0	17.0	20.0	62.0	2031
4	P6	1.5	1.5	4.0	-	16.5	19.0	42.5	1826
5	P5	0.0	0.5	3.0	3.5	-	15.0	22.0	1570
6	P4	0.0	0.0	0.0	0.5	5.0	-	5.5	1235

Tabla: Resultados del Experimento de Thompson en programas con distinto nivel de profundidad de búsqueda.

Resulta sorprendente ver la regularidad de comportamiento de los programas diferenciados por niveles de profundidad. Existe una correlación prácticamente lineal entre el performance de rating del programa y su límite de profundidad. El problema del test radica en que desafortunadamente a pesar de realizarse 20 partidas entra cada oponente y con porcentajes de victoria cercanos al 75% no se puede argumentar con total confianza que un programa es mejor que otro en general. De acuerdo Mysliwietz en [61] para establecer una diferencia de rating de 70 puntos son necesarias al menos 500 partidas mientras que para diferencias de 40-50 puntos cerca de 100 partidas son necesarias.

Newborn en [64] ha sugerido que si uno duplica la velocidad de un programa de fuerza bruta este mejora su rating en 100 puntos. Si asumimos una profundidad de factor 5,5 entonces un movimiento de ventaja otorga 250 puntos. En el rango lineal de P4 a P6 (el rango observado por Newborn en programas reales) esta relación se mantiene. En el rango extendido de este experimento (P7-P9) el incremento de rating no es similar al predecido. Algunas conclusiones respecto de este experimento realizado por los investigadores de BELLE:

1. Los ratings obtenidos a partir del experimento son similares a los ratings que BELLE obtiene contra jugadores humanos en cada nivel de profundidad.



2. Los programas no poseen un factor de temor o confianza. Esto significa que si P9 cree estar abajo en un score de una fracción de peón intentará empatar con P4. El resultado muestra que P9 tiene un mayor rating contra P8, luego contra P7, etc.



3. La función de evaluación para cada programa en el experimento fue la misma. En la evolución de un programa la función de evaluación debería evolucionar a la fuerza del programa. La función de evaluación de BELLE posee elementos de un jugador de 1600 pts. sabe mucho acerca de protección del Rey y estructuras de peones, mientras que poco acerca de debilidad de casillas y colaboración de piezas. Claramente P8 y P9 se beneficiarían a partir de una función de evaluación más sofisticada mientras que en P5 o P6 ésta perdería su capacidad dada el bajo nivel de profundidad.

Otros tests de este mismo estilo realizados en computadoras fueron realizados por Szabo en 1988, Berliner en 1990, Mysliwietz en 1995 y Jughanns en 1997. La descripción de estas experiencias se encuentra en [48].

En términos de búsqueda podemos argumentar que cualquier mejora en el algoritmo de recorrido sobre el árbol de variantes (podas o algoritmos de selectividad, por ejemplo) se verá reflejado en una búsqueda de mayor velocidad, o mejor dicho, en la capacidad de lograr mayor profundidad en igual tiempo que otro programa que no posea la mejora en su algoritmo de búsqueda. Esto apunta a demostrar que cualquier mejora en el proceso de búsqueda se verá reflejado en un aumento en el límite de profundidad de ella.