El juego de cartas “Magic: The Gathering” es el más difícil de todos, afirman matemáticos | N+1: artículos científicos, noticias de ciencia, cosmos, gadgets, tecnología
El juego de cartas “Magic: The Gathering” es el más difícil de todos, afirman matemáticos
Magic: The Gathering
Un equipo de matemáticos ha demostrado que el juego de cartas Magic: The Gathering es el más difícil de todos los juegos. Resultó que la existencia de un algoritmo que calcula si un jugador dado ganará es equivalente al problema de la parada: el problema clásico de la teoría de los algoritmos, cuya insolubilidad fue probada por Alan Turing en 1936. Así, Magic: The Gathering se convierte en un juego incomparablemente complejo, el estudio fue publicado en arXiv.org.
En informática teórica, una máquina de Turing se usa para formalizar el concepto de algoritmo: una computadora abstracta que consiste en una cinta infinita dividida en celdas discretas y un dispositivo de control que puede leer información y escribirla desde una cinta. Un dispositivo puede estar en un número final de estados internos estrictamente definido, variando el cual puede implementar diferentes algoritmos.
Al usar este modelo teórico, Alan Turing en 1936 demostró la imposibilidad de resolver el problema de la parada, es decir, la imposibilidad de la existencia de un algoritmo que pudiera predecir de antemano si una máquina de Turing dada dejaría de calcular esta información de entrada o realizaría infinitamente operaciones. En otras palabras, el algoritmo de la máquina de Turing que resuelve el problema de la parada no es computable.
La vida real
La mayoría de los problemas del mundo real son computables y generalmente se clasifican de acuerdo con su intensidad de recursos. Las más simples son las tareas resueltas en tiempo polinomial, que juntas forman el conjunto P. Para ellas, el número de pasos necesarios de la máquina de Turing para obtener una respuesta no crece más rápido que nk, donde k es una constante y n es el número de celdas ocupadas por los datos de entrada en la cinta. Un ejemplo de una tarea tan simple es el cálculo de si dos enteros positivos dados son coprimos, es decir, si tienen divisores comunes distintos de uno.
Un ejemplo de una categoría de problemas mucho más complejos es EXP, que incluye problemas que se pueden resolver en tiempo exponencial, es decir, el número de operaciones requeridas no crece más rápido que kn, y tal función para una n suficientemente grande crecerá mucho más rápido que nk independientemente de k.
Existen muchas clases de algoritmos de complejidad intermedia que pueden diferir no solo por el tiempo empleado, sino también por el espacio, es decir, el número de celdas utilizadas para los cálculos. También se conocen tareas para las que no existe el algoritmo, como el problema de la parada.
Además de los cálculos matemáticos abstractos por clases de complejidad, uno puede clasificar varios juegos, por ejemplo, ajedrez, que se encuentran en EXP. Al mismo tiempo, la gran mayoría de los juegos reales estudiados por los matemáticos tienen un límite superior de complejidad y no alcanzan problemas indiscutibles, por lo que la mayoría de los estudios sobre teoría de juegos algorítmicos se consideran en general generalizaciones de juegos estándar, en lugar de sus versiones existentes.
La excepción
Pero ahora el investigador independiente Alex Churchill de Gran Bretaña, así como los matemáticos Stella Biderman del Instituto de Tecnología de Georgia y Austin Herrick de la Universidad de Pennsylvania presentaron la formalización matemática del juego Magic: The Gathering.
Los autores, utilizando mapas y reglas existentes para dos jugadores, implementaron una máquina de Turing universal, y descubrieron que determinar el ganador en este caso es equivalente al problema de detener esta máquina. Por un lado, por primera vez se muestra un ejemplo de un juego real en el que la definición de una estrategia ganadora no es computable, y por el otro, demuestra la imposibilidad en el caso general de comprobar la equivalencia de diferentes estrategias en un juego dado.
Además del interés en el contexto de este juego, el nuevo resultado también puede tener un impacto significativo en los fundamentos de la teoría de juegos, ya que el punto de vista prevaleciente de hoy sugiere que el resultado de cualquier juego debería ser teóricamente computable. Según los propios autores, Magic: The Gathering no coincide con las hipótesis que se usan comúnmente al modelar juegos de computadora.
Victor Román
Esta noticia ha sido publicada originalmente en N+1, ciencia que suma.
Sobre N+1: Es la primera revista online de divulgación científica y tecnológica que permite la reproducción total o parcial de sus contenidos por medios de comunicación, bloggers e influencers, realizando la mención del texto y el enlace a la web: “Esta noticia ha sido publicada originalmente en la revista N+1, ciencia que suma: www.nmas1.org”.
This content was originally published here.
El juego de cartas “Magic: The Gathering” es el más difícil de todos, afirman matemáticos Magic: The Gathering Un equipo de matemáticos ha demostrado que el juego de cartas Magic: The Gathering es el más difícil de todos los juegos. Resultó que la existencia de un algoritmo que calcula si un jugador dado ganará es…
El juego de cartas “Magic: The Gathering” es el más difícil de todos, afirman matemáticos Magic: The Gathering Un equipo de matemáticos ha demostrado que el juego de cartas Magic: The Gathering es el más difícil de todos los juegos. Resultó que la existencia de un algoritmo que calcula si un jugador dado ganará es…