'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