AJEDREZ POR ORDENADOR: Pasado, presente y futuro (Parte 5)

AJEDREZ POR ORDENADOR: Pasado, presente y futuro
Parte 5
Por Jose Fernando Blanco

¿Qué pasaba con ese enroque?

Terminé mi artículo anterior con un diagrama y una pregunta:

Figura 1: ¡Falta información!

¿Cuál es el número exacto de posiciones que contiene el árbol de variantes de la siguiente posición (producida tras la jugada 29 de las negras), con una profundidad de 2 movimientos (uno por bando)?

Ya dije que la pregunta tenía trampas. Estas eran dos, como los lectores pudieron adivinar:

• ¿Cuál fue la última jugada del negro? Si esta fue 29 … c7-c5 o 29 … e7-e5, el blanco tendría sendas capturas al paso disponibles.
• ¿Puede enrocar corto el blanco?

Esta información faltaba adrede en mi problema, por lo que pido disculpas a los lectores; si bien, conociendo los datos de la partida, es posible encontrarla en Internet (aunque reconozco que no es sencillo). Aquí, por ejemplo:

https://chess24.com/en/watch/live-tournaments/espana-veteran-2018-50/1/1/2

Como puede verse, la última jugada negra fue 29 … Ad8, por lo que no hay capturas al paso disponibles para el blanco. Por otro lado, y esto es lo que me llamó la atención de la partida, el enroque corto blanco no es posible porque… ¡el blanco ya enrocó en la jugada 17! Lo más curioso es que la torre que se encuentra actualmente en h8 no es la que comenzó la partida en esa casilla, sino la otra.

Aclaradas estas dudas, las jugadas posibles del blanco y sus respectivas posibles respuestas del negro están en esta tabla:

Tabla 1: La punta del iceberg.

En resumen, el blanco tiene 25 jugadas legales y hay 711 respuestas en total a todas ellas, por lo que las posiciones que se dan, contando ambos nodos, son 736.

Esto es solo el comienzo de una bola de nieve que alcanza dimensiones astronómicas en pocos pasos, como ya vimos al final del artículo anterior. Profundicemos un poco ahora en cómo afecta esta bola de nieve a las expectativas de conseguir un ordenador capaz de aplicar la Estrategia A de Shannon de forma rápida y con buenos resultados.

Recordemos que el artículo objeto de nuestro estudio está escrito en los primeros años 50, es decir, en la prehistoria de la computación: aparecieron los primeros mastodontes, ordenadores enormes y (desde nuestro punto de vista) muy lentos. Los microprocesadores y los procesadores en paralelo, que fueron las bases para el desarrollo exponencial de la computación, no aparecieron hasta los años 70. Los pioneros de mitad del siglo pasado confiaban, sin duda, en un aumento de la velocidad de proceso, pero no tan espectacular, ni tan sostenido, como se dio veinte años después.

Con estas consideraciones en mente, veamos lo que pensaba Shannon:

Por desgracia, una máquina que operara según la Estrategia A sería lenta, y su juego demasiado débil. Sería lenta porque, aunque se pudiera evaluar cada posición en un microsegundo (muy optimista), se necesitan unas 10 ⁹ evaluaciones para cada posición tras la tercera jugada de ambos bandos. De este modo, se requerirían más de 16 minutos para una jugada, o sea, diez horas para realizar las jugadas de uno de los dos bandos en una partida de cuarenta jugadas.

Una puntualización: para hacer una jugada en la Estrategia A no basta con “evaluar” las posiciones. Como ya expliqué en el apartado anterior, también hay que comparar estas evaluaciones y trasladarlas a las ramas superiores del árbol de variantes. Este proceso no es ni mucho menos sencillo, pero por ahora vamos a aceptar que la mayor parte del tiempo de proceso consiste, como insinúa Shannon, en evaluar las posiciones. Por este y otros motivos, los cálculos que siguen son solamente aproximados.

Para entender hasta qué punto el cálculo de Shannon era “muy optimista”, vamos a tomar como ejemplo el ordenador SEAC, construido en 1950 y que, según la Wikipedia, podía realizar una suma en 864 μs (microsegundos) y una multiplicación en 2.980 μs.

Figura 2: El ordenador SEAC.

Retomemos, de nuestro tercer artículo, la función f(P) propuesta para la evaluación de una posición:

f(P) = 9(D-D’) + 5(T-T’) + 3(A-A’+C-C’) + (P-P’) – 0,5(d-d’+r-r’+a-a’) + 0,1(m-m’) + 0,3(n-n’)

Como vemos, la función incluye 18 sumas (las restas cuentan como sumas también) y siete multiplicaciones. El tiempo de evaluación de esta función para SEAC (al que llamaremos t(P)) sería, por tanto:

t(P) = 18 x 864 + 7 x 2.980 = 36.412 μs

Esto quiere decir que la estimación de Shannon era unas 36.000 veces más optimista que la realidad de ese momento (insisto de nuevo en que son cálculos poco precisos, pero válidos para unas conclusiones aproximadas).

 icon-chevron-right Sugerencia: Aprende más informática aplicada al ajedrez en nuestra Academia online: The Zugzwang Members.

Es bueno tener un plan B

Probablemente Shannon calculaba que se tardaría unas cuantas décadas en llegar a la velocidad de proceso de su estimación. Hoy sabemos que estaba equivocado, pero por ahora vamos a seguir su línea de razonamiento: Si nunca vamos a tener una máquina así y, aunque la tuviéramos, sería demasiado lenta (diez horas por partida) y demasiado floja (ya que una profundidad de tres jugadas por bando tampoco es para tirar cohetes), más nos vale mejorar la Estrategia A. Para ello, Shannon identificó dos áreas de mejora:

• En primer lugar, un aspecto que comentamos de pasada en otro artículo y que dejamos “aparcado” entonces: el tratamiento de posiciones no quiescentes, es decir, aquellas en las que, por así decirlo, están pasando cosas (intercambios de piezas, sucesiones de jaques, posibles promociones de peones…). Detenerse en un nivel preestablecido, como establece la Estrategia A, puede ser terrible si en alguna de las variantes dicho nivel se encuentra en una posición no quiescente (cosa bastante normal).
• En segundo lugar, parece innecesario calcular todas las variantes posibles. Sin duda hay jugadas, en cualquier posición, que son obviamente malas, o al menos irrelevantes; detectar esas jugadas y eliminarlas del proceso de selección se traduciría en un gran ahorro de tiempo y, por tanto, en un aumento en el nivel de juego.

A la implementación de estas dos mejoras en el programa de ajedrez Shannon la llamó Estrategia B.

Un personaje escurridizo

A Shannon le atraía la idea de que estas dos mejoras, si llegaran a implementarse, acercarían la estrategia del ordenador al modo de pensar de un ajedrecista humano. En sus propias palabras (las negritas son mías):

La máquina opera de forma muy ineficiente: calcula todas las variantes hasta exactamente tres jugadas y ahí se detiene (incluso si ella o el oponente están en jaque). Un buen jugador humano examina solo unas pocas variantes seleccionadas y las analiza hasta un nivel razonable.

Así aparece por primera vez, en esta historia, nuestro segundo protagonista: si en la tercera entrega de esta serie conocimos al personaje principal (la inteligencia humana, a la que en adelante, para abreviar, llamaremos IH), ahora se presenta ante nosotros su hermanastra (o su hija, según se mire): la inteligencia artificial (en adelante IA).

No es raro que ya en el primer artículo sobre programación de ordenadores para jugar al ajedrez aparezca este sujeto. Cuando nació el concepto de procesador artificial ya se planteó la pregunta: “¿Podrán llegar a pensar estas máquinas como pensamos nosotros?”, y desde siempre se ha asociado la tarea de pensar con el juego del ajedrez (no se sabe muy bien por qué; supongo que por la cara de concentración que ponemos cuando jugamos).

Como consecuencia de esta asociación, una y otra vez los avances del ajedrez por ordenador se han identificado como avances de la IA, cuando eran en realidad grandes logros de la IH. Pero no adelantemos acontecimientos. Por ahora vamos a conformarnos con analizar hasta qué punto la Estrategia B es comparable al modo de jugar humano.

Dice Shannon que el ser humano examina solo unas pocas variantes seleccionadas y las analiza hasta un nivel razonable. Eso es cierto. Pero el ser humano hace también otras cosas cuando juega una partida de ajedrez. No me resisto a copiar aquí un fragmento del magnífico libro “Los siete pecados capitales del ajedrez”, de Jonathan Rowson (también la traducción es mía):

Figura 3: GM Jonathan Rowson.

También piensas cuando juegas al ajedrez, pero al hacerlo estás evaluando, recordando, juzgando, analizando, comparando, intuyendo, buscando, dudando, sincronizando, calibrando, provocando, comprendiendo, orientando, complicando, simplificando, planificando, anticipando, cuestionando, divagando, etcétera. Como vimos en el prólogo, los pensamientos están también profundamente vinculados con las emociones, en cuyo caso también puedes estar preocupándote, temiendo, confiando, esperando, lamentando, reprochándote, alarmándote, excitándote, etcétera.

Cierto que no necesitamos que un programa haga todas esas cosas para parecer humano; pero es innegable que la Estrategia B de Shannon está bastante lejos de conseguir dicho objetivo. Le faltaría, por ejemplo (me limito a enumerar cosas que se pueden hacer durante la partida, no antes o después de la misma):

• Idear planes, que podríamos definir, de forma muy simple, como conjuntos de jugadas. Por ejemplo “voy a llevar a mi rey de g1 a b3”, “pondré todos mis peones en casillas de color negro”, “cambiaré mi alfil de casillas blancas por uno de sus caballos”, etcétera.
• Recordar esquemas de partidas anteriores (propias y de otros jugadores) que tengan similitudes con la posición actual.
• Tratar de adivinar y adelantarse a las intenciones del rival.
• Juzgar posiciones según nuestra intuición.
• Inducir al rival, por diferentes medios, a caer en una celada.
• Hacer trampas.

Esta lista no es exhaustiva (y los dos últimos puntos posiblemente sean prescindibles), pero sirve para ilustrar que hay un mundo entre el programa imaginado por Shannon y el juego de una persona medianamente experta.

Pero al menos es un paso, porque la Estrategia A no tiene nada de humana; y pongo esta frase en negrita porque, como veremos en un artículo posterior, tiene una importancia capital.

Si hay que ir más lejos, se va…

Sigamos ahora con Shannon. ¿Qué propone hacer para implementar las dos mejoras que definen la “Estrategia B”?

• Para la primera mejora: Una función g(P), siendo P la posición objeto del cálculo, que determine la quiescencia de la misma. Esta función valdrá:
  • 1, si hay alguna pieza atacada por una pieza de menor valor, o bien atacada por más piezas que las que la defienden; o si hay un jaque posible en una casilla controlada por el rival.
  • 0, en cualquier otro caso.
• Para la segunda mejora: Una función h(P, M), siendo P la posición y M un posible movimiento en la misma. Esta función determinaría si el movimiento M merece la pena analizarse, por comparación con un valor concreto h_min (es decir: si h(P, M) es mayor que h_min, la variante se tendrá en cuenta, y viceversa).

La primera función es fácil de implementar y su uso consistiría en profundizar en el análisis de la posición en cuestión, si g(P) = 1, hasta que g(P) = 0, estableciendo posiblemente un límite máximo de profundidad. Esta mejora, por cierto, también es aplicable a la Estrategia A. Todos los módulos con un nivel presentable implementan esta función, y las variantes adicionales que se calculan suelen recibir el nombre de extensores. Como ejemplo, véase el siguiente pantallazo, tomado de un programa comercial muy conocido:

Figura 4: Doble profundidad.

La profundidad, que he enmarcado en rojo, tiene dos números: el primero (15) es la profundidad a la que el programa ha llegado calculando todas las variantes seleccionadas, mientras que el segundo (46) es la profundidad a la que ha llegado el extensor más largo.

Este filtro es un coladero

Ya tenemos una función g(P) que decide si deberíamos profundizar en una variante concreta. ¿Y la función h(P, M)? Eso ya es otra historia… Veamos qué sugiere Shannon:

Un jaque es el tipo de jugada más forzada. Las respuestas del oponente están muy limitadas; nunca puede contestar con un contraataque, por ejemplo. Esto significa que una variante que empiece con jaque puede calcularse más fácilmente que otras. De manera similar las capturas, ataques a piezas mayores, amenazas de mate, etcétera, limitan las respuestas del rival y deberían calcularse tanto si la jugada parece buena a primera vista como si no. Por tanto, h(P, M) debería tener valores altos para todas las jugadas que fuercen la respuesta (jaques, capturas y jugadas de ataque) y para jugadas de desarrollo; valores medios para las jugadas defensivas; y valores bajos para el resto de jugadas. Al explorar una variante, h(P, M) debe calcularse para cada movimiento posible y usarse para seleccionar o descartar la variante que dicho movimiento origina. A medida que se profundiza en el análisis, se requiere aumentar h_min, de manera que se analicen menos subvariantes cada vez.

No hay que ser Gran Maestro para detectar los puntos dudosos de estas sugerencias. Por ejemplo, ¿que un jaque no se puede contestar con un contraataque? Hay cientos de ejemplos de partidas en los que se demuestra lo contrario. Por otro lado, a menudo la mejor jugada en una partida no es un jaque o una amenaza, o una jugada defensiva, sino una jugada tranquila:

Figura 5: Tranquila, pero venenosa.

Muchos lectores identificarán esta posición; a los que no la conozcan, les sugiero que intenten adivinar la jugada del blanco sin ayuda de un módulo. Pista: seguramente el valor de la función h(P, M) de Shannon para esta jugada sería muy bajo, pues no da jaque, no captura, no ataca ninguna pieza, ni amenaza mate.

Hay miles de ejemplos parecidos. La conclusión es clara: Muchas jugadas buenas (a veces ganadoras, y a veces las únicas ganadoras) no pasarían el filtro de Shannon. Si aplicáramos su criterio, de hecho, nuestro programa estaría todo el rato dando jaques o capturando piezas rivales.

Lógicamente, el criterio de Shannon es muy mejorable, pero el problema de fondo permanece: tarde o temprano alguna jugada importante no pasará el filtro de la función h(P, M). Supongamos, por ejemplo, que encontramos una nueva h(P, M) tan fina que tiene un 95% de eficacia (es decir, que 95 de cada 100 veces la mejor jugada pasa el filtro). Pues bien, después de 7 movimientos por bando la probabilidad de que la mejor jugada se nos haya escapado en algún nivel del análisis es de más del 50%. Y en una partida de 40 jugadas la probabilidad de que la mejor jugada se nos escape alguna vez es superior al 98%.

Esto no es muy grave si pasan el filtro otras jugadas, no tan buenas pero lo bastante buenas; pero en una partida siempre hay varias posiciones que requieren gran precisión, y a la larga la probabilidad de desechar una jugada importante es siempre alta.

Sin embargo, con todas sus limitaciones, en los años 50 la Estrategia B era la única esperanza de conseguir un programa de ordenador que jugara a un nivel decente en un tiempo aceptable; los números en contra de la Estrategia A eran demasiado contundentes. En mi próxima entrega contaré cómo se las apañaron los primeros programadores; ahora vamos a comentar los últimos apartados del artículo de Shannon.

Creando estilos

A Shannon le preocupaba (con motivo) que su hipotético programa hiciera siempre las mismas jugadas (y, sobre todo, que cayera siempre en las mismas líneas perdedoras). Para evitar esto, planteó algunas posibilidades:

• Introducir un elemento aleatorio que permitiera, en la misma posición, elegir jugadas diferentes, siempre que las evaluaciones de dichas jugadas fueran iguales o muy parecidas.
• Proporcionar al programa las principales variantes de apertura, de manera que eligiera entre ellas, variando de una partida u otra.
• Permitir aplicar diferentes estilos al juego de la máquina, modificando a voluntad, de una partida a otra, los valores de la función de evaluación.

Es interesante que ya Shannon plantea el problema ético de si la segunda posibilidad (proporcionar al programa variantes de apertura conocidas) es una ventaja adicional para la máquina con respecto al jugador humano. Para él no lo es:

Durante las primeras jugadas (hasta que alguno de los rivales se desvíe del libro o se alcance el final de la variante almacenada) la máquina jugará de memoria. Esto no puede considerarse “trampa”, ya que es así como los maestros de ajedrez juegan la apertura.

Hay que reconocer que el razonamiento parece bastante válido, aunque tiene un matiz importante: los ajedrecistas humanos, efectivamente, aprenden aperturas que después aplican en sus partidas; pero las memorizan en un medio (su cerebro) no demasiado fiable para guardar información, ya que tiene mucha tendencia a olvidarla y mezclarla. En cambio, los ordenadores llevan las variantes escritas en un soporte tecnológico prácticamente infalible.

Además, los maestros aprenden esas variantes a base de un gran esfuerzo y mucho tiempo de estudio; mientras que los ordenadores no emplean ese tiempo, simplemente leen la información que alguien les ha dejado escrita. Es como si los humanos, en vez de memorizar las variantes que juegan, pudieran llevarlas apuntadas en una enorme chuleta que les asomara por los bolsillos, sin que nadie pudiera acusarles de hacer trampa (y las chuletas se las hiciera un secretario).

En los años cincuenta esto no parecía un problema. De hecho, todos los módulos decentes incluían libros de aperturas; pero más que nada para conseguir que hicieran las primeras jugadas más rápidamente y, sobre todo, para igualar un poco las condiciones de juego, ya que el nivel de juego de los programas era muy inferior incluso al de simples aficionados.

El problema vino mucho después, cuando los programas alcanzaron el nivel de maestros, y muchos usuarios empezaron a ver con desconfianza que ese monstruo que habían comprado, además de jugar mejor que ellos, tuviera apuntadas todas las jugadas de apertura conocidas. Pero ya llegaremos a eso.

A continuación, Shannon comenta la (in)capacidad de aprendizaje de las máquinas. Dejo sus reflexiones aquí tal cual e invito a los lectores a comentarlas. Yo lo haré en una futura entrega, pues este es uno de los aspectos que más han cambiado en estos setenta años:

La principal debilidad de la máquina es que no puede aprender de sus errores. El único modo de que lo haga es mejorar el programa. Se ha estudiado la posibilidad de diseñar un programa capaz de mejorar su juego de forma autónoma pero, aunque parece posible, los métodos estudiados hasta ahora no parecen muy prácticos. Una posibilidad es tener un programa de mayor nivel que cambie los términos y coeficientes implicados en la función de evaluación, basándose en los resultados de las partidas jugadas por la máquina.

Y ahora ¡todos a programar!

Shannon termina su artículo proponiendo un enfoque radicalmente distinto a todo lo anteriormente expuesto. Resumidamente, se trataría de alimentar al programa con “posiciones tipo” (combinaciones estándar, temas tácticos, maniobras…) de manera que el programa reconozca dichas posiciones en sus partidas y dirija sus análisis hacia las mismas.

Esto, desde luego, es muchísimo más fácil de decir que de hacer, y así lo reconoce Shannon. No obstante, algunos lo han intentado y, en su momento, hablaremos de ello también (adelanto que tuvieron poco éxito y que incluso cierta eminencia ajedrecística se llevó un buen revolcón).

Termina así mi revisión del artículo de Shannon, que se ha alargado más de lo que yo preveía. Este artículo fue el pistoletazo de salida que puso a cientos de informáticos manos a la obra de crear un programa de ajedrez ejecutable en un ordenador. En los próximos artículos veremos cómo les fue.

Ya he dejado un par de preguntas repartidas por el texto, por tanto no voy a poner más aquí. ¡Espero vuestros comentarios!