¿Es "Magic: The Gathering" el juego más complicado del mundo?

Magic: the Gathering es computacionalmente complejo, no "complicado"

Al menos no es "complicado" de una manera cuantificada por estas fuentes. Parecen estar confundiendo el significado basándose en una comprensión descuidada de un artículo científico.

La "complejidad computacional" es un concepto matemático, y el documento al que se hace referencia en estos artículos encuentra que M:tG es "Turing completo", que nuevamente es un término matemático con una definición precisa. En pocas palabras, las reglas de Magic se pueden usar para simular cualquier programa de computadora, con el tiempo suficiente.

Este es un resultado inteligente, pero no dice mucho acerca de si el juego es "complicado" de acuerdo con la comprensión cotidiana de la palabra. Por ejemplo, un artículo diferente de 2007 encontró un truco similar con el juego Minesweeper. La mayoría de la gente estaría de acuerdo en que Buscaminas es menos "complicado" que Magic, pero según estos documentos, los dos son igualmente "complejos desde el punto de vista informático".

Es difícil demostrar que es negativo, no parece haber un intento serio o autorizado de clasificar los juegos por "complicaciones". En cualquier caso, las afirmaciones en la pregunta no hacen referencia a uno. En cambio, confunden el significado de un término matemático utilizado en un artículo académico.

Los autores (Churchill et al) hacen una afirmación bastante fuerte:

Antes de este trabajo, no se conocía la existencia de juegos reales indecidibles.

Por "juego real" parecen querer decir un juego jugado con las reglas que se usan en la vida real, en lugar de modificaciones de las reglas. Aquí puede ser de donde los reporteros sacaron la idea de que Magic es "el juego más complicado", por lo que vale la pena examinarlo.

Las reglas de la mayoría de los juegos descartan inmediatamente la completitud de Turing, como señalan los propios autores:

Como la mayoría de los juegos tienen límites finitos en su complejidad (como el tamaño de un tablero de juego), la mayoría de las investigaciones en la teoría de juegos algorítmicos de los juegos del mundo real se han centrado principalmente en las generalizaciones de los juegos que se juegan comúnmente en lugar de las versiones del mundo real de los juegos .

(Agregué el enlace de Wikipedia).

Turing completo requiere un número ilimitado de estados y un número ilimitado de movimientos (referencia: cualquier texto de informática), por lo que la afirmación de que Magic, tal como se juega realmente, es Turing completo incluye la afirmación de que no hay límite en la duración, número de movimientos o tamaño (número de piezas en juego) de un juego en las reglas de la vida real. Por ejemplo, si solo se le permite usar cartas y fichas que se fabricaron antes de que comenzara el juego, entonces la cantidad de piezas en juego está limitada y el juego es (en palabras de los autores) "trivialmente decidible" como resultado. No sé si existen reglas de ese tipo en los torneos de Magic, pero espero que sí, ya sea explícitamente o como consecuencia de otras reglas explícitas.

En abstracto también afirman

que incluso reconocer quién ganará un juego en el que ninguno de los jugadores tiene que tomar una decisión no trivial para el resto del juego es indecidible.

La indecidibilidad requiere un conjunto infinito de instancias de problemas, por lo que esta afirmación no se aplica a los estados iniciales (mazos), ya que siempre están limitados en tamaño y contenido por las reglas. Se aplica a los juegos que comenzaron hace una cantidad ilimitada de movimientos, en los que los jugadores ya han tomado una cantidad ilimitada de decisiones no triviales, ya que esa es la única forma de crear una cantidad ilimitada de estados diferentes. (También se aplica solo si las reglas satisfacen los requisitos de integridad de Turing como se mencionó anteriormente).

También hacen la siguiente afirmación extraña:

[L]a teoría formal líder de los juegos estratégicos afirma que la memoria ilimitada requerida para simular una máquina de Turing por completo en un juego sería una violación de la naturaleza misma de un juego [9].

Regresan a esto más tarde y parecen creer que han demostrado que los modelos de juegos existentes son inadecuados para describir Magic, lo que definitivamente es incorrecto. La referencia [9] es "Lógica de restricción: un marco uniforme para modelar la computación como juegos" de Demaine y Hearn. Churchill et al pueden estar refiriéndose a la sección "¿Qué es un juego?" donde Demaine y Hearn dicen

Una diferencia clave [entre los juegos y las máquinas de Turing] está en el tamaño del estado: las máquinas de Turing tienen cintas infinitas, por lo que el estado en cualquier momento es ilimitado, mientras que siempre requerimos que el estado de un juego esté definido por una posición de tablero finita. . Podemos, por supuesto, limitar el tamaño de una cinta de máquina de Turing, o usar un modelo de circuito de computación, pero tales restricciones limitan el modelo de computación de la decidibilidad general. Por el contrario, mostramos que tales limitaciones no existen para los juegos.

No me queda claro lo que Demaine y Hearn están tratando de decir aquí. La afirmación de que "el estado en cualquier momento es ilimitado" es falsa a primera vista. El estado de una máquina de Turing en cualquier momento es finito (es decir, finitamente describible) de la misma manera que los juegos que modelan. Dado que dicen que "no existen tales limitaciones para los juegos", y luego usan Conway's Life (que durante mucho tiempo se sabe que es Turing completo) como ejemplo de un juego, parece claro que su marco admite juegos como Unbounded Magic, e incluso si no es así, no hay nada remotamente nuevo en la idea de modelar matemáticamente tales juegos.

Churchill et al en su conclusión incluso dicen

parece probable que sea necesario un modelo de juegos súper Turing para explicar la Magia .

(las cursivas son de ellos). Si se trata de una afirmación de que Magic podría violar la tesis de Church-Turing , y no veo otra forma de interpretarla, entonces es absurdo y no tiene ningún respaldo en el resto del preprint.

La respuesta hasta ahora se basa en la versión preliminar de arXiv. Este trabajo también se ha publicado como un documento de conferencia revisado por pares, según el CV de Biderman . Las actas completas de la conferencia, incluido este documento, están disponibles aquí . La versión publicada parece ser esencialmente la misma, incluso las afirmaciones más extremas del preprint, lo que me lleva a cuestionar la competencia de los revisores y editores.

Sí, la afirmación parece ser cierta en cierto sentido técnico preciso basado en nociones de informática teórica. Esto puede corresponder o no a la experiencia humana subjetiva de un jugador humano que compara cuán "complicado" consideran que es jugar a Magic: The Gathering versus algún otro juego.

1. Credibilidad de la investigación.

La afirmación del artículo de Forbes se basa en un artículo académico (" Magic: The Gathering Is Turing Complete ", de Churchill, Biderman y Herrick). Por lo tanto, tiene sentido preguntar primero si esa investigación es correcta. El artículo se publicó en las actas de la 10ª Conferencia Internacional sobre Diversión con Algoritmos (FUN 2021), una conferencia de informática. Por lo tanto, es revisado por pares, al menos según los estándares de una conferencia de informática. Aunque es bien sabido que las conferencias de matemáticas e informática no son tan estrictas con su proceso de revisión por pares como las revistas académicas (ya que operan con un cronograma apretado), eso le da a la investigación un buen nivel de credibilidad.

Además, la afirmación técnica del artículo es bastante plausible. No he leído los detalles, pero lo que está haciendo es bastante similar a las ideas estándar utilizadas en la literatura. Hay muchos artículos que discuten la complejidad computacional de varios juegos.

Basado en esos dos factores, asumiría que el resultado del artículo es correcto con una probabilidad bastante alta. Aunque existe la posibilidad de que los resultados sean incorrectos (los errores ocurren ocasionalmente en este tipo de investigación teórica), las posibilidades de que este sea el caso aquí parecen bastante pequeñas.

2. Contenido técnico de la demanda.

La afirmación técnica es que Magic: The Gathering es Turing-completo . Eso significa, en términos generales, que determinar el resultado de un juego dado su estado actual, suponiendo que los jugadores están jugando de manera óptima, es una pregunta cuya respuesta no solo es potencialmente muy difícil de encontrar, sino que incluso en principio es incognoscible . Entonces, en cierto sentido, eso significa que Magic no es solo el juego más complejo conocido, sino el juego más complejo que puede existir. Es decir, su complejidad puede ser igualada por algunos otros juegos, pero no puede ser superada.

La forma en que los autores del artículo muestran esto es mostrando que para responder a la pregunta sobre el resultado del juego uno tiene que ser capaz de responder a una pregunta diferente ("¿se detiene alguna vez una máquina de Turing dada?") para la cual ya se sabe que la respuesta es potencialmente incognoscible (en lenguaje técnico, el problema de la detención es indecidible ). Este tipo de argumento es estándar en informática teórica, aunque los detalles específicos para llevarlo a cabo varían de un caso a otro.

3. Resumen.

Los artículos en los medios de comunicación que tratan de hacer que la investigación académica sea “accesible” para el público, por lo general no logran transmitir con precisión lo que afirma la investigación; a menudo incluso tratan deliberadamente de sensacionalizar los resultados y hacer que suenen lo más emocionantes (y me atrevo a decir, clic-baity) como sea posible, lo que necesariamente tiene el costo de una mayor pérdida de precisión y matiz. El artículo de Forbes citado aquí no es una excepción, por lo que ciertamente se justifica cierto escepticismo saludable. En particular, los autores originales del estudio no afirmaron que "La magia es el juego más complicado", sino que hicieron una afirmación técnica precisa.

Habiendo dicho eso, no es irrazonable interpretar su afirmación como diciendo fundamentalmente que Magic es, en un sentido teórico, tan complicado como cualquier juego puede esperar ser.