Czy Magic: the Gathering Turing jest ukończony?

Zdaję sobie sprawę z bardzo konkretnego pytania i wątpię, że odpowie na nie każdy, kto nie jest zaznajomiony z zasadami Magii. Przeniesiony do Draw3Cards . Oto kompleksowe zasady gry Magic: the Gathering . Zobacz to pytanie, aby uzyskać listę wszystkich magicznych kart. Moje pytanie brzmi - czy gra Turing jest ukończona?

Aby uzyskać więcej informacji, zobacz post na Draw3Cards .

Alex Churchill (@AlexC) opublikował rozwiązanie, które nie wymaga współpracy między graczami, ale modeluje pełne wykonanie uniwersalnej maszyny Turinga z dwoma stanami i 18 symbolami taśmy. Aby uzyskać szczegółowe informacje, zobacz https://www.toothycat.net/~hologram/Turing/ [ archiwum ].

Ok, mam rozwiązanie, które pozwala uniknąć problemu z wypalaniem many, na który wpadłem. Jest to rodzaj włamania, ponieważ muszę założyć, że gracze mogą zidentyfikować określone ziemie, co nie wydaje się, aby było to uregulowane w zasadach. W praktyce jest tak, ponieważ można je ustawić w linii na podstawie kolejności, w jakiej są odtwarzane.

Po pierwsze, pełny opis problemu ze strony Draw3Cards:

Pozytywna odpowiedź składałaby się z następujących elementów:

1. Obliczalna funkcja fM od Turing Machines do uporządkowanych talii magicznych (tam gdzie ma znaczenie kolejność bibliotek)
2. Dwie dobrze zdefiniowane deterministyczne i obliczalne strategie gry w Magię (które nie zależą od talii). Nazwijmy je Strategia TS (Strategia Turinga) i Strategia IS (Strategia wprowadzania).
3. Obliczalny sposób fI do kodowania dowolnego ciągu zer i jedynek jako talia Magic Input. Jednym z takich sposobów byłoby pobranie numeru Gödela z łańcucha i umieszczenie tylu wysp na pokładzie wejściowym.

Dodatkowy warunek, który powinien zostać spełniony, to: biorąc pod uwagę maszynę Turing Machines, rozważmy wynik gry Magic między strategią TS grającą talią fM (TM) a strategią TI grającą talią fI (I), gdy biblioteki są nie tasowane przed rozpoczęciem gry. Ta gra powinna zostać wygrana przez pierwszego gracza wtedy i tylko wtedy, gdy TM (I) = true.

Oto pomysł. Mamy 2 graczy, A i B. B dostarczy dane wejściowe, a A bezpośrednio wdroży maszynę Turinga. Talia będzie się składać prawie w całości z ziemi, ale także z karty Kamienia Kamieni , aby unieważnić spalanie many. A będzie miał 3 rodzaje gruntów: wyspy, góry i lasy. Podstawową ideą jest użycie podsłuchanej ziemi do przedstawienia 1, a niewykorzystanej ziemi do reprezentacji 0. Wyspy będą użyte do przedstawienia stanu taśmy, Góry do zindeksowania bieżącej pozycji wzdłuż taśmy, a Lasy do przedstawienia stanu wewnętrznego 24 stan 2 symbol Maszyna Turinga (uważam, że jest uniwersalna dzięki Rogozhinowi).

$2^5 = 32 > 24$$2^{m+1}$

$2^5 = 32 > 24$$2^{m+1}$

Strategia: Zarówno A, jak i B grają o jedną ziemię na turnie w kolejności ich losowania. Kiedy każdy losuje 4 lasy, grają w Artefakt. Uwaga A jest pierwszy, więc ma już wyspę, gdy B dobiera, zagrywa swoją pierwszą kartę wejściową.

A i B po prostu kontynuują układanie swoich kart, dopóki B nie wyczerpie swoich Równin i Bagien i zagra swoją pierwszą Wyspę. Przy następnym przejściu, A dla wszystkich i stuka swoją wyspę iff Bs i Land Input był bagnem. Inicjuje swoją maszynę Turinga, dotykając pierwszego Lasu i Góry. Jeśli stuknął nieparzystą liczbę kart, stuka swój dodatkowy forrest i używa całej tej many, aby dodać żetony do tablicy kamieni szlachetnych. Odtąd gra przebiega w następujący sposób: B używa swojej tury, aby po prostu odzwierciedlić stan many A. B stuknie swoją i-tę Ziemię Wejściową, a i-ta Wyspa A zostanie stuknięta. Podobnie B klepie swój i-ty Las (Góra) i i A A-go Las (Góra) jest dotknięty. Ponieważ A zawsze stuknie parzystą liczbę kart, podobnie B, a mana służy do dodawania żetonów do tablicy kamieni szlachetnych.

W turze A cała mana A zostaje niewykorzystana, więc A patrzy na stan many B, reprezentuje stan many A w poprzedniej turze. A stosuje regułę przejścia zgodnie z maszyną uniwersalną (24,2) do stanu B, aby uzyskać swój nowy stan.

Gra toczy się w ten sposób, aż maszyna zatrzyma się. W tym momencie A wprowadza swoje góry w zarezerwowany stan „skończony” (stan całkowicie niewykorzystany). Jeśli maszyna Turinga zatrzyma się w stanie akceptacji, B kopiuje stan gór A, ale stuka całą pozostałą ziemię zaniedbując użycie tablicy Kamieni, rozpoczynając w ten sposób proces samobójstwa przez spalenie many. Z kolei A, jeśli góry B są w stanie „ukończonym”, a wszystkie inne ziemie B są dotknięte, A po prostu nic nie robi (zauważ, że jego góry są automatycznie w stanie „ukończonym”). Jeśli góry A są w stanie gotowym, ale nic więcej nie jest na podsłuchu, B kontynuuje samobójstwo z powodu poparzenia many. To się powtarza, aż B nie żyje.

Jeśli jednak maszyna skończy w stanie odrzucenia, B pozostawia wszystkie swoje karty niewykorzystane. Jeśli wszystkie karty B są niewykorzystane, A stuka wszystkie swoje karty, rozpoczynając ten sam proces samobójstwa przez spalenie many. Jeśli wszystkie karty A, które nie są Górami, zostaną dotknięte, a góry niewykorzystane, B pozostawi wszystkie swoje karty niewykorzystane. Doprowadzi to A do kontynuowania samobójstwa z paleniem many, dopóki nie przegra gry.

Powinno to spełniać kryteria zadane w pytaniu, a zatem, gdy takie zamówienie jest dozwolone, uważam, że gra jest kompletna w sensie opisanym w pytaniu.

Alex Churchill, Stella Biderman i Austin Herrick opublikowali ten artykuł, pokazując, że magia jest pełna Turinga

Streszczenie - Magic: The Gathering to popularna i słynna skomplikowana gra karciana o magicznej walce. W tym artykule pokazujemy, że optymalna gra w magii świata rzeczywistego jest co najmniej tak trudna jak problem zatrzymania, rozwiązując problem, który jest otwarty od dekady [1], [10]. Aby to zrobić, przedstawiamy metodologię osadzania dowolnej maszyny Turinga w grze Magic, dzięki czemu pierwszy gracz ma gwarancję wygranej, jeśli tylko maszyna Turinga się zatrzyma. Nasz wynik dotyczy sposobu grania prawdziwej Magii, można ją osiągnąć przy użyciu standardowych talii turniejowych i nie opiera się na stochastyczności ani ukrytych informacjach. Nasz wynik jest również bardzo niezwykły, ponieważ wszystkie ruchy obu graczy są wymuszone w konstrukcji. To pokazuje, że nawet rozpoznanie, kto wygra grę, w której żaden z graczy nie podejmie trywialnej decyzji do końca gry, jest nierozstrzygalne. Kończymy dyskusją na temat implikacji dla zunifikowanej obliczeniowej teorii gier i uwagami na temat grywalności takiej planszy w turniejach.