Magic: The Gathering to oficjalnie najbardziej złożona gra na świecie

Obraz pakietów kart do gry Magic: The Gathering

Obraz pakietów kart do gry Magic: The GatheringNathan Rupert



Magic: The Gathering to gra karciana, w której czarodzieje rzucają zaklęcia, przyzywają stworzenia i wykorzystują magiczne przedmioty, aby pokonać swoich przeciwników.

W grze dwóch lub więcej graczy tworzy talię złożoną z 60 kart o różnych mocach. Wybierają te talie z puli około 20 000 kart stworzonych w miarę rozwoju gry. Chociaż jest podobny do gier fantasy RPG, takich jak Dungeons and Dragons, ma znacznie więcej kart i bardziej złożone zasady niż inne gry karciane.





Rodzi to interesujące pytanie: gdzie wśród gier w świecie rzeczywistym (tych, w które ludzie faktycznie grają, w przeciwieństwie do tych hipotetycznych, które zwykle rozważają teoretycy gier), poziom złożoności Magic?

Dzisiaj otrzymujemy odpowiedź dzięki pracy Alexa Churchilla, niezależnego badacza i projektanta gier planszowych z Cambridge w Wielkiej Brytanii; Stella Biderman w Georgia Institute of Technology; i Austina Herricka z Uniwersytetu Pensylwanii.

Jego zespół po raz pierwszy zmierzył złożoność obliczeniową gry, kodując ją w sposób, w który może grać komputer lub maszyna Turinga. Ta konstrukcja stanowi, że Magia: Zgromadzenie twierdzą, że jest to najbardziej złożona obliczeniowo gra w świecie rzeczywistym znana w literaturze.



Najpierw trochę tła. Ważnym zadaniem w informatyce jest ustalenie, czy problem można w zasadzie rozwiązać. Na przykład decydowanie, czy dwie liczby są względnie pierwsze (innymi słowy, czy ich największy wspólny dzielnik jest większy niż 1), jest zadaniem, które można wykonać w skończonej liczbie dobrze zdefiniowanych kroków, a więc jest obliczalne.

W zwykłej grze w szachy decydowanie, czy biały ma zwycięską strategię, jest również obliczalne. Proces obejmuje testowanie każdej możliwej sekwencji ruchów, aby sprawdzić, czy białe mogą wymusić wygraną.

Ale chociaż oba te problemy są obliczalne, zasoby wymagane do ich rozwiązania są znacznie różne.

najlepsze definicje słownika miejskiego

W tym miejscu pojawia się pojęcie złożoności obliczeniowej. Jest to ranking oparty na zasobach wymaganych do rozwiązania problemów.



W takim przypadku decydowanie, czy dwie liczby są względnie pierwsze, można rozwiązać w kilku krokach, które są proporcjonalne do funkcji wielomianowej liczb wejściowych. Jeśli dane wejściowe to x , najważniejszy wyraz w funkcji wielomianowej ma postać Cxn , gdzie C oraz n są stałymi. To należy do klasy znanej jako P , gdzie P oznacza czas wielomianowy.

W przeciwieństwie do tego, problem szachowy musi być rozwiązany brutalną siłą, a liczba kroków, które to wykonuje, wzrasta proporcjonalnie do wykładniczej funkcji wejścia. Jeśli dane wejściowe to x , najważniejszy wyraz w funkcji wykładniczej ma postać Cnx , gdzie C oraz n są stałymi. I jako x wzrasta, to staje się większe znacznie szybciej niż Cxn . Tak więc należy to do kategorii o większej złożoności zwanej EXP lub czasem wykładniczym.

Poza tym istnieją różne inne kategorie o różnej złożoności, a nawet problemy, dla których nie ma algorytmów do ich rozwiązania. Są to tak zwane nieobliczalne.

Ustalenie, w którą klasę złożoności mieszczą się gry, jest trudnym zadaniem. Większość gier w świecie rzeczywistym ma skończone ograniczenia co do ich złożoności, takie jak rozmiar planszy. A to sprawia, że ​​wiele z nich jest trywialnych z punktu widzenia złożoności. Większość badań nad algorytmiczną teorią gier w rzeczywistych grach skupiała się przede wszystkim na uogólnieniach powszechnie używanych gier, a nie na rzeczywistych wersjach gier, mówią Churchill i spółka.

Tak więc wiadomo, że tylko kilka gier z prawdziwego świata ma nietrywialną złożoność. Należą do nich Kropki i Pudełka, Jenga i Tetris. Uważamy, że żadna gra w świecie rzeczywistym nie byłaby trudniejsza niż NP przed tą pracą, mówi Churchill i spółka.

Nowa praca pokazuje, że Magic: the Gathering jest znacznie bardziej złożona. Metoda jest w zasadzie prosta. Churchill i spółka zaczynają od przełożenia mocy i właściwości każdej karty na zestaw kroków, które można zakodować.

Następnie rozgrywają grę między dwoma graczami, w której rozgrywka toczy się na maszynie Turinga. I wreszcie pokazują, że ustalenie, czy jeden gracz ma zwycięską strategię, jest równoznaczne ze słynnym problemem zatrzymania w informatyce.

Jest to problem decydowania, czy program komputerowy z określonymi danymi wejściowymi zakończy działanie, czy będzie działał w nieskończoność. W 1936 roku Alan Turing udowodnił, że żaden algorytm nie jest w stanie określić odpowiedzi. Innymi słowy, problem jest nieobliczalny.

Kluczowym wynikiem Churchilla i spółki jest to, że określenie wyniku gry w magię jest nieobliczalne. To pierwszy wynik pokazujący, że istnieje gra w świecie rzeczywistym, dla której ustalenie zwycięskiej strategii jest nieobliczalne.

To interesująca praca, która podnosi ważne fundamentalne pytania dotyczące teorii gier. Na przykład Churchill i wsp. twierdzą, że wiodąca formalna teoria gier zakłada, że ​​każda gra musi być obliczalna. Magia: Zgromadzenie twierdzą, że nie pasuje do założeń powszechnie przyjmowanych przez informatyków podczas modelowania gier.

Sugeruje to, że informatycy muszą przemyśleć swoje pomysły na temat gier, zwłaszcza jeśli mają nadzieję stworzyć ujednoliconą, obliczeniową teorię gier. Najwyraźniej magia reprezentuje muchę w zaczarowanej maści, jeśli o to chodzi.

Nr ref.: arxiv.org/abs/1904.09828 : Magic: The Gathering Is Turing Complete

ukryć

Rzeczywiste Technologie.

Kategoria

Bez Kategorii

Technologia

Biotechnologia

Polityka Techniczna

Zmiana Klimatu

Ludzie I Technologia

Dolina Krzemowa

Przetwarzanie Danych

Magazyn Mit News

Sztuczna Inteligencja

Przestrzeń

Inteligentne Miasta

Blockchain

Historia Funkcji

Profil Absolwenta

Połączenie Absolwentów

Funkcja Wiadomości Mit

1865

Mój Widok

77 Msza Św

Poznaj Autora

Profile W Hojności

Widziany Na Kampusie

Listy Absolwentów

Aktualności

Wybory 2020

Z Indeksem

Pod Kopułą

Magazyn Informacyjny Mit

Wąż Pożarowy

Nieskończone Historie

Projekt Technologii Pandemicznej

Od Prezydenta

Przykrywka

Galeria Zdjęć

Zalecane