EN ES PT
EN ES PT

Gambito de dama y la complejidad

27 de January de 2021 Blog por Cassotis Consulting

En 2020, el mundo redescubrió la pasión por el ajedrez después del gran éxito de la serie limitada de Netflix, Gambito de dama. Se trata de la historia de una jugadora de ajedrez altamente dotada en su camino al éxito. A lo largo de su evolución, el público ve lo complejo que puede ser un solo movimiento y las repercusiones que puede tener cada uno. Pero, ¿cuán difícil puede ser un juego de mesa de 8 x 8?

 

La estructura del juego y un conjunto de reglas preciso son atractivos para profesionales de matemática aplicada. Estas características han convertido al ajedrez en un contexto clásico para estudios de caso, especialmente en la teoría del juego y la optimización de combinaciones. 

 

El primer campo pretende comprender las interacciones entre jugadores racionales, en donde cada uno busca maximizar su ventaja. La culminación de este esfuerzo es saber cuál de los tres resultados posibles de un partido (las blancas ganan, las negras ganan o empate) se da, suponiendo que los dos jugadores lo jueguen a la perfección. Actualmente, los expertos están lejos de obtener las respuestas, inclusive con la ayuda de las mejores supercomputadoras. Es posible imaginar su complejidad al compararlo con otro juego de 8 x 8, como las damas, que se descifró en 2007 [1]. Este juego más sencillo demoró casi 28 años en descifrarse mientras se investigaba un juego que podía tener 5 x 1020 (500 trillones) de posibles posiciones.

 

El segundo caso está ilustrado por el Problema del caballo. Consiste en encontrar una secuencia de movimientos que le permita al caballo pasar por cada casilla del tablero exactamente una vez.  

 

Figura: Una solución para el Problema del caballo

 

Para el tablero clásico de 8 x 8, el problema se descifró. Existen 19 x 1015 (19 billones) de recorridos dirigidos posibles [2]. Esto está lejos de cualquier cálculo que alguien pueda adivinar con solo mirar el tablero y ya es difícil encontrar un recorrido viable.

 

Para ser un gran maestro del ajedrez, el jugador debe contar con habilidades analíticas extraordinarias, ya que debe predecir una gran cantidad de escenarios por adelantado. Podríamos pensar incorrectamente que hay una cantidad “limitada” de juegos y que, después de algunos años, usted puede saber cómo proceder en una situación específica. Nuevamente, la percepción se aleja de la realidad. En promedio, un juego de ajedrez cuenta con 80 rondas y aproximadamente tres movimientos sensibles (significativos) por cada ronda, lo cual genera casi 1040 juegos sensibles posibles. Esto implica mucho más de lo que toda la población del planeta podría jugar todos los días, ¡inclusive desde la formación de la tierra!

 

Estos ejemplos destacan la diferencia en magnitud entre la complejidad real de un problema y la percepción que podemos tener del mismo. En muchas oportunidades, la sociedad ha sido testigo de cómo la inteligencia artificial (IA) les ganó a grandes maestros del juego, en partidos como Deep Blue contra Kasparov y Watson contra Ken Jennings. Esto crea una idea falsa de que cada problema formulado matemáticamente se puede resolver en solo unos minutos por una máquina. Avances en el procesamiento de datos, como la informática cuántica y GPGPU, han elevado significativamente las capacidades de resolución de las computadoras. Sin embargo, dada la cantidad de soluciones posibles, aún dependemos de la creatividad de las personas para desarrollar algoritmos eficientes para resolver problemas complejos.


 

Referencias

[1] Schaeffer, J.; Burch, N.; Bjornsson, Y.; Kishimoto, A.; Muller, M.; Lake, R.; Lu, P. & Sutphen, S. (2007), 'Checkers Is Solved', Science , 1144079+.

[2] The On-Line Encyclopedia of Integer Sequences - OEIS Foundation Inc. (2020).


 

Autor: Guilherme Martino - Consultor Senior en Cassotis Consulting

                                      Coautor: Emmanuel Marchal - Managing Partner en Cassotis Consulting

 

Contáctenos

Vamos a hablar de optimización

R. da Paisagem, 220, sala 11S, Vila da Serra, Nova Lima - MG, Brasil

Hable con nosotros Enviar correo electrónico