jueves, 11 de noviembre de 2010

Problema Exponencial

Ifrán: Cada vez tomamos más en cuenta la opinión del "oráculo divino". La anterior "carrera" por conseguir los últimos informadores o enciclopedias de aperturas se ha cambiado por conseguir el "último y mejor motor" para nuestra computadora. Sin embargo son pocos los que entienden a este "nuevo" integrante de nuestra toma de decisiones cuya influencia es cada vez mayor. Con el fin de poder entender aunque sea de forma general qué es un motor (modulo) y cómo funciona le he pedido esta reseña a Guillermo.

Por el M.N Guillermo Carvalho

Los módulos de ajedrez en el presente


Mucho se ha hablado, mucho se habla, y mucho se hablará aun sobre las "computadoras" que juegan al ajedrez.
Existen multitud de mitos, dudas, historias y errores populares que se cometen al interpretar el juego de las creaciones lógicas, que se conocen con el nombre de "programas" o mas recientemente "motores".
La presente nota, sin pretender hacer un recorrido exhaustivo por todo el espectro de cuestiones relacionadas intentará arrojar un poco de luz sobre este interesante tema.

Un poco de historia

Desde hace tiempo, mucho antes de las computadoras electrónicas, surgió la idea de crear un autómata ajedrecista. Algo que fuese una creación del hombre, pero que no fuese propiamente humano, que pudiese resolver el problema que el ajedrez plantea, mejor que el propio hombre. Famoso es para casi todos los cultores del ajedrez, "El Turco", aquella máquina creada y exhibida en el siglo XVIII por Wolfgang von Kempelen.
Este autómata que fascino al mundo, cobró gran fama al derrotar a Napoleón Bonaparte pero lamentablemente resulto ser un fiasco que ocultaba a algún verdadero ajedrecista en su interior, que manipulaba al jugador con complejos mecanismos mecánicos. Mas de un siglo después, Leonardo Torres de Quevedo, construyo una maquina que daba mate de torre y rey, contra rey. Para lo que vemos hoy día, puede parecer poco, pero para el año 1912, esta maquina que no era ningún fiasco, significo un salto enorme.Unos 40 años después, Claude Shannon publica el primer articulo sobre como hacer un programa de ajedrez. Al año siguiente, el famoso Alan Turing, escribe un bosquejo de lo que seria un programa y en 1952 la computadora Maniac I, utilizada en el proyecto de ajedrez de Los Álamos, derrota a su primer oponente humano, una secretaria del proyecto, a la cual se le enseñan los movimientos básicos, poco antes de la partida.
De allí en mas, quizás para los tiempos de una vida humana el proceso parezca lento, pero el desarrollo ha sido meteórico si lo comparamos por ejemplo, con la evolución de una especie. En el 1956 se desarrolla la idea fundamental detrás de los algoritmos modernos de juego de ajedrez, la "poda alfa-beta". En el 66 se juega el primer match entre programas. En el 74 "Kaissa" gana el primer campeonato de programas. En el 77, sale al mercado la famosa "Chess Challenger". Esta fue la primer computadora portátil exclusiva para jugar al ajedrez. Tuve el placer de poder jugar dos partidas contra uno de estos equipos.
Eran una verdadera joya para su época. En 1982, el programa Belle, obtiene el titulo de maestro en EEUU. De allí en mas podríamos decir que se desarrolla la historia "moderna" de los programas, que quizás tenga su ultimo hito mas conocido, en la derrota de Vladimir Kramnik en el 2006 contra Deep-Fritz sin olvidar por supuesto, la famosa derrota de Garry Kasparov, frente a Deep Blue en el 97, probablemente el mojón mas conocido de todo lo antedicho.

El problema exponencial

En los tiempos mas recientes, se ha planteado lo que considero un falso conflicto en el tema ajedrecístico. La lucha hombre-maquina. Debido quizás a mi incursión en la programación de módulos así como en el ajedrez competitivo tengo visión sobre el particular no es la que mas se escucha. Lo primero que hay que tener bien presente, es que si bien uno ve jugar a una "computadora", el centro de la cuestión, es un programa. La computadora le da soporte a su ejecución, pero lo que tiene el poder de aproximar la solución del problema, es el programa. El problema planteado, tiene desde el punto de vista matemático, un tamaño exponencial. Quizás la expresión no sea formalmente correcta, pero sirve para ilustrar lo siguiente. Si contamos las posibles primeras jugadas del blanco, tendremos sin pretender ser exactos, en el entorno de 25. A modo de simplificación, diremos que en cada jugada, el jugador en turno tiene 25 opciones para elegir. Olvidemos por el momento la consideración ajedrecística de que la mayoría de esas jugadas son "malas".
De esta forma, al cabo de unas 5 jugadas, todas las posibles "partidas" legales, muchas de las cuales le parecerían locuras a un ajedrecista totalizarían alrededor de 10 millones. Si en lugar de 5, consideramos 15 jugadas, da algo así como 930 trillones, sin pretender ser exacto, ni nada parecido. Pues bien. El problema es lograr encontrar el mejor camino en ese "árbol" de variantes, con algún criterio.

El ajedrecista humano, ha aprendido a utilizar formas de seleccionar jugadas. Reconoce la mayoría de las jugadas por absurdas, y las descarta.
Mas aun, las descarta sin enumerarlas, casi siempre, usando su "intuición" y selecciona en cada piso del fabuloso árbol, las continuaciones mas prometedoras así como las supuestamente mas prometedoras para su oponente.
Un programa de ajedrez, apunta a resolver el mismo problema. El camino es diferente. Recorre ese mismo árbol, sin podarle ramas, mas que en situaciones muy claras, con la profundidad que le permite la capacidad de procesamiento de la maquina en la que esta siendo utilizado.
Es así de que de esos millones de posiciones que supuestamente analiza un programa, la enorme mayoría, serian ajedrecísticamente absurdas.
Aun así, el perfeccionamiento de los algoritmos de búsqueda, recorrida y poda del gran árbol del ajedrez, han permitido, combinado con un enorme crecimiento en la capacidad de procesamiento de las maquinas, alcanzar horizontes dentro del árbol, mas allá de la capacidad humana actual.

Un programa de ajedrez, intenta resolver el problema exponencial, por un camino diferente al que utiliza un humano, pero tampoco llega a resolverlo completamente. No podemos asegurar que algún día no lo haga, pero actualmente no lo hace. En enfrentamientos de programas contra ajedrecistas es posible sin embargo, que haya pasado el tiempo en que había oportunidad de vencer para los ajedrecistas.

Por alguna razón, que no comprendo cabalmente, esto parece ser mal digerido o mal enfocado por muchas personas. ¿ Que es lo que ha ocurrido ?, pues que un grupo de humanos muy inteligentes, capaces y trabajadores, han construido una cosa, llamada "programa" que alcanza a solucionar el problema exponencial del ajedrez, un poco mejor que los humanos ajedrecistas, que lo venían solucionando de otra manera hasta fines del siglo 20.
Y digo un poco mejor, porque el problema es tan enorme, que en el estado actual, los programas están a mi entender, unos pocos pasos mas cerca que los humanos sin programas, en un camino de quien sabe cuantos millones de pasos.

Los programas no entienden nada de ajedrez


He escuchado esta frase muchas veces. Pues no tiene nada de novedoso, además de que por un lado es correcta, y por otro no lo es.

Para empezar, la mayoría de los programadores no son ajedrecistas. Se enfocan en el problema desde un punto de vista no ajedrecístico, y evidentemente obtienen buenos resultados. "Entender" ajedrez, es entendido, valga la redundancia, como jugar al ajedrez de la forma humana.

Pues no...desde ese punto de vista, no entienden un comino de ajedrez. No "saben" nada de ajedrez. De hecho ni siquiera tiene sentido para mi, decir que "saben" de algo. Ni de ajedrez, ni de horticultura, ni de crianza de patos. Nada de nada. Solo hacen operaciones matemáticas, y mas
aun, si vamos mas abajo, solo detectan diferencias de corriente en microchips. No saben absolutamente nada de nada.

Cuando se hace la afirmación que precede este párrafo, se maneja un concepto de entender, completamente humano, y comprendido desde el punto de vista de lo que es entender algo, por alguien que supuestamente lo hace bien. Si los mejores humanos que mejor juegan y supuestamente mejor entienden el juego practico, y el ajedrez, no pueden detener a un programa que los combate sobre el tablero, poco sentido tiene acusar a los programas de cometer errores, ya que evidentemente, los oponentes humanos cometen peores errores, o con mayor frecuencia práctica.

Por la fuerza de los resultados, si los programas no entienden nada de ajedrez, habría que preguntarle a quienes no están en el mundo del ajedrez cuanto le parece que entienden los ajedrecistas, de ajedrez. Muy filosófico, pero así esta planteado. Aparentemente entender de ajedrez, no nos llevaría a jugar mejor, lo cual, desde un punto de vista practico, aun en el ajedrez únicamente "humano" es una rotunda verdad.

Los motores de análisis modernos

En mis tiempos de universidad, allá por los 80, siempre me atrajo el tema de la programación de ajedrez. Desgraciadamente no había casi documentación al respecto, y uno podía imaginarse vagamente como hacer las cosas, pero en términos técnicos, era como reinventar la rueda. De hecho luego de alguna documentación que leí, hice algún intento, y llegue a reinventar sin conocerlo, un algoritmo escrito 10 años antes. Luego de una década, gracias a Internet, las cosas comenzaron a cambiar, y súbitamente, se empezó a disponer de multitud de material, así como de la oportunidad de intercambiar ideas con académicos de todo el mundo, que trabajaban sobre ello.
También aparecieron algunos módulos con su código disponible, para quien quisiese leerlo, de forma de aprender los detalles de un funcionamiento típico, y eventualmente no tener que concentrarse en las rutinas académicamente triviales. Este ultimo punto significaba que uno no debía preocuparse mas que por el corazón del problema, que eran las rutinas de evaluación y recorrida del árbol, y no por la presentación grafica, o algunos otros pequeños módulos de interfaz.

Con la aparición de entornos gráficos gratuitos, primero el Winboard, y luego el fabuloso Arena, el problema de enfrentar módulos entre si se veía muy simplificado. Se desarrolló rápidamente un lenguaje estándar para comunicar módulos de análisis, con las carcasas graficas llamado "UCI". Mediante esta comunicación, la carcasa grafica le iba indicando al modulo el tiempo disponible, la jugada del modulo rival, y multitud de datos, y a su vez el modulo le pasaba a la carcasa, sus jugadas, las variantes analizadas y multitud de otros datos que hoy vemos como información adicional en las pantallas de nuestras computadoras.

Este ultimo salto permitió a los programadores, concentrarse en los módulos de análisis, y nada mas. Puede parecer poco, pero los programadores independientes se acercaron así, a competir con grandes compañías, ya que el desarrollo del modulo paso a ser lo único crucial.
El protocolo UCI fue aceptado por los productos comerciales como el Chessbase o el Fritz, de forma de poder incorporar a sus interfaces graficas los motores gratuitos, cada vez disponibles en mayor cantidad. Proliferaron las paginas donde aficionados, o expertos en el tema, realizaban torneos de módulos, evaluando su fuerza comparativa. Y es así que llegamos a la década actual, donde los programas como el Deep Blue, son algo así como los tiranosauros que otrora dominaron este mundillo, ejecutándose sobre maquinas físicas que valían millones. Hoy día, podemos tener módulos de gran fuerza, comparable a la de grandes maestros de primer orden (si, ya se...no saben nada de ajedrez) con quienes entrenar diferentes aspectos del juego.

Hoy día, casi no se ven competiciones de humanos contra módulos. Ya no tienen gracia. Los módulos han superado esa etapa y solo compiten entre ellos, pero sirviendo de sparrings a quienes seguimos practicando el juego a la manera tradicional.

De hecho, creo que los módulos han influido en la forma de encarar el juego, de las nuevas generaciones, siendo Carlsen quizás, el ejemplo mas notorio y reciente, pero eso el tiempo lo dirá.

Lo cierto es que los motores de hoy, nos permiten analizar nuestras partidas y ver sus innumerables errores. Permiten desarrollar líneas de apertura con una precisión que hace 5 años era impensable. Nos permiten practicar los finales, nos permiten ejercitar líneas repetidamente, y toda otra tarea que requiera de un sparring de la fuerza que seleccionemos.

Desde cierto punto de vista, eso no nos "enseñara" ajedrez, porque no podemos entender humanamente el ajedrez de esa forma. La forma humana de comprenderlo es otra, por aproximación basada en la experiencia, y no de bruces con un inmenso poder de calculo contra el enorme bosque de variantes.

Los errores que hoy cometen los módulos, basados en su forma de aproximar el problema exponencial, ocurren debido a algo bastante obvio. Son incapaces, igual que los humanos, de recorrer aun, todo el árbol. Son incapaces de resolver el problema. Lo interesante, es que cada vez le resulta mas difícil a un humano, percibir esos errores. A veces los entendemos como lo que un humano llamaría errores de "concepto" cuando en realidad, no pueden tener este tipo de errores, porque no manejan conceptos. Solo calculan. Cuanto mas profundo se calcula, menos importa si uno sabe lo que es una casilla débil, o se conoce el final de Alekhine-Capablanca. El calculo, con la profundidad suficiente, lo corrige todo. Eso es lo que hacen los programas. Aun así, un programa ligeramente mejor, puede calcular "un poquito" mas en ciertas situaciones, que otro, y entonces en ese horizonte de análisis, descubre un error posiblemente horrible del otro programa.
Pero si ud es un ajedrecista, y pudiese calcular a la perfección, siempre, variantes de 15 a 20 jugadas de profundidad, sin importar lo complejo de la posición, la frecuencia con la que se "colgaría" algo allá por la jugada 22 seria muy inferior a la que tendría su mortal y humano oponente que apenas analizara a la perfección, "solo" 18 jugadas de profundidad.

Hoy día se ve también otro fenómeno. No hace mas de un par de años, algunos módulos creados por estudiantes, empezaron a competir directamente con módulos de carácter comercial. Hubo algunas acusaciones de plagios por ingeniería reversa (tomar un programa y deducir su código para modificarlo), pero en la practica estos nuevos módulos, acusados de ser copias del Rybka, pronto lo superaron.
Peor aun, pusieron disponible el código, permitiendo que programadores de todo el mundo, pudiesen "toquetear" aquí y allí, estas maquinas lógicas, con ideas propias y lograr pequeñas mejoras. Al mejor estilo del código abierto tipo Linux, se pusieron así disponibles una serie de módulos gratuitos como el Robbolito, el Invanhoe o el actual Fire 1.31, totalmente popularizado en el mundo ajedrecístico, según indican entrenadores y jugadores asistentes a la ultima olimpiada de Kanthy-Mansik, por ejemplo. Salvo que algún operador privado tradicional, pueda pegar un salto enorme en cuestiones de diseño interno, mientras los programas sigan operando con una estructura tradicional como la actual, creo difícil que se pueda competir con estos módulos gratuitos.

Seguramente el mundo de los módulos de ajedrez, aun nos tenga muchas sorpresas, pero creo que algunas cosas ya son inamovibles. Con el diseño de funcionamiento actual, los módulos no saben ni sabrán nada de ajedrez, al estilo humano. A lo sumo en los recónditos subsuelos de sus funciones de evaluación, existen algunos conceptos ajedrecísticos muy básicos, pero no mucho mas que eso. Los humanos no pueden ya pensar seriamente en derrotar módulos, por lo menos, no los humanos educados desde la tradicional aproximación a la solución del problema exponencial. Los módulos y las interfaces graficas, son herramientas invaluables para el entrenamiento ajedrecístico moderno, al menos el entrenamiento tradicional (creo que hoy día no se puede pensar en prescindir de ellos).

El impacto tecnológico derivado de la red Internet, y las tecnologías de la comunicación, nos ponen a disposición, Internet en nuestro bolsillos junto con una capacidad de procesamiento también de bolsillo, superior a la de un centro de cómputos de los 80.

No es fácil vaticinar que pasara con el ajedrez en esta situación, pero creo que hoy día no cabe duda de que todo esto ha contribuido a popularizarlo como quizás muchos de los que nacimos antes de los 80, jamás habríamos soñado que ocurriría.

1 comentario:

  1. Hola, muy interesante el artículo. Sobre los problemas que aún tienen las computadoras en determinadas posiciones, les recomiendo que vean las partidas de Javier Rubio Ortín, es un aficionado que vence a los mejores módulos, en partidas rápidas, evidentemente que el sistema que usa es que útil solo para partidas de este tipo, ya que está muy lejos del ajedrez que se juega entre humanos. Sería bueno que, para continuar con el tema de los soft, Carvalho escriba un artículo sobre las computadoras como "entrenadores" de ajedrez, ya que hay múltiples puntos de vista en cuanto a su uso y resultados.
    A los que les interese, les dejo un enlace para descargar una base con partidas de Rubio contra varios programas, http://www.4shared.com/file/Bfc3U2yL/Javier_Rubio_Ajedrez.html.

    Saludos.

    ResponderEliminar