Magic: The Gathering es oficialmente el juego más complejo del mundo

Una imagen de paquetes de cartas Magic: The Gathering Nathan Rupert

Magic: The Gathering es un juego de cartas en el que los magos lanzan hechizos, invocan criaturas y explotan objetos mágicos para derrotar a sus oponentes.

En el juego, dos o más jugadores arman cada uno una baraja de 60 cartas con diferentes poderes. Eligen estos mazos de un grupo de unas 20.000 cartas creadas a medida que evolucionaba el juego. Aunque es similar a los juegos de rol de fantasía como Dungeons and Dragons, tiene muchas más cartas y reglas más complejas que otros juegos de cartas.

Y eso plantea una pregunta interesante: entre los juegos del mundo real (aquellos a los que la gente realmente juega, a diferencia de los hipotéticos que suelen considerar los teóricos de los juegos), ¿dónde cae Magic en complejidad?

Hoy recibimos una respuesta gracias al trabajo de Alex Churchill, investigador independiente y diseñador de juegos de mesa en Cambridge, Reino Unido; Stella Biderman en el Instituto de Tecnología de Georgia; y Austin Herrick en la Universidad de Pensilvania.

Su equipo ha medido la complejidad computacional del juego por primera vez al codificarlo de manera que pueda ser jugado por una computadora o una máquina de Turing. Esta construcción establece que Magia: la reunión es el juego del mundo real más complejo computacionalmente conocido en la literatura, dicen.

Primero, algunos antecedentes. Una tarea importante en informática es determinar si un problema se puede resolver en principio. Por ejemplo, decidir si dos números son primos relativos (en otras palabras, si su máximo común divisor es mayor que 1) es una tarea que se puede realizar en un número finito de pasos bien definidos y, por lo tanto, es computable.

En un juego ordinario de ajedrez, decidir si las blancas tienen una estrategia ganadora también es computable. El proceso consiste en probar todas las secuencias posibles de movimientos para ver si las blancas pueden forzar una victoria.

Pero si bien ambos problemas son computables, los recursos necesarios para resolverlos son muy diferentes.

Aquí es donde entra la noción de complejidad computacional. Esta es una clasificación basada en los recursos necesarios para resolver los problemas.

En este caso, decidir si dos números son primos relativos se puede resolver en varios pasos que son proporcionales a una función polinomial de los números de entrada. Si la entrada es x , el término más importante en una función polinomial es de la forma Cxn , donde C y norte son constantes. Esto cae en una clase conocida como P , donde P representa el tiempo polinomial.

Por el contrario, el problema de ajedrez debe resolverse por la fuerza bruta, y el número de pasos que esto toma aumenta en proporción a una función exponencial de la entrada. Si la entrada es x , el término más importante en una función exponencial es de la forma cnx , donde C y norte son constantes. Y como x aumenta, esto se vuelve más grande mucho más rápido que Cxn . Entonces esto cae en una categoría de mayor complejidad llamada EXP, o tiempo exponencial.

Más allá de esto, hay varias otras categorías de diversa complejidad, e incluso problemas para los que no existen algoritmos para resolverlos. Estos se llaman no computables.

Averiguar en qué clase de complejidad entran los juegos es un asunto complicado. La mayoría de los juegos del mundo real tienen límites finitos en su complejidad, como el tamaño de un tablero de juego. Y esto hace que muchos de ellos sean triviales desde el punto de vista de la complejidad. La mayoría de las investigaciones en la teoría algorítmica de juegos de los juegos del mundo real se han centrado principalmente en las generalizaciones de los juegos que se juegan comúnmente en lugar de las versiones de los juegos en el mundo real, dicen Churchill y compañía.

Por lo tanto, solo se sabe que unos pocos juegos del mundo real tienen una complejidad no trivial. Estos incluyen Dots-and-Boxes, Jenga y Tetris. Creemos que ningún juego del mundo real es conocido por ser más difícil que NP antes de este trabajo, dice Churchill y compañía.

El nuevo trabajo muestra que Magic: the Gathering es significativamente más complejo. El método es sencillo en principio. Churchill y compañía comienzan traduciendo los poderes y propiedades de cada carta en un conjunto de pasos que se pueden codificar.

Luego juegan un juego entre dos jugadores en el que el juego se desarrolla en una máquina de Turing. Y finalmente muestran que determinar si un jugador tiene una estrategia ganadora es equivalente al famoso problema de la detención en informática.

Este es el problema de decidir si un programa de computadora con una entrada específica terminará de ejecutarse o continuará para siempre. En 1936, Alan Turing demostró que ningún algoritmo puede determinar la respuesta. En otras palabras, el problema no es computable.

Entonces, el resultado clave de Churchill y compañía es que determinar el resultado de un juego de Magic no es computable. Este es el primer resultado que muestra que existe un juego del mundo real para el cual determinar la estrategia ganadora no es computable, dicen.

Es un trabajo interesante que plantea importantes preguntas fundamentales para la teoría de juegos. Por ejemplo, Churchill y compañía dicen que la principal teoría formal de juegos asume que cualquier juego debe ser computable. Magia: la reunión no se ajusta a las suposiciones comúnmente hechas por los informáticos al modelar juegos, dicen.

Eso sugiere que los científicos informáticos deben repensar sus ideas sobre los juegos, particularmente si esperan producir una teoría computacional unificada de los juegos. Claramente, Magic representa una mosca en el ungüento encantado en lo que a esto se refiere.

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

esconder