¿Se ha completado Magic: the Gathering Turing?

24

Una pregunta muy específica, lo sé, y dudo que sea respondida por alguien que no esté familiarizado con las reglas de Magic. Publicación cruzada en Draw3Cards . Aquí están las reglas integrales para el juego Magic: the Gathering . Vea esta pregunta para obtener una lista de todas las cartas mágicas. Mi pregunta es: ¿está completo el juego Turing?

Para más detalles, consulte la publicación en Draw3Cards .

ripper234
fuente
1
(1) ¿Cuál es la entrada? ¿Asumes que conoces el contenido y el orden de las cartas en los mazos de ambos jugadores? (2) Para analizar su complejidad, un problema debe tener infinitas entradas posibles. Por ejemplo, no podemos decir que el ajedrez es EXP-complete (incluso si lo decimos, significa que la generalización del ajedrez a un tablero n × n es EXP-complete). ¿Cómo generalizas el juego? (3) El juego puede ser demasiado complicado para analizar su complejidad, pero no lo sé.
Tsuyoshi Ito
1
@Daniel: Gracias. De hecho, también lo comprobé, pero no estaba seguro de si alguien quiere analizar el juego donde cada carta, excepto las cartas de tierra, está restringida a un máximo de 4 copias y solo puede crecer la cantidad de cartas de tierra.
Tsuyoshi Ito
1
@Daniel: No estoy seguro si la lógica funciona de esa manera porque hay varios tipos diferentes de cartas de tierra. Después de todo, el juego original en sí mismo puede ser lo suficientemente complicado como para completar Turing. Lo que no estoy seguro es si el autor de la pregunta realmente quiere analizar el juego donde casi todas las cartas de un mazo son necesariamente cartas de tierra. Esperaré a que el que pregunta responda.
Tsuyoshi Ito
44
@Daniel: ¡Esa no es una objeción razonable! La mayoría de las reducciones de dureza para juegos generan algo que se parece más a la reducción que el juego original. (Los ciclos hamiltonianos no surgen naturalmente en los borradores, por ejemplo).
Jeffε
1
@ Tsuyoshi - Creo que eso sería preguntar si Magic es decidible. Para que esta pregunta sea significativa, puede asumir información perfecta: se revelan todas las bibliotecas y manos, y todos los lanzamientos aleatorios de monedas y similares están predeterminados. ¿Es posible determinar desde cada posición de Magic quién es el ganador?
ripper234

Respuestas:

21

Alex Churchill (@AlexC) ha publicado una solución que no requiere la cooperación entre los jugadores, sino que modela la ejecución completa de una máquina Turing universal con dos estados y 18 símbolos de cinta. Para más detalles, consulte https://www.toothycat.net/~hologram/Turing/ [ archive ].

revs Jeffε
fuente
1
El enlace está muerto para mí. ¿Deberíamos recrear la solución en la respuesta para que esté completa?
Artem Kaznatcheev
1
La solución se aloja en toothycat.net/~hologram/Turing por el momento.
AlexC
15

Ok, tengo una solución que evita el problema de quemadura de maná que encontré. Esto es una especie de truco, ya que necesito suponer que los jugadores pueden identificar tierras específicas, lo que no creo que se aborde en las reglas. En la práctica, este es el caso, ya que se pueden organizar en una línea según el orden en que se reproducen.

Primero, la descripción completa del problema desde el sitio Draw3Cards:

Una respuesta positiva estaría compuesta de estos componentes:

  1. Una función computable fM desde máquinas de Turing hasta mazos mágicos ordenados (donde importa el orden de la biblioteca)
  2. Dos estrategias deterministas y computables bien definidas para jugar Magic (que no dependen del mazo). Llamémoslos Estrategia TS (Estrategia de Turing) y Estrategia IS (Estrategia de entrada).
  3. Una manera computable de codificar cualquier cadena de ceros y unos como un mazo de entrada mágica. Una de esas formas sería tomar el número de Gödel de la cadena y poner tantas islas en el mazo de Entrada.

La condición adicional que debe cumplirse es esta: dado un Turing Machines TM, consideremos el resultado del juego Magic entre la estrategia TS jugando con el mazo fM (TM) contra la estrategia TI jugando con el mazo fI (I), cuando las bibliotecas están no barajado antes de que comience el juego. Este juego debe ser ganado por el primer jugador si y solo si TM (I) = verdadero.

Así que aquí está la idea. Tenemos 2 jugadores, A y B. B proporcionará la entrada, mientras que A implementará directamente una máquina de Turing. Los mazos estarán compuestos casi en su totalidad por tierra, pero también por la carta Gemstone Array para anular la quema de maná. A tendrá 3 tipos de tierra: islas, montañas y bosques. La idea básica es usar tierra explotada para representar un 1 y tierra sin explotar para representar un 0. Las islas se usarán para representar el estado de la cinta, las montañas para indexar la posición actual a lo largo de la cinta y los bosques para representar el estado interno de 24 máquina de Turing del símbolo del estado 2 (creo que hay una universal debido a Rogozhin).

25=32>242m+1

25=32>242m+1

Estrategia: A y B juegan una tierra por turno en el orden en que son sorteados. Cuando cada uno ha dibujado 4 bosques, juegan Gemstone Artifact. Nota A va primero, por lo que ya tiene una isla cuando B dibuja juega su primera carta de entrada.

A y B simplemente continúan colocando sus cartas en orden hasta que B haya agotado sus llanuras y pantanos y juegue su primera isla. En su siguiente intento, A por todo lo que toca su isla i-ésima si Bs ith Input Land era un pantano. A inicializa su máquina de turing tocando su primer Bosque y Montaña. Si ha tocado un número impar de cartas, toca su forrest extra y usa todo este maná para agregar fichas a la matriz de piedras preciosas. A partir de aquí, el juego procede de la siguiente manera: B usa su turno para reflejar simplemente el estado del maná de A. B toca su i-ésima tierra de entrada si se toca la i-ésima isla de A. De manera similar, B toca su ith Bosque (Montaña) si se toca el ith Bosque (Montaña) de A. Como A siempre toca un número par de cartas, B también lo hace, y el maná se usa para agregar fichas a la matriz de piedras preciosas.

En el turno de A, todo el maná de A queda sin explotar, por lo que A observa el estado del maná de B y representa el estado del maná de A en el turno anterior. A aplica la regla de transición de acuerdo con la máquina universal (24,2) al estado de B para obtener su nuevo estado.

El juego continúa de esta manera hasta que la máquina se detiene. En este punto, A coloca sus montañas en el estado reservado "terminado" (el estado sin explotar). Si la máquina de Turing se detuvo en un estado de aceptación, B copia el estado de las montañas de A, pero aprovecha todas sus tierras restantes descuidando el uso de la matriz de piedras preciosas, comenzando así el proceso de suicidio por quema de maná. En el turno de A, si las montañas de B están en el estado "terminado", y todas las otras tierras de B están aprovechadas, A simplemente no hace nada (tenga en cuenta que sus montañas están automáticamente en el estado "terminado"). Si las montañas de A están en el estado terminado, pero no se toca nada más, B continúa suicidándose por quema de maná. Esto se repite hasta que B esté muerto.

Sin embargo, si la máquina termina en el estado de rechazo, B deja todas sus cartas sin explotar. Si todas las cartas de B están sin explotar, A toca todas sus cartas, comenzando el mismo proceso de suicidio por quema de maná. Si las cartas que no son de Montaña de A están todas giradas, y las montañas sin explotar, B deja todas sus cartas sin explotar. Esto llevará a A a continuar el suicidio de quema de maná hasta que pierda el juego.

Esto debería satisfacer los criterios solicitados en la pregunta y, por lo tanto, cuando se permite este orden, creo que el juego se está completando en el sentido descrito en la pregunta.

Joe Fitzsimons
fuente
2
Guay. Un pensamiento adicional: siempre que cualquier jugador toque más de 1 tierra por turno, puedes usar cargas en la matriz de piedras preciosas para evitar la quema de maná. Por ejemplo, si necesito aprovechar 3 tierras, convierto dos maná en una carga, gasto la carga para generar un maná, luego gasto los dos maná restantes para crear una nueva carga. - por supuesto, ya resolviste este problema de todos modos. :)
Daniel Apon
2
Aewsome! También podría ser más fácil simular una máquina de 2 contadores (usando diferentes tipos de maná como contadores) en lugar de simular directamente una máquina de Turing: en.wikipedia.org/wiki/…
Jeffε
3
Tu reducción también implica que Magic (cooperativo) con un número finito de cartas es PSPACE-hard.
Jeffε
3
@ Joe: ya no hay quema de maná en Magic. Podrías usar Platinum Angel para evitar perder debido a la falta de cartas en tu cementerio.
ripper234
1
@ Joe: te perdiste mi comentario anterior de que el concepto de quema de maná se ha eliminado por completo de las reglas. Puedes arreglarlo haciendo que cada jugador tenga una copia de Fireball en su mazo.
ripper234
7

Alex Churchill, Stella Biderman y Austin Herrick publicaron este artículo mostrando que Magic is Turing Complete

Resumen: Magic: The Gathering es un popular y famoso juego de cartas intercambiables sobre combate mágico. En este artículo mostramos que el juego óptimo en la magia del mundo real es al menos tan difícil como el problema de detención, resolviendo un problema que ha estado abierto durante una década [1], [10]. Para hacer esto, presentamos una metodología para incorporar una máquina arbitraria de Turing en un juego de magia de modo que el primer jugador tenga la garantía de ganar el juego si y solo si la máquina de Turing se detiene. Nuestro resultado se aplica a cómo se juega Magic real, se puede lograr usando mazos legales de torneo de tamaño estándar, y no se basa en estocasticidad o información oculta. Nuestro resultado también es muy inusual ya que todos los movimientos de ambos jugadores son forzados en la construcción. Esto muestra que incluso reconocer quién ganará un juego en el que ninguno de los jugadores tiene una decisión no trivial para el resto del juego es indecidible. Concluimos con una discusión sobre las implicaciones para una teoría computacional unificada de los juegos y comentarios sobre la jugabilidad de tal tablero en un torneo.

DerMolly
fuente