Magic: El encuentro es famoso un juego de cartas en el que los magos lanzan hechizos, invocan criaturas y utilizan objetos mágicos para derrotar a sus oponentes. En el juego, dos o más jugadores reúnen una baraja de 60 cartas con diferentes poderes. Estas 60 cartas son elegidas entre un total de unas 20.000 cartas que se han ido creando durante el desarrollo del juego. Aunque es similar a los juegos de rol de fantasía como Dragones y Mazmorras, tiene muchas más cartas y reglas más complejas que la mayoría de los juegos de naipes.

Eso plantea una cuestión interesante: entre los juegos del mundo real (aquellos que la gente juega realmente, y no los hipotéticos que los teóricos de juegos suelen analizar), ¿qué nivel de complejidad presenta el Magic? Esa es la pregunta a la que responde el trabajo del investigador independiente y diseñador de juegos de mesa de Cambridge (Reino Unido) Alex Churchill; la matemática del Instituto de Tecnología de Georgia (EE.UU.) Stella Biderman; y el científico en la Universidad de Pennsylvania (EE.UU.) Austin Herrick.

Por primera vez, este equipo ha medido la complejidad computacional de este juego. Para ello, lo ha codificado para que pueda ser jugado por un ordenador o máquina de Turing. "Esta construcción revela que Magic: El encuentro es el juego más complejo del mundo real a nivel computacional que se conoce en la historia", afirman.

En primer lugar, algunos antecedentes. Una tarea importante en las ciencias informáticas consiste en determinar si un problema puede ser resuelto en principio. Por ejemplo, decidir si dos números son primos relativos (en otras palabras, si su máximo divisor común es mayor que uno) es una tarea que se puede realizar en un número de pasos bien definidos y, por lo tanto, es computable.

En un juego ordinario de ajedrez, decidir si el jugador blanco tiene una estrategia ganadora también se puede computerizar. Para hacerlo hay que probar cada secuencia posible de movimientos para ver si el blanco puede forzar una victoria. Pero, aunque ambos problemas son computerizables, los recursos necesarios para resolverlos son muy diferentes.

Aquí es donde aparece la noción de la complejidad computacional. Se trata de una clasificación basada en los recursos necesarios para resolver cada problema.

El número de pasos necesarios para determinar si dos números son primos relativos es proporcional a una función polinómica de los números de entrada. Si la entrada es x, lo más importante en una función polinómica tiene la forma Cxⁿ, donde C y n son constantes. Por eso se trata de una clase de complejidad conocida como P, donde P representa el tiempo polinómico.

En cambio, el problema del ajedrez debe resolverse mediante fuerza bruta, y el número de pasos necesarios aumenta en proporción a una función exponencial de entrada. Si la entrada es x, el término más importante en una función exponencial tiene la forma Cn^x, donde C y n son constantes. Y a medida que x aumenta, todo esto se hace más grande mucho más rápido que Cxⁿ. Entonces este tipo de cálculos pertenece a una categoría de mayor complejidad llamada EXP, o tiempo exponencial.

Además de esto, existen varias otras categorías de complejidad variable, e incluso problemas para los cuales no existen algoritmos capaces de resolverlos. Estos se llaman no computerizables.

Determinar qué clase de complejidad un juego es un trabajo difícil. La mayoría de los juegos del mundo real tienen determinados límites en su complejidad, como el tamaño del tablero. Y esto hace que muchos de ellos resulten triviales desde el punto de vista de la complejidad. "La mayoría de las investigaciones de la teoría de juegos algorítmicos, de los juegos del mundo real, se han centrado principalmente en generalizaciones sobre los juegos comunes en vez de las versiones reales de los juegos", opinan Churchill y sus colaboradores.

Así que solo unos pocos juegos del mundo real (como el timbiriche, la Jenga, y el Tetris) presentan una complejidad no trivial. Churchil detalla: "Creemos que no se conoce ningún juego del mundo real que sea más difícil que el NP anterior a este trabajo".

Su investigación concluye que Magic: El encuentro es significativamente más complejo, y su método para averiguarlo parece relativamente sencillo. Churchill y sus colegas comienzan trasladando los poderes y las propiedades de cada carta en un conjunto de pasos que se pueden codificar.

Luego organizan una partida de dos jugadores cuyos pasos se introducen en una máquina de Turing. Finalmente, afirman que determinar si un jugador tiene una estrategia ganadora requiere un proceso equivalente al famoso problema de la parada en informática.

Este problema consiste en decidir si un programa informático con una entrada específica terminará de ejecutarse o continuará para siempre. En 1936, el científico Alan Turing demostró que ningún algoritmo podría determinar la respuesta. En otras palabras, se trata de un problema no computerizable.

La conclusión clave de Churchill y sus compañeros es que no se puede computerizar el proceso de determinar el resultado de un juego de Magic. "Esta es la primera vez que se demuestra que muestra que existe un juego del mundo real para el cual no es computable determinar la estrategia ganadora", asegura el equipo.

Se trata de un trabajo interesante que plantea importantes cuestiones básicas para la teoría de juegos. Por ejemplo, Churchill y sus colegas afirman que la principal teoría de juegos formal supone que cualquier juego debe ser computable. "Magic: El encuentro no encaja en las suposiciones que suelen hacer los informáticos al diseñar los juegos", concluyen.

Eso sugiere que los informáticos deben repensar sus ideas sobre los juegos, especialmente si esperan producir una unificada teoría computacional de juegos. Está claro que Magic representa una mágica pega en este aspecto.

Ref: arxiv.org/abs/1904.09828 : Magic: The Gathering Is Turing Complete