211service.com
Magic: The Gathering is officieel de meest complexe game ter wereld
Een afbeelding van pakjes Magic: The Gathering speelkaarten Nathan Rupert
Magic: The Gathering is een kaartspel waarin tovenaars spreuken uitspreken, wezens oproepen en magische voorwerpen exploiteren om hun tegenstanders te verslaan.
In het spel stellen twee of meer spelers elk een kaartspel van 60 kaarten met verschillende krachten samen. Ze kiezen deze kaartspellen uit een pool van zo'n 20.000 kaarten die zijn gemaakt naarmate het spel evolueerde. Hoewel het vergelijkbaar is met fantasy-rollenspellen zoals Dungeons and Dragons, heeft het aanzienlijk meer kaarten en complexere regels dan andere kaartspellen.
En dat roept een interessante vraag op: onder de echte games (de games die mensen echt spelen, in tegenstelling tot de hypothetische games die gametheoretici gewoonlijk beschouwen), waar valt magie in complexiteit?
Vandaag krijgen we een antwoord dankzij het werk van Alex Churchill, een onafhankelijke onderzoeker en bordspelontwerper in Cambridge, VK; Stella Biderman aan het Georgia Institute of Technology; en Austin Herrick aan de Universiteit van Pennsylvania.
Zijn team heeft voor het eerst de computationele complexiteit van het spel gemeten door het te coderen op een manier die kan worden gespeeld door een computer of Turing-machine. Deze constructie stelt vast dat: Magie: The Gathering is de meest computationeel complexe real-world game die in de literatuur bekend is, zeggen ze.
Eerst wat achtergrond. Een belangrijke taak in de informatica is om te bepalen of een probleem in principe kan worden opgelost. Bijvoorbeeld, beslissen of twee getallen relatief priem zijn (met andere woorden, of hun grootste gemene deler groter is dan 1) is een taak die kan worden uitgevoerd in een eindig aantal goed gedefinieerde stappen en is dus berekenbaar.
In een gewoon schaakspel is het ook berekenbaar of wit een winnende strategie heeft. Het proces omvat het testen van elke mogelijke reeks zetten om te zien of wit een overwinning kan forceren.
Maar hoewel beide problemen berekenbaar zijn, zijn de middelen die nodig zijn om ze op te lossen enorm verschillend.
Dit is waar het begrip computationele complexiteit om de hoek komt kijken. Dit is een rangschikking op basis van de middelen die nodig zijn om de problemen op te lossen.
In dit geval kan de beslissing of twee getallen relatief priem zijn, worden opgelost in een aantal stappen die evenredig zijn met een polynoomfunctie van de ingevoerde getallen. Als de invoer is x , de belangrijkste term in een polynoomfunctie is van de vorm Cxn , waar C en N zijn constanten. Dit valt in een klasse die bekend staat als P , waarbij P staat voor polynomiale tijd.
Daarentegen moet het schaakprobleem worden opgelost met brute kracht, en het aantal stappen dat dit neemt neemt toe in verhouding tot een exponentiële functie van de invoer. Als de invoer is x , de belangrijkste term in een exponentiële functie is van de vorm Cnx , waar C en N zijn constanten. en als x toeneemt, wordt dit veel sneller groter dan Cxn . Dit valt dus in een categorie met een grotere complexiteit die EXP wordt genoemd, of exponentiële tijd.
Daarnaast zijn er verschillende andere categorieën van verschillende complexiteit, en zelfs problemen waarvoor er geen algoritmen zijn om ze op te lossen. Deze worden niet-berekenbaar genoemd.
Uitzoeken in welke complexiteitsklasse games vallen, is een lastige zaak. De meeste spellen in de echte wereld hebben eindige limieten voor hun complexiteit, zoals de grootte van een speelbord. En dit maakt veel van hen triviaal vanuit het oogpunt van complexiteit. Het meeste onderzoek naar de algoritmische speltheorie van real-world games heeft voornamelijk gekeken naar generalisaties van veel gespeelde games in plaats van naar de real-world versies van de games, zeggen Churchill en co.
Van slechts een paar real-world games is dus bekend dat ze een niet-triviale complexiteit hebben. Deze omvatten Dots-and-Boxes, Jenga en Tetris. We geloven dat er geen real-world game bekend is als moeilijker dan NP voorafgaand aan dit werk, zegt Churchill en co.
Het nieuwe werk laat zien dat Magic: the Gathering aanzienlijk complexer is. De methode is in principe eenvoudig. Churchill en co beginnen met het vertalen van de krachten en eigenschappen van elke kaart in een reeks stappen die kunnen worden gecodeerd.
Vervolgens spelen ze een spel tussen twee spelers waarbij het spel zich afspeelt in een Turing-machine. En tot slot laten ze zien dat het bepalen of een speler een winnende strategie heeft, gelijk staat aan het beroemde stopprobleem in de informatica.
Dit is het probleem om te beslissen of een computerprogramma met een specifieke invoer zal stoppen of voor altijd zal doorgaan. In 1936 bewees Alan Turing dat geen enkel algoritme het antwoord kan bepalen. Met andere woorden, het probleem is niet berekenbaar.
Het belangrijkste resultaat van Churchill en co is dus dat het bepalen van de uitkomst van een magisch spelletje niet berekenbaar is. Dit is het eerste resultaat dat aantoont dat er een echt spel bestaat waarvoor het bepalen van de winnende strategie niet berekenbaar is, zeggen ze.
Dat is interessant werk dat belangrijke fundamentele vragen oproept voor de speltheorie. Churchill en co zeggen bijvoorbeeld dat de leidende formele theorie van games ervan uitgaat dat elk spel berekenbaar moet zijn. Magie: The Gathering past niet in de veronderstellingen die vaak worden gemaakt door computerwetenschappers bij het modelleren van games, zeggen ze.
Dat suggereert dat computerwetenschappers hun ideeën over games moeten heroverwegen, vooral als ze hopen een uniforme computationele theorie van games te produceren. Het is duidelijk dat Magic wat dit betreft een vlieg in de betoverde zalf is.
Referentie: arxiv.org/abs/1904.09828 : Magie: The Gathering Is Turing voltooid