Una nueva prueba nos muestra que ningún algoritmo puede determinar al ganador de este famoso juego de cartas coleccionables.
Magic: The Gathering es un juego de cartas en el que los jugadores representan a magos que lanzan hechizos, invocan a las criaturas y explotan los objetos mágicos para derrotar a sus oponentes.
En este juego, dos o más jugadores montan cada uno un mazo de 60 cartas con diferentes poderes. Eligen estas barajas de un conjunto de unas 20.000 cartas creadas a medida que el juego evolucionaba. Aunque es similar a los juegos de fantasía de rol como Dungeons and Dragons, tiene significativamente más cartas y reglas más complejas que otros juegos de cartas.
Y esto plantea una pregunta interesante: entre los juegos del mundo real (aquellos a los que la gente realmente juega, en contraposición a los hipotéticos que los teóricos del juego suelen considerar), ¿dónde recae la complejidad de la magia?
Hoy obtenemos una respuesta gracias al trabajo de Alex Churchill, un investigador independiente y diseñador de juegos de mesa de Cambridge, Reino Unido; Stella Biderman del Instituto de Tecnología de Georgia; y Austin Herrick de la Universidad de Pennsylvania.
Su equipo ha medido por primera vez la complejidad computacional del juego codificándolo de manera que pueda ser jugado por un ordenador o una máquina de Turing. «Esta construcción establece que Magic: The Gathering es el juego del mundo real más complejo computacionalmente conocido», dicen.
Primero, algunos antecedentes. Una tarea importante en la informática es determinar si un problema puede ser resuelto en principio. Por ejemplo, decidir si dos números son relativamente primos (en otras palabras, si su mayor divisor común es mayor que 1) es una tarea que puede hacerse en un número finito de pasos bien definidos y por lo tanto es computable.
En un juego de ajedrez ordinario, decidir si las blancas tienen una estrategia ganadora también es computable. El proceso implica probar cada posible secuencia de movimientos para ver si las blancas pueden forzar una victoria. Pero mientras que 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 relativamente primos puede resolverse en un número de pasos que es proporcional a una función polinómica de los números de entrada. Si la entrada es x, el término más importante en una función polinómica es de la forma Cxn, donde C y n son constantes. Esto cae dentro de una clase conocida como P, donde P significa tiempo de polinomio.
Por el contrario, el problema de ajedrez debe ser resuelto por la fuerza bruta, y el número de pasos que ésta da 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 n son constantes. Y a medida que x aumenta, esto se hace más grande mucho más rápido que Cxn. Así que 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 complejidad variable, e incluso problemas para los que no hay algoritmos para resolverlos. Estos se llaman no computables.
Resolver en qué clase de complejidad caen 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 del mundo real ha mirado principalmente a las generalizaciones de los juegos comúnmente jugados más que a las versiones de los juegos del mundo real», dicen Churchill y compañía.
Así que sólo unos pocos juegos del mundo real se sabe que tienen una complejidad no trivial. Estos incluyen Dots-and-Boxes, Jenga y Tetris. «Creemos que no se conoce ningún juego del mundo real que sea 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 pueden ser codificados.
Luego juegan un juego entre dos jugadores en el que la obra 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 informática.
Este es el problema de decidir si un programa de ordenador con una entrada específica terminará de funcionar 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.
Así que el resultado clave de Churchill y compañía es que determinar el resultado de un juego de Magia 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 cuestiones fundamentales para la teoría del juego. Por ejemplo, Churchill y compañía dicen que la principal teoría formal de juegos asume que cualquier juego debe ser computable. «Magic: The Gathering no encaja con las suposiciones comúnmente hechas por los científicos informáticos al modelar juegos», dicen.
Esto sugiere que los informáticos deben replantearse sus ideas sobre los juegos, especialmente si esperan producir una teoría computacional unificada de los juegos. Claramente, la magia representa una mosca en el ungüento encantado en lo que a esto se refiere.
Si te apetece empezar en el apasionante mundo de Magic The Gathering tienes varios packs y kits de iniciación con los que puedes empezar a jugar desde que los recibas:
Y para que vayas saboreando, te dejo un video tutorial de cómo jugar a Magic. En éste video te explican las nociones básicas para que aprender a jugar a Magic The Gathering sea muchísimo más fácil:
Y si eres un friki de los juegos de mesa y cartas coleccionables, también puedes pasarte por nuestras otras secciones y ver más productos que te pueden gustar:
Imagen principal por Wayne Low, via @wayneshin

