¿Se puede resolver el juego del ajedrez?

Por Razvan Iagar (CSIC)*

Cuando la gente me pregunta a qué me dedico, al responder que aparte de investigador en matemáticas soy un jugador activo de ajedrez en competiciones, me hacen preguntas como: “Pero, ¿no está el ajedrez ya resuelto?, ¿no hay ya máquinas que pueden dar la mejor jugada?”. Voy a dar respuesta a estas cuestiones, argumentando por qué el ajedrez no solo no está acabado, sino que goza de muy buena salud y tiene un gran futuro por delante.

Por “resolver el ajedrez” entendemos establecer una estrategia óptima para jugar la partida; es decir, encontrar el camino que contiene las mejores jugadas tanto para las blancas como para las negras, desde el principio, o desde cualquier posición dada, hasta el final. En un sentido más débil, también podemos entender por “resolver el juego” el hecho de predecir el resultado óptimo (con el mejor juego posible) de una partida. Es decir, a partir de la posición inicial, cuál de los tres resultados posibles -victoria de las blancas, victoria de las negras o el resultado de tablas- es el resultado del juego óptimo de un encuentro entre dos jugadores perfectos sin exponer necesariamente la estrategia óptima.

Tan solo a través de fuerza bruta de cálculo, ninguna máquina puede resolver en la actualidad el ajedrez

Se trata de un problema abierto que ha surgido a partir del desarrollo de los programas informáticos de ajedrez. Pero esta cuestión ya se ha intentado solucionar antes. Claude Shannon, ‘el padre de la teoría de la información’, explicó en un artículo en 1950 la tarea de una máquina para analizar todas las variantes posibles de jugadas y concluyó que “una máquina operando con una tasa de una variante por microsegundo necesitaría un tiempo de 1090 años para calcular todas las posibilidades desde la primera jugada”. Shannon argumenta así que, tan solo a través de fuerza bruta de cálculo, ninguna máquina razonable podrá completar esta tarea.

Más recientemente, en 2007, se ha podido resolver el juego de las damas, emparentado con el ajedrez, pero con una complejidad mucho menor, sobre todo porque aquí todas las piezas son idénticas -tienen el mismo valor-, mientras que en el ajedrez las piezas tienen valores y capacidades diferentes. El equipo investigador liderado por el canadiense Jonathan Schaeffer, experto en inteligencia artificial, pudo comprobar que en las damas siempre se acaba en tablas si no se comete ningún error por parte de ninguno de los dos jugadores. El esfuerzo computacional para analizar de forma exhaustiva todas las posiciones ha tomado 18 años, utilizando en algunos periodos incluso 200 ordenadores conectados trabajando en paralelo y sin pausa, para analizar un número de posiciones del orden de 1014. ¡Todo un esfuerzo!

En 2007 se resolvió el juego de las damas.

Sin embargo, se trata un esfuerzo no extrapolable al ajedrez, ni en el aspecto de la capacidad computacional necesaria, ni en cuanto a método de demostración. Si miramos la complejidad del ajedrez desde el punto de vista del número total de partidas posibles que se pueden jugar (lo que en términos de la teoría de juegos recibe el nombre de ‘complejidad del árbol del juego’, game-tree complexity) alcanzamos un número muy grande, del orden de 10123. Esta estimación se deduce usando un cálculo basado en dos aproximaciones: que el número medio de jugadas completas de una partida es de 40 y que, en cada paso, el número medio de jugadas legales disponibles es de 35. El mismo Jonathan Schaeffer opina que solo después del establecimiento de una nueva tecnología de cálculo —ordenadores cuánticos— tendría sentido intentar ponerse a la tarea de resolver este juego milenario.

Por otro lado, el método de demostración que ha funcionado en las damas falla completamente en nuestro caso debido a los valores y capacidades diferentes de las piezas, y también por la existencia de algunas piezas con características especiales como el rey, cuyo mate acaba la partida en cualquier momento, incluso con todas las demás piezas en el tablero; o el peón, cuya coronación hace que reaparezcan en el tablero piezas más fuertes que posiblemente habían desaparecido antes en el transcurso de una partida. Así pues, no se puede establecer una base de finales de partidas con, por ejemplo, un número máximo de 10 piezas, de tal manera que cualquier partida tenga que pasar por una de esas posiciones. En efecto, un jaque mate puede ocurrir mucho antes de haber llegado a una situación de menos de 10 piezas en el tablero. Este razonamiento sencillo demuestra que es necesario tener la capacidad de analizar todas las posiciones posibles, sin simplificaciones.

Por todas estas razones, aunque el reto de resolver -o no- el ajedrez queda abierto (no hay una demostración matemática o lógica formal de que este hecho sea imposible), la mayoría de los especialistas consideran que no hay nada que indique una posibilidad práctica de llegar a una solución. Ni siquiera en el sentido débil, es decir, predecir el resultado sin decir las jugadas, a corto o medio plazo. Así pues, los maestros y aficionados pueden estar tranquilos: ¡el juego tiene todavía mucho futuro!

*Razvan Iagar es investigador del CSIC en el Instituto de Ciencias Matemáticas (ICMAT) de Madrid y autor del libro Matemáticas y ajedrez, de la colección ¿Qué sabemos de?, disponible en la Editorial CSIC y Los Libros de la Catarata.

4 comentarios

  1. Dice ser Rebor Mestare

    Dado que calcular la solución plantea un problema de búsqueda muy dificil de resolver desde un punto de vista computacional, cómo se plantea en el artículo; los resultados más prometedores ahora mismo vienen de la mano del mundo de la optimizacion, cuando el objetivo es ganar una partida.

    En este mundo, la combinación de 1) Markov Decision Processes e.g. Active Reinforcement Learning donde el aprendizaje se hace algo través de ejecutar acciones y sus recompensas (una combinación de recompensas inmediatas y futuras) y 2) redes neuronales profundas para aproximar los valores en cada par estado-acción (especialmente útiles cuando el estado se puede codificar como una imagen); proporcionan una solución excepcional para encontrar una política de juego óptima capaz de ganar a la política de cualquier experto a nivel mundial.

    Se puede consultar el paper de AlphaGo [1] donde se aplican estos concpetos a un juego mucho más complejo desde el punto de vista computaciónal con el juego del GO ya que el tablero es de 19×19 (Go tiene una complejidad en el árbol de búsqueda de 10^360 mientras que el ajedrez de 10^123 …. de manera general). En [2] también se aplican estos conceptos para obtener una política óptima para juegos de Atari.

    Un saludo y enhorabuena por estos estupendos artículos Razvan.

    [1] https://storage.googleapis.com/deepmind-media/alphago/AlphaGoNaturePaper.pdf
    [2] https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

    31 agosto 2017 | 16:53

  2. Dice ser a la fuerza bruta

    Dando un puñetazo a la tabal y la ayudita de san sacabó y de repente, que es cuando más gana la sorpresa.

    31 agosto 2017 | 17:30

  3. Dice ser ჷ

    La conclusión es que las matemáticas no son herramientas que todo lo pueden, son algo en cierto modo maravilloso, quizás alguien algún día surjan formas diferentes de representar todo lo conocido y lo que resta por conocer con otras herramientas, lo que ya sabemos es que las matemáticas tienen límites.
    Imaginemos una representación matemática del universo conocido contenida en un ordenador, es imposible generar esa representación y el contenedor de la misma por multiples razones conocidas y desconocidas. No son comparables las escalas, el juego del ajedrez es infinítamente más simple que todo el universo conocido, pero el concepto del cual se parte es similar, o sea que de momento ajo y agua.

    05 septiembre 2017 | 22:26

  4. Dice ser jmarc

    Por qué intentar resolver algo que normalmente quiere emular el enfrentamiento de dos cerebros humanos?

    27 octubre 2017 | 13:18

Los comentarios están cerrados.