'Magic: The Gathering' lleva más de 25 años siendo el rey de los juegos de cartas. Hechizos, criaturas, objetos mágicos... el juego de cartas coleccionables de Wizard of the Coast congrega a millones de personas en todo el mundo, pero además de su popularidad, con serie de Netflix incluida, también esconde una complejidad muy elevada.
Tal es así, que Alex Churchill, diseñador de juegos de mesa de Cambridge y Stella Biderman, matemática del Instituto de Tecnología de Georgia publicaban un estudio en el portal arxiV donde catalogaban a 'Magic: The Gathering' como el juego más complejo del mundo, computacionalmente hablando.
No hay algoritmo infalible para ganar una partida de Magic
Los juegos son un ecosistema perfecto para enseñar a las máquinas a entrenar su inteligencia. Es el caso de DeepMind con AlphaGo o OpenAI con Dota 2, pero los científicos nos han sorprendido con su hallazgo. No es otro que con Magic, el juego más complejo del mundo. Y para comprobarlo crearon una máquina de Turing, le dieron un mazo y la hicieron jugar a 'Magic: The Gathering'.
¿Qué es una máquina de Turing? Básicamente un ordenador que puede ejecutar los métodos matemáticos clásicos para resolver problemas. En el caso de Magic, los investigadores adaptaron una máquina que ya fue fabricada para tal propósito en 2011.
Como explica Stella, el programa es capaz de jugar a Magic. La máquina recibe como 'input' una carta y devuelve un movimiento. En base a esto, los investigadores pueden predecir cuántos movimientos harán falta para derrotar al oponente o durante cuánto tiempo es óptimo seguir con esa carta. Lo que ocurre es que no todos los problemas dentro del juego de Magic pueden ser resueltos por un algoritmo.
En las simulaciones realizadas con la máquina de Turing que juega a Magic, descubrieron que es matemáticamente imposible para el ordenador jugar a Magic óptimamente. Es decir, no hay algoritmo que sea capaz de en base a un 'input' devolver el mejor movimiento.
Según los investigadores, "Magic es el primer juego conocido y jugado en el mundo físico donde tenemos un sistema no computable". A lo que añaden que "además de mostrar que el juego estratégico más óptimo en Magic no es computable, también tenemos que la mera evaluación de las consecuencias deterministas de movimientos pasados en Magic no es computable. La complejidad total del juego sigue siendo una pregunta abierta, al igual que muchos otros aspectos computacionales en 'Magic: The Gathering'".
Debemos tener en cuenta que hablamos a nivel general. No todas las partidas de Magic producirán un resultado no computable y en muchas ocasiones la máquina sí sabrá determinar los mejores movimientos. Sin embargo, la importancia de esta investigación es que se produce el hecho de ser el único juego donde existe la posibilidad, dentro del marco de las reglas, en que el juego no sea computable.
Esto abre toda una serie de puertas en el campo de la teoría de juegos y la inteligencia artificial. Según los responsables del estudio: "'Magic: The Gathering' no se ajusta a las suposiciones que suelen hacer los informáticos al modelar juegos. Creemos que el juego más óptimo en Magic es mucho más difícil de lo que implica este resultado. Dejaremos la verdadera complejidad de Magic y su reconciliación con las teorías de juegos existentes para futuras investigaciones".
'Magic: The Gathering' es Turing completo
El ajedrez es más complejo que las damas, pero los dos son juegos computables. Si bien, en el caso del primero el ejercicio de fuerza bruta necesario para ganar es enorme. Sin embargo, hay juegos donde no es cuestión de fuerza bruta, sino que todavía no hay un algoritmo capaz de establecer cómo se gana. Son los llamados "no computables" y Magic sería uno de ellos, con sus más de 2.000 reglas y más de 19.000 cartas únicas.
Solo unos pocos juegos disponen de una complejidad no trivial, es el caso de algunos como el Jenga, el Tetris u otros videojuegos como 'Super Smash Bros' o 'Doom'. Pero 'Magic: The Gathering' sería el primer juego físico que entraría en esta categoría. No se descarta que haya otros juegos físicos más complejos, pero de los estudiados, Magic ha resultado ser el más complejo y el primero de estas características.
Ya en 2011, Alex Churchill explicó que 'Magic: The Gathering' era un juego Turing completo. Lo hizo a través de una simulaciones pero no fue hasta 2019 cuando se construyó la base matemática para demostrarlo.
Finally got around to reading the "MTG is Turing complete" paper by @Stroodle76, @alextfish, and @BlancheMinerva. It was well-written and, I believe, correct.
— Frank Karsten (@karsten_frank) May 21, 2019
I can't write a better ELI5 than one of the authors in the thread linking their paper: https://t.co/NT7P31Y4tp pic.twitter.com/jnDecftuTE
¿Qué significa que sea Turing completo? Se trata de una manera matemática de decir que se podría utilizar el juego como una máquina de Turing y por tanto actuar como base para solucionar cualquier tipo de problemas. Los matemáticos podrían trasladar sus algoritmos a un mazo de Magic y teóricamente utilizarlo como un método de computación. Aunque claro está, esta tarea sería increíblemente difícil de programar y consumiría un tiempo inviable.
El mero hecho de que 'Magic: The Gathering' sea un juego no computable representa nuevas vías de investigación en la teoría unificada de juegos. El artículo inicialmente fue publicado en el portal arXiv en marzo de 2019, siendo la investigación revisada posteriormente en una segunda versión durante la 'IEEE Conference on Games'. A finales de 2020, su trabajo fue anunciado en la conferencia 'Fun with Algorithms'. Desde entonces, Alex Churchill, Stella Biderman y Austin Herrick dan conferencias explicando su investigación.
Ver 29 comentarios
29 comentarios
pableras
Emmmm
No, creo que es simplemente cuestión de azar y opciones. La cantidad de opciones que tú tienes para hacerte un mazo y la que tiene tu oponente. La cantidad de opciones que tienes para bajar cartas. Y la cantidad de opciones que tienes para combinarlas . Ya llevamos unos cuantos millones de posibilidades. Y a eso sumamos el azar, que las cartas no siempre salen en el mismo orden.
En ese sentido, por ejemplo, el ajedrez, siempre son las mismas piezas que siempre empiezan en el mismo sitio y que siempre hacen los mismo movimientos. Por eso computacionalmente es muchísimo más sencillo.
Pero no creo que al jugarlos tengan el mismo nivel de complejidad.
zasaz
Pues porque no ha probado de jugar con un comander de fragmentados... (el que entiende, entiende)
jmoran2611
Un apunte, arXiv no es una revista, es un portal donde publicar de forma abierta articulos cientificos.
pererecuda
Magic, el juego por excelencia del Pay to Win. Yo lo jugué bastante, pero me di
cuenta que era pasta para ganar, comprar las cartas más poderosas, etc.
Un sacacuartos en toda regla.
alexandrorodriguez
Para mí lo interesante es que fuera un Turing completo, como el juego de la vida.
ernestofabianojedazepeda
me imagino que en dota para ser justos son 5 ia jugando vs 5 player, por que una ia que controle 5 personajes a la ves tendra ventaja en rotaciones team fight,etc.
humboy
'Magic: The Gathering' es el juego más complejo del mundo, tanto que ni siquiera las máquinas saben cómo ganar" Bravo lumbreras, se llama azar!
Me encantan estos títulares tan epicos, "ni siquiera las máquinas saben como ganar,"... Wooow...como si fuese una virtud intrínseca del propio sistema de juego, en fin...
jaimebcn
Pues fíjate que yo dejé de jugar (de esto hace años ya, allá por el 97) por que se me hacían todas las partidas tremendamente repetitivas.
Con una baraja rojo-negra rápida y optimizada a 40 cartas que era el mínimo... meh.
Supongo que ahora habrá más ediciones, más cartas, nuevas normas, etc. Pero tampoco creo que diste mucho de cómo funcionaba el juego originalmente.
lopez
Pues no veo que valga como test de Turing, anda que no habrá humanos que jugarán peor con ese mismo mazo, y acaben jugando una carta al azar por no saber qué hacer.
juan ignaciocaballer
Duda,
El Go es computable? Tenía entendido que el gran mérito de alphago era que había vencido al mejor humano en un juego donde no es posible evaluar todas posibilidades. Aunque magic es más complejo en cuanto a mecánica que el Go supongo.
Luis
Hasta que Google deepmind quiera vencer al juego.
shur_it
Y digo yo, ¿el póker, ya sea en sus variantes texas holdem u Omaha, es acaso computable?
Teniendo en cuenta las casi infinitas combinaciones de cartas, el factor psicológico de los rivales, el tamaño de las apuestas, el factor azar...
Se sabe que desde hace años hay Bots que son capaces de ganar en Head's Up (1 vs 1), pero no son capaces de ser óptimos en partidas con mayor cantidad de jugadores debido a que las posibilidades crecen exponencialmente
dduusagi
Bueno, se podrían poner a probar más juegos de cartas y creo que practicamente todos lo serían, por el mero hecho de tener un factor azar con el que tienes que jugar.
Magic es de los juegos más sencillos computacionalmente que me vienen a la cabeza, contando solo juegos que actualmente están en funcionamiento.
Le das Leyenda de los 5 Anillos a un pc y lo mismo explota.