Monday, April 09, 2012

¿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.

5 comments:

emiliano said...

Es tan dificil porque los humanos siempre queremos sobre explicar TODO con teoremas, esquemas, metodos, marcos teoricos etc. Yo se bien que la ciencia es lo mejor que tenemos hasta ahora, pero pobre del que se quiera salir un poco de su rigor. Al fin la ciencia ha sido solo capaz hasta ahora de dar generalizacion superficiales de todo.

No se puede comprender que hay seres humanos que son capaces de resolver ese tipo de problemas encontrados en ese jueguito, tal vez otros tipos de inteligencia aplicados a este pasatiempo seria "MAS FACIL" explicar todo esto.

POr ultimo, que relevancia tiene en lo absoluto ese jueguito para dedicarle todo ese analisis? solo curiosidad, o eso lo mantiene lejos de los OXXOS, ja ja

Morsa said...

Emiliano,

No veo nada de malo en querer explicarse el entorno. El rigor de la ciencia no es gratuito y si a través del método científico no puedes probar algo, es porque probablemente se sale de la competencia del mismo, por ejemplo, la creencia en un dios, etc. Yo creo que te equivocas: la ciencia no ha dado hasta ahora generalizaciones superficiales de todo. Al contrario, se sabe mucho y a mucha profundidad en una gran variedad de temas. Tu generalización es de lo más superficial y habla de tu ignorancia del nivel que la ciencia ha alcanzado en su conjunto, que disfrutas en muchos casos de ello pero ni te percatas.

Eso que llamas "jueguito" habla de nuevo que como no juegas ajedrez, como no entiendes nada de eso, lo desdeñas. Mira, el problema del ajedrez es que hay que profundizar para entenderlo y esto puede llevar una vida. Si no conoces del tema, puedes juzgar pero tus juicios parten de la ignorancia por lo cual no pueden ser tomados muy serio. Tan importante es el ajedrez que hay gente que dedica su vida entera a comprender este juego. Para ti probablemente Kasparov, Karpov, Fischer y todos los grandes jugadores sean unos ociosos sin oficio ni beneficio, pero de nuevo, así probablemente pensarás porque no tienes idea de la belleza del juego, del placer estéticos que provoca y en todo el trabajo de análisis para desentrañar sus secretos.

Con respecto a lo de oxxo, ni te contesto porque tu comentario es grosero y está fuera de lugar.

Víctor Hugo Alcalá-Octaviano said...

¡Carambas!

Lo que es no tener ni la mas peregrina idea de lo que es la ciencia y el método científico. Esto es la mejor herramienta que tenemos para desentrañar misterios cualquiera que sea su índole. Ya me imagino que trae la gente su teléfono celular y pensarán que fue concebido por obra del espíritu santo.

Saludos.

Alberto Fuentes said...

para la tarea del colegio:

necesito saber cientificamente donde se encuentra el amor y el sentido de justicia (cuales son los elementos celulares que participan y como es la transformacion en los elementos quimicos). Junto a ello como se conectan con el pensamiento (que es el pensamiento: ¿como se mide cientificamente?)

Morsa said...

No tengo respuestas a tus preguntas. Lo lamento. Pero de hecho dudo que alguien sepa las respuestas a estas interrogantes

saludos