Seleccionar página

Es tan complicado que aunque tengas toda la información de antemano, no puedes saber realmente quién ganará.

Magic the Gathering es un popular y famoso juego de cartas coleccionables sobre combates mágicos. Esencialmente, tienes cartas con criaturas, hechizos y otros recursos que usas para derrotar a tu oponente. Formalmente, es un juego de cartas estocástico de suma cero para dos jugadores con información imperfecta que lo coloca en la misma categoría que juegos como el póquer y los corazones.

Para los informáticos, un asunto de interés es averiguar si los problemas pueden ser computables o no, y esto incluye los juegos. Tome tic-tac-toe por ejemplo: es un juego realmente simple y computable. Haga que dos algoritmos se enfrenten a un bazillion de juegos y obtendrán un bazillion de sorteos. Pero pasemos a algo más complicado, como el ajedrez. En teoría, el ajedrez es computable; puedes resolverlo Sin embargo, tener los recursos para hacerlo es un problema completamente nuevo. Si bien los algoritmos de ajedrez pueden derrotar fácilmente a los mejores jugadores humanos del mundo, todavía estaban muy, muy lejos de resolver el ajedrez.

Sin embargo, desde el punto de vista de la complejidad, el ajedrez tiene un sólido límite en su complejidad, dado por el tamaño de los tableros y las piezas. La mayoría de los juegos del mundo real tienen límites finitos en su complejidad, pero algunos juegos del mundo real tienen
Se ha encontrado que tiene una complejidad no trivial, incluidos Dots-and-Boxes, Jenga y Tetris. Magic the Gathering , como resultado, es más complejo que todos ellos.

Para probar esto, los investigadores primero tradujeron los poderes y propiedades de las 20,000 cartas de Magic . La mecánica de algunas de las cartas requiere información del jugador, como nombrar un número o elegir si jugar o no una acción. En algún momento el estudio dice:

Por ejemplo, Kazuul Warlord dice Siempre que Kazuul Warlord u otro Aliado entre al campo de batalla bajo tu control, puedes poner un contador +1/ + 1 sobre cada Aliado que controles.

Esto hace que las cosas sean muy extrañas, ya que el objetivo de los investigadores era esencialmente cargar el juego en una máquina de Turing, esencialmente, crear un motor de juego Magic the Gathering . Entonces, para los fines de este estudio, se eliminaron estas tarjetas. Aun así, el juego siguió siendo increíblemente complejo.

El equipo demostró no solo que Magic es el juego del mundo real más complejo que conocemos, sino que también no es computable, a diferencia de juegos como el ajedrez.

En 1936, Alan Turing atacó el llamado problema de la detención. El problema de la detención pregunta: dada una entrada y un programa de computadora arbitrario, ¿el programa se detendrá (detendrá) o se ejecutará para siempre? Turing demostró que los algoritmos no pueden determinar la respuesta, por lo que el problema no es computable.

Esta construcción establece que Magic: The Gathering es el juego del mundo real más complejo computacionalmente conocido en la literatura, escriben los investigadores. En pocas palabras, no hay una estrategia ganadora, continúan los investigadores.

Además de mostrar que el juego estratégico óptimo en Magic no es computable, también muestra que simplemente evaluar las consecuencias deterministas de movimientos pasados ​​en Magic no es computable. La complejidad total del juego estratégico óptimo sigue siendo una pregunta abierta, al igual que muchos otros aspectos computacionales de Magic. Por ejemplo, un jugador parece tener infinitos movimientos disponibles desde algunos estados del tablero de Magic, continúa el estudio. No está del todo claro si un juego del mundo real puede tener movimientos infinitamente significativos , pero indica una tremenda complejidad computacional.

Además de dar a los jugadores de Magic the Gathering derechos de jactancia, el trabajo en sí es importante por varias razones. Para empezar, tener un juego de cartas donde no hay una estrategia ganadora claramente definida es impresionante. Además, esto da una señal a todos los científicos informáticos que intentan modelar juegos: Magic es un hueso duro de roer y no parece comportarse de acuerdo con las suposiciones comunes.

Este es el primer resultado que muestra que existe un juego del mundo real para el cual determinar la estrategia ganadora no es computable.

Conjeturamos que el juego óptimo en Magic es mucho más difícil que este resultado por sí solo.
implica, y dejar la verdadera complejidad de Magic y la reconciliación de Magic con las teorías de juegos existentes para futuras investigaciones, concluye el estudio.

El estudio ha sido publicado en arXiv.

"