¿Por qué el ajedrez es tan difícil?

En estas últimas semanas he estado reflexionando el por qué el ajedrez es un juego tan difícil y creo haber llegado a una conclusión que quisiera llamarla definitiva. Para ello, debo antes explicar algunos asuntos.

Todos los problemas pueden definirse vía una descripción o representación del conocimiento de un pequeño mundo (llamado micromundo), el cual puede satisfacer o no ciertas metas. Remitámonos al problema de representar el árbol de variantes en una partida de ajedrez. Aquí creamos un árbol que empieza en la jugada inicial (desde la posición dada en un principio) y a partir de ahí se abren hojas para acomodar las jugadas posibles. A su vez se pueden abrir más nodos hacia abajo y depende de qué tan profundo generemos este árbol, podemos llegar a tener un árbol muy frondoso (dependerá, desde luego, de la posición inicial dada).

Dada esta representación, lo que normalmente hacemos es recorrer el árbol de variantes, valorando cada posición y viendo si nos es conveniente o no. Esto es lo que hacen los programas de ajedrez a partir de una función de evaluación, el corazón de todo programa de esta naturaleza. Los ingenios cibernéticos actuales como Rybka, Houdini, Fritz, StockFish, etc., pueden analizar miles de jugadas por segundo. Desafortunadamente esta velocidad no es suficiente porque el crecimiento de jugadas en el árbol de posibilidades de una partida de ajedrez crece de forma exponencial y muy rápido (creo que lo que estoy diciendo es un pleonasmo, pero en fin).

Existen dos métodos clásicos para recorrer el árbol (o espacio de búsqueda): Búsqueda en profundidad (depth first) y Búsqueda a lo ancho (breadth first). El siguiente diagrama puede mostrarnos cómo hacer la búsqueda en profundidad:

Consideremos que la meta es hallar que desde una posición dada, se llega al mate. Si empezamos la búsqueda en el nodo 1 (ver figura), buscamos probar la meta. Si no se cumple, entonces nos movemos al nodo 2. Repetimos probar la meta. Si no se cumple, pasamos al siguiente nodo a la izquierda, el cual es el 3. Si probamos la meta y no se cumple, pasamos al nodo 4. Si de nuevo, al probar la meta, fallamos, entonces nos movemos al nodo inmediatamente a la derecha, pues el nodo 4 es un nodo terminal. Así, caemos en en nodo 5. Si de nuevo la meta no se puede probar entonces hacemos backtrack y hemos regresado al nodo 3. Como éste ya vimos que no era solución, regresamos vía este mismo procedimiento al nodo 2 y posteriormente al 1. Entonces hallamos que el siguiente nodo a analizar es el 7. ¿Es una solución? Si no lo es, regresamos al anterior (pues el 7 es otro nodo terminal), y comenzamos a recorrer el nodo 8. Este nodo contiene dos hojas, el 9 y el 12. ¿a cuál debe irse? De acuerdo a lo que sabemos primero revisamos el nodo de la izquierda, es decir, pasamos al 9, de ahí al 10. Si en ninguno de los casos la meta se cumple, hacemos backtrack del nodo 10 y analizamos el nodo 11. Si tampoco resulta este ser solución, hacemos backtrack y subimos hasta el nodo 8, en donde solamente nos resta analizar el nodo 12. Si éste no es solución, entonces no existe una respuesta satisfactoria al problema.

Nótese como hacemos una búsqueda exhaustiva, empezando por el nodo raíz y siempre revisando primero el nodo izquierdo hasta lo más profundo para acto seguido analizar el nodo derecho mas inmediato.

La otra búsqueda, llamada breadth first permite buscar y valorar cada nodo al mismo nivel. Por ejemplo, en la siguiente imagen:

En la búsqueda breadth first, el algoritmo examina todos los nodos a un nivel (llamado en ocasiones ply).

El siguiente diagrama muestra el orden en el que los nodos son examinados. Como puede notarse, todos los nodos en un nivel se analizan consecutivamente buscando satisfacer la meta. Al terminar esto se sigue en el siguiente nivel y así sucesivamente.

Para el caso del ajedrez, si el diagrama del árbol mostrado representara analizar jugadas, ¿qué es lo mejor? ¿buscar en profundidad o a lo ancho?

El caso ideal sería analizar en profundidad pero esto implicaría ir hasta las últimas consecuencias en todas las variantes hasta llegar al mate o a una posición ganadora. Pero esto es una utopía por el crecimiento de variantes en ajedrez que llega a ser inmanejable. No importa qué computadora podamos conseguir. Siempre el ajedrez nos superará en términos de jugadas a analizar.

La otra opción es ser más humanos y ver una jugada adelante en todas las ramas (como en breadth first). Podríamos evaluar hasta ese momento y decir quién tiene la ventaja. Sin emabrgo, sabemos que esto es poco, porque por ejemplo, una jugada en donde el blanco puede capturar la dama enemiga parece una buena idea... a menos que el rival conteste con un mate inmediato en castigo a nuestra glotonería. Por ello hay que ir al siguiente nivel en el árbol. Cada nivel es un ply y en ajedrez esto significa media jugada, un movimiento, ya sea de blancas o negras. Dos plys conforman una jugada completa (de blancas y negras).

Una vez que ya sabemos esto, podemos preguntarnos qué clase de búsquedas hace el ser humano. Desde luego que en la multitud de posibilidades de búsqueda, si tomamos solamente este par de sistemas, veremos que es más probable que el ser humano decida  analizar la siguiente jugada con sus variantes (un ply). En la medida de lo posible buscará analizar más profundamente, pero no llegará en general a analizar más de 6  o 7 plys (3 a 3.5 jugadas en promedio), que de hecho es lo que una de las primeras computadoras dedicadas al ajedrez, la Belle, de Ken Thompson, podía analizar y con lo que logró el título de maestro nacional en los Estados Unidos allá por los años setentas del siglo pasado.

Evidentemente un gran maestro, un jugador de elite, puede analizar si lo requiere, muchos plys. Por ejemplo, hace poco Nakamura y Carlsen se enfrascaron en una compleja partida en donde ambos jugadores vieron en algún momento más allá de 20 plys, asombroso para los seres humanos llegar a esa profundidad. Y aunque la posición lo amerite, muchas veces está fuera del alcance de la imaginación de los jugadores de cierto nivel.

Así pues, el ajedrez es difícil, muy difícil para los seres humanos porque nosotros comúnmente usamos breadth first search en lugar de depth first search, y esto probablemente tenga que ver además con las problemáticas que normalmente se tienen en la vida cotidiana y por ende, en la manera de buscar que usamos los seres humanos, en un afán de esforzarnos lo menos posible para hallar la solución adecuada, sino la óptima. Para decirlo de manera menos técnica: nuestras búsquedas para solucionar los problemas son en general bastante superficiales, quizás demasiado.