Hablemos de opciones

Antes de empezar, me gustaría agradecer los numerosos comentarios de los lectores a mi artículo anterior. No solo estimulan para seguir escribiendo, sino que además ayudan a enfocar los siguientes artículos.

Al final del anterior propuse la siguiente posición:

Juegan las negras. Dos preguntas:

  • ¿Qué opciones tienen las negras en esta posición? Hay que encontrar al menos cinco, quizá más.
  • Si el lector tuviera negras en esta posición, ¿qué opción escogería?

El lector Francisco Rivero, tras darle varias vueltas, encuentra las cinco opciones mínimas que yo pedía:

  • Rg7
  • Db8
  • Dd8
  • Te8
  • Abandonar

Estas son las opciones obvias, o casi obvias, pero hay más. El propio Francisco apunta una sexta:

  • No mover.

En una partida con tiempo, lógicamente, esto también llevaría a la derrota; pero no deja de ser una opción más a disposición del jugador. Es importante notar que a menudo tenemos más opciones de las que a primera vista se nos presentan. Llevando el tema al extremo, podemos encontrar algunas más:

  • Pegar un manotazo al tablero y salir corriendo.
  • Hacer una jugada ilegal, por ejemplo, Dd6xa8 (!!).
  • Disimuladamente, empujar con el meñique el peón de h7 a h6 y jugar Rh7.
  • Fingir un desmayo y esperar que el rival, compadecido, nos conceda tablas.

La primera opción, aparte de antideportiva y maleducada, es difícil que sirva para algo. Las dos siguientes son ilegales pero, ¿y si cuelan? En el fragor de la batalla, cosas peores se han visto; y aunque no cuelen, siempre podemos esperar que el rival se ponga nervioso, olvide parar el reloj y pierda por tiempo mientras llama al árbitro. En cuanto a la última, puedo atestiguar que la he visto funcionar al menos una vez.

 icon-arrow-circle-right Artículo recomendado: Ajedrez por ordenador: pasado, presente y futuro.

Que quede claro que no recomiendo ninguna de estas opciones; solo las incluyo aquí para demostrar que el ser humano tiene muchas más que el módulo. Este se limita a las cinco primeras, y en muchos casos a cuatro, pues pocos módulos están programados para abandonar; hay que darles mate, o bien, si es un torneo oficial, el operador está autorizado para abandonar “en su nombre”. El módulo no tiene manos, no hace jugadas ilegales, no finge desmayos (aunque su operador puede desenchufar el ordenador del rival, cosa que también se ha dado, y hablo de campeonatos del mundo de ordenadores).

Lo más curioso es que, aunque nos limitemos a las cinco primeras opciones, los criterios de selección del ser humano y del módulo son radicalmente diferentes:

El módulo evaluará la posición hasta la profundidad que su capacidad de proceso y el tiempo disponible le permitan; hecho esto, elegirá la jugada que le dé mejor valoración. En la posición que nos ocupa, todo depende de si entra en su horizonte de cálculo la siguiente variante: 34 … Rg7 35 Df8+! Rxf8 36 Ah6+ Ag7 (o bien 36 … Rg8, que lleva a lo mismo) 37 Tc8+ Dd8 38 Txd8+ Te8 39 Txe8 mate. Si “la ve”, entonces muy probablemente escogerá 34 … Te8, que pierde una torre pero evita el mate. Si no la ve, jugará 34 … Rg7 y quedará a merced de lo que su rival “la vea” (hay que decir que, en 1977, una variante de 10 movimientos podía caer fácilmente fuera del horizonte de muchos programas).

La respuesta del ser humano también dependerá de si “ve” la línea de mate que empieza con Df8. Si no la ve, jugará confiadamente 34 … Rg7 y, como el módulo, quedará a merced de la visión táctica del rival.

Ahora bien, si el jugador humano, con negras, ve que esa jugada llega al mate, elegirá probablemente una de estas alternativas (de hecho son las únicas que considera Francisco Rivero):

  • Si su rival es un maestro y además se le ve tranquilo, asumirá que ha visto el mate y abandonará.
  • Si su rival es de nivel medio-bajo y está apurado de tiempo, el negro jugará 34 … Rg7 y confiará en su suerte.

¡Cualquier cosa menos 34 … Te8, que es exactamente la jugada que haría el módulo!

Aclaro que la posición corresponde a una de las partidas más famosas del ajedrez por ordenador. Se jugó en Toronto, durante el Campeonato del Mundo de 1977, entre Duchess (EEUU) y Kaissa (Unión Soviética). Según fuentes fiables, estaban presentes, entre otros, dos ex-campeones del mundo de los años sesenta: Mijail Botvinnik (de ajedrez sobre el tablero) y Hans Berliner (de ajedrez por correspondencia), ambos expertos en ajedrez por ordenador.

Kaissa jugó 34 … Te8 y provocó una mueca de desagrado de los ilustres mirones. Solo cuando vieron los listados de cálculo de Kaissa comprobaron que había detectado la línea de mate que ellos pasaron por alto. La pregunta obvia es, ¿habría visto Duchess la línea? Por desgracia, no hay una respuesta documentada a esta pregunta, y sí muchas especulaciones; lo que está claro es que, con torre de menos, la posición de Kaissa pasó a ser desesperada.

Conclusión: Más allá de las capacidades de cálculo, queda claro que el hombre y la máquina tienen criterios de decisión muy dispares, y eso que los criterios de la máquina son los que el hombre le da…

Toda la Galia está ocupada…

Volveremos sobre las reflexiones anteriores, pero ya es hora de empezar, como prometí, a contar la historia del ajedrez por ordenador. Y qué mejor modo de hacerlo que presentando, al modo de las aventuras de Astérix el Galo, a la protagonista de este relato: la mente humana, creadora no solo del ajedrez y los ordenadores, sino también de la bolsa de valores, la Teoría de Juegos, el minimax, Astérix, el alfabeto con que escribo estos artículos, y el mismísimo AlphaZero, que nos espera al final de los mismos.

 icon-arrow-circle-right Recomendación: Lo que esconde el verdadero ajedrez por ordenador.

Como Astérix, la mente humana es inteligente y astuta, valiente y emprendedora. También es a veces solidaria y a veces egoísta, amable y colérica, eufórica y melancólica… Como el pequeño guerrero galo, tampoco hace ascos a una ayudita externa de vez en cuando.

Astérix tomando anabolizantes.

Tiene también, eso sí, algunos rasgos negativos que no encontramos en el pequeño galo: a menudo es sanguinaria, autodestructiva, perezosa, mentirosa… Sin embargo, a pesar de sus defectos, es un superhéroe cuyas hazañas no conocen límites. Todos los secretos del universo están en su poder (¿todos?… ¡no!), desde el funcionamiento interno de los átomos hasta los movimientos remotos de las galaxias; ha conquistado todos los rincones de este planeta, y no se detiene ahí.

Hablaremos mucho más de este personaje e iremos presentado a otros, pero ya es hora de empezar…

…Y empezamos con excusas

En el artículo anterior el ajedrez salía un poco malparado al situarlo en la escala de dificultades de la Teoría de Juegos; en este podemos decir con orgullo que entre los pioneros de su relación con los ordenadores se encuentran dos de los matemáticos más importantes del siglo XX: Alan Turing y Claude Shannon, si bien la aportación del primero al mundo del ajedrez por ordenador es más bien anecdótica (al contrario que en otros campos), y de ella quizá nos ocupemos en otro momento.

Muy diferente es el caso del distinguido matemático e ingeniero Claude Elwood Shannon (1916-2001). En 1948, mientras desarrollaba las ideas que dieron forma a la Era de la Información, publicó un artículo sobre cómo programar un ordenador para que juegue al ajedrez (Programming a Computer for Playing Chess).

El autor quizá temió que se le criticara por dedicarse a un asunto tan banal (o él mismo se sentiría culpable, teniendo entre manos algo mucho más importante), y ya en la introducción intenta justificarse (salvo que indique lo contrario, todas las traducciones en este artículo son mías):

Aunque quizá carezca de importancia práctica, el asunto tiene interés teórico, y es de esperar que una solución satisfactoria de este problema sirva como base para abordar otros de naturaleza similar y de mayor significado. Algunas posibilidades en este sentido son:

  • Máquinas para diseñar filtros, ecualizadores, etc.
  • Máquinas para diseñar circuitos de relés y de conmutación.
  • Máquinas que manejen el enrutamiento de las llamadas telefónicas según las circunstancias particulares y no por patrones fijos.
  • Máquinas para realizar operaciones matemáticas simbólicas (no numéricas).
  • Máquinas capaces de traducir de un idioma a otro.
  • Máquinas para tomar decisiones estratégicas en operaciones militares simples.
  • Máquinas capaces de orquestar una melodía.
  • Máquinas capaces de deducciones lógicas.

De esta forma, Shannon inauguró también la tradición de poner excusas al gasto de tiempo y recursos en el ajedrez por ordenador. Esta tradición ha perdurado hasta nuestros días. Por ejemplo, una comunicación oficial de IBM en 1997, a propósito del encuentro Kasparov-Deep Blue, decía lo siguiente:

La contienda ajedrecística ayudó a hacer avanzar la habilidad de los ordenadores a la hora de manejar el tipo de cálculos complejos necesarios para, entre otras cosas: descubrir nuevos medicamentos; realizar los modelos financieros requeridos para identificar tendencias y hacer análisis de riesgos; manejar búsquedas en bases de datos gigantes; y ejecutar cálculos masivos requeridos en muchos campos de la ciencia.

Y en octubre de 2017 The Economist cita a Demis Hassabis, cofundador de DeepMind (la empresa que desarrolló AlphaZero):

Cualquier cosa que se pueda reducir a una búsqueda inteligente entre un número enorme de posibilidades, dijo el Sr. Hassabis, podría beneficiarse del enfoque de AlphaGo [precedente de AlphaZero que juega al go]. Por ejemplo, averiguar cómo se pliegan las proteínas para alcanzar su forma funcional definitiva, predecir qué moléculas son prometedoras como medicinas, o simular con precisión reacciones químicas.

Nada nuevo bajo el sol… Al menos con el tiempo hemos tirado más de la medicina y menos de la guerra. En cuanto a la validez de estas excusas, por difícil que sea hacer un programa que juegue al ajedrez, no es nada comparado con hacer uno que tome decisiones correctas en la bolsa o que realice modelos macroeconómicos eficaces. Pero ya sabemos que una de las cosas que mejor se nos da a los ajedrecistas es poner excusas…

Claude Shannon

Mi reino por una estrategia

Pero sigamos con el artículo de Shannon. Después de una breve introducción (con algunas reflexiones interesantes que comentaremos en otro momento), Shannon expone una serie de consideraciones generales:

  • Una posición de ajedrez (incluyendo la situación de las piezas y todos los datos necesarios para establecer la posibilidad de enroque, captura al paso, tablas por repetición, etcétera) puede definirse mediante datos numéricos.
  • De acuerdo con la Teoría de Juegos, y dado que (1) en las reglas del ajedrez no hay elementos de azar y (2) los dos rivales disponen de toda la información sobre la partida (no solo la posición actual, sino el desarrollo completo de la misma), cualquier posición tiene una valoración definida y única, igual a una de las tres posibles terminaciones del juego (tablas o victoria de uno u otro bando).
  • No existe, sin embargo (y por suerte, añado yo), un método bien definido (un algoritmo) que permita determinar dicha valoración (tablas o victoria de algún bando) para cualquier posición de ajedrez. Es importante recalcar aquí que hablamos de una función directa, es decir, aplicable directamente a la posición, sin calcular variantes a partir de la misma.
  • Si existiera dicho algoritmo, es probable que fuera demasiado complicado para que un ser humano pudiera aplicarlo durante la partida; pero seguramente se podría implementar en un programa y ejecutar en un ordenador que tardara segundos o minutos en procesarlo. Dicho programa jugaría a la perfección, de la siguiente manera:
    • A partir de la posición dada, buscaría todas las jugadas legales posibles.
    • Aplicaría el algoritmo a todas las posiciones resultantes de las jugadas encontradas.
    • Elegiría la jugada (o unas de las jugadas) que le diera la mayor valoración posible para el bando que tiene el turno.
  • Sí existe un método teórico indirecto para valorar una posición, que no es otro que el minimax (aunque Shannon no llega a emplear el término), descrito en mi artículo anterior. Recordemos brevemente en qué consistiría:
    • Desde la posición de partida, se extiende el árbol de variantes hasta que todas las ramas terminan por jaque mate o por tablas reglamentarias.
    • Se da a los nodos terminarles el valor de +1 (el blanco da mate), 0 (tablas) o -1 (el negro da mate).
    • Se trasladan estos valores hacia arriba en el árbol, dando en cada nodo el valor más favorable al bando que tiene el turno en ese momento.
    • Al terminar este proceso, la posición inicial recibe la valoración que le corresponde (y a la que en mi anterior articulo llamé valoración heredada o VH).
    • Como en el caso anterior, para jugar a la perfección bastaría con elegir, en cada momento, la jugada que tuviera la valoración heredada más favorable de entre las jugadas legales en la posición de partida.
  • Este procedimiento indirecto de valoración es sencillo de implementar en un programa. El problema es que el tiempo de proceso de un minimax completo en una posición normal de ajedrez es demasiado largo, incluso para los ordenadores más potentes (los que había en la época de Shannon y los que tenemos ahora).
  • Por tanto, no es posible escribir un programa que juegue perfectamente al ajedrez: Ni por cálculo de la valoración directa de una posición, porque tal valoración no existe, ni por búsqueda de la valoración indirecta (heredada), porque el proceso llevaría demasiado tiempo.
  • Nuestro objetivo será, por tanto, escribir un programa que juegue razonablemente bien. En palabras de Shannon: Está claro entonces que el problema no es diseñar una máquina que juegue perfectamente al ajedrez (lo cual es impráctico) o que se limite a realizar jugadas legales (lo cual es trivial). Sería deseable que tuviera un nivel de juego competente, comparable quizá al de un buen jugador humano.
  • Para ello hay que idear una estrategia, es decir, un proceso capaz de escoger una jugada (si no óptima, al menos plausible) en cualquier posición dada, en un tiempo razonable.

Hasta aquí las consideraciones generales. Como paso previo para llegar a la susodicha estrategia, Shannon propuso un procedimiento para valorar posiciones; no un proceso perfecto, pues ya hemos visto que no existe tal, sino aproximado.

Todo está en los números

Al comienzo de este artículo hice referencia a la decisiva contribución de Shannon a la Era de la Información. Uno de los puntos clave de su tesis es que toda la información puede reducirse a números, y eso es exactamente lo que hace con las posiciones de ajedrez: cuando una posición no puede valorarse como jaque mate o tablas reglamentarias, se puede valorar sumando ciertos factores:

  • El material existente.
  • Los criterios posicionales, entre los cuales Shannon cita:
    • La movilidad de las piezas.
    • La existencia de peones débiles (retrasados, aislados o doblados).
    • La exposición del rey.

Tanto el material como los criterios posicionales pueden evaluarse numéricamente, por ejemplo:

  • El material, de acuerdo con los siguientes valores:
    • 9 para la dama.
    • 5 para la torre.
    • 3 para el alfil y el caballo.
    • 1 para el peón.
  • Los criterios posicionales, según lo siguiente:
    • La movilidad de las piezas, según el número de jugadas posibles de todas las piezas de cada bando.
    • La existencia de peones débiles, según el número de ellos que hay.
    • La exposición del rey, según el número de piezas enemigas cercanas y/o el número de peones que lo protegen.

Todos estos ejemplos son simplificaciones, pero pueden complicarse tanto como quiera el evaluador y, por supuesto, añadir nuevos criterios.

A continuación hay que aplicar a cada uno de los criterios posicionales un factor de corrección. Por ejemplo, si consideramos que dos peones débiles son tan importantes como un peón de más o de menos, multiplicaremos el número de peones débiles por 0,5.

Por último, haremos una suma algebraica de todos estos datos, dando valor positivo a lo que favorezca a las blancas y negativo a lo que favorezca a las negras. Así, una dama negra valdrá -9, mientras que un peón débil negro valdrá +0,5, ya que es un aspecto de la posición favorable al blanco.

Esta suma algebraica es nuestra función de evaluación. Como curiosidad, aquí va la de Shannon (he adaptado un poco las abreviaturas):

f(P) = 200(R-R’) + 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’) + …

donde:
(1) R,D,T,A,C,P son los números de reyes, damas, alfiles, caballos y peones blancos en el tablero.
(2) d,r,a son peones blancos doblados, retrasados y aislados.
(3) m es la movilidad de las piezas blancas (medida, digamos, por el número de jugadas legales posibles)
Las comillas indican valores similares para el negro.

Añado, por mi parte, que los puntos suspensivos indican la posibilidad de añadir otros factores, y que la valoración de la posición será favorable al blanco cuando f(P) sea positiva y al negro cuando sea negativa (y tanto más favorable a uno u otro cuanto más positiva o negativa sea).

Llama la atención la inclusión de los reyes en la fórmula. Explica el autor:

El jaque mate se ha incluido artificialmente aquí por el método de dar al rey el valor de 200 (cualquier valor mayor que la suma máxima posible del resto de factores valdría).

Como sabemos, esto no funciona exactamente así: el jaque mate consiste en que un rey está en jaque y ninguna jugada legal de su bando lo defiende del mismo. La partida termina aquí y el rey no llega a salir del tablero. Eso solo se daría si la partida durara dos turnos más: (1) cualquier jugada, obviamente no legal, del bando del rey que está en jaque, seguida de (2) la captura del mismo por parte del rival.

Lo que se hace en realidad, por tanto, es dar al hecho de que la posición es de jaque mate (no a la presencia de los reyes en el tablero, pues esta es invariable) un valor máximo y, cuando esto sucede, el resto de criterios (materiales y posicionales) no es que valgan menos, es que ni siquiera se calculan. Del mismo modo, si la posición es de tablas reglamentarias (por ejemplo, si el rey no está en jaque pero cualquier jugada de su bando lo pone en jaque), la valoración es de 0 y los demás criterios no tienen importancia.

Si quitamos entonces los reyes de la fórmula, y añadimos la seguridad del rey de forma muy simple (por ejemplo, el número de peones propios contiguos al rey, al que llamaremos n y daremos un factor de 0,3), tendríamos esta funció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’)

Veamos cómo aplicar esta función a una posición “cualquiera”:

Aparte del material presente, tenemos los siguientes criterios posicionales:

  • No hay peones doblados.
  • El blanco no tiene peones retrasados, el negro uno (f7).
  • El blanco tiene un peón aislado, el negro tres.
  • La movilidad del blanco es de 39, la del negro de 29 (salvo error por mi parte).
  • El rey blanco está resguardado por un peón, el negro también.

Los valores que tenemos son:

  • D = 1, D’ = 1, T = 0, T’ = 2, A = 1, A’ = 2, C = 2, C’ = 2, P = 6, P’ = 5
  • d = 0, d’ = 0, r = 0, r’ = 1, a = 1, a’ = 3, m = 39, m’ = 29, n = 1, n’ = 1

Con esto tendremos el siguiente resultado:

f(P) = 9(1-1) + 5(0-2) + 3(1-2+2-2) + (6-5) – 0,5(0-0+0-1+1-3) + 0,1(39-29) + 0,3(1-1)
f(P) = 0 – 10 – 3 + 1 + 1,5 + 1 + 0
f(P) = -9,5

Según nuestra función de evaluación, por tanto, la posición es muy favorable a las negras. Esto recuerda ligeramente a la posición que propuse a final de mi primera entrega, ya que es fácil ver que en realidad las negras están fritas; pero esa es una evaluación indirecta o heredada, resultante de profundizar en la posición y comprobar que el blanco puede dar mate en dos (1 Df6 Cxf6 2 Ae7).

La evaluación directa es -9,5 y, aunque añadiéramos nuevos criterios posicionales o modificáramos los factores de corrección de algunos de ellos, no cambiaría mucho.

¿Por qué? Sencillamente, porque la parte del león de la ecuación se la lleva el material. De hecho, ¿qué pasa si dividimos la evaluación en dos términos, una evaluación del material y otra de los criterios posicionales? Tenemos entonces dos funciones:

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

Y sus valores en la posición propuesta:

f(Pm) = -13
f(Pp) = +3,5

Hasta donde yo sé, esta división de la función de evaluación no se ha hecho hasta ahora, o no se le ha dado importancia. Sin embargo, en este caso al menos, da un resultado interesante: Una de las dos sub-funciones (la segunda, que da gran ventaja blanca) es coherente con lo que sabemos que es la valoración heredada de la posición (blancas dan mate). En vista de ello, ¿no será que hemos dado demasiada importancia al material? ¿Deberíamos aumentar los factores de corrección de los criterios posicionales? ¿O quizá modificar los valores de las piezas?

Antes de que algún lector me acuse de blasfemia o herejía por la última sugerencia, cierro aquí esta entrega, pero ¡cuidado! que en otra entrega volveré sobre este punto. Como estamos de vacaciones (al menos los lectores europeos), esta vez no voy a poner deberes. Saludos a todos y hasta la próxima, en la que seguiremos analizando el artículo de Claude Shannon.

4 COMENTARIOS

  1. Hola, José Fernando.

    Enhorabuena por tu artículo, igual de bueno que el anterior.

    Aunque aquí se habla de los albores de los algoritmos y la programación, y aunque sea un enfoque totalmente distinto, por aquello de que coincidieron en la misma época convendría citar al gran ingeniero español Leonardo Torres Quevedo, quien en 1912 inventó su máquina “El ajedrecista”, realmente la primera “máquina” capaz de “jugar” al ajedrez, y que por medios mecánicos y electromagnéticos era capaz de mover las piezas pos sí sola y dar el mate de rey+torre contra rey.

    http://www.ajedrezdeataque.com/04%20Articulos/00%20Otros%20articulos/Computadoras/Automatas/Torres_Quevedo.htm

    Un saludo.

    • Hola Juan,

      De nuevo, muchas gracias por tus comentarios.

      Tu sugerencia sobre la invención de Torres Quevedo es estupenda. De hecho, en su artículo Shannon menciona este caso.

      Dudé mucho si incuir esta mención en mi artículo, y al final opté por no hacerlo, más que nada por miedo a irme demasiado por las ramas. Aprovecho que lo hayas comentado tú para hacerlo ahora. Estas son las palabras de Shannon (como siempre, la traducción es mía):

      “Un intento más honesto [nota de JF: comparado con “El Turco”, el autómata del siglo XIX que en realidad tenia un jugador humano dentro] de diseñar una máquina que jugara al ajedrez fue llevado a cabo en 1914 por Torres y Quevedo, que construyó un dispositivo que jugaba el final de rey y torre contra rey (Vigneron, 1914). La máquina hacía las jugadas del bando fuerte y forzaba el mate en pocas jugadas, sin importar cómo jugara su oponente humano. Dado que se pueden establecer una serie de reglas que permitan realizar jugadas correctas en dicho final, el problema es relativamente sencillo, pero la idea era bastante avanzada para la época.”

  2. Enhorabuena por el artículo. Está muy “currao”. Muy interesante ese último párrafo de la primera parte, esa “conclusión”, esa dicotomía entre los criterios de decisión del hombre y de la máquina. Me he quedado con “sabor de boca”, y sería muy interesante su desarrollo. Pero como dices, volverás sobre esas reflexiones.

    Es imprescindible conocer la historia para comprender el por qué del presente y muy interesante ir viendo esa evolución del ajedrez electrónico desde sus comienzos hasta hoy, incluso nos permitirá vislumbrar un poco el futuro. Aunque a mi entender, visto lo visto, ese futuro es el presente, por eso es tan importante conocer como hemos llegado hasta aquí.

    Saludos.

    • Hola Francisco, muchas gracias por los elogios. 100% de acuerdo con lo que comentas, sobre todo “ese futuro es el presente”.

DEJA UNA RESPUESTA

¡Por favor, escribe tu comentario!
Please enter your name here

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.