Magic: The Gathering är officiellt världens mest komplexa spel

En bild av paket med Magic: The Gathering-spelkort Nathan Rupert

Magic: The Gathering är ett kortspel där trollkarlar trollformler, kallar fram varelser och utnyttjar magiska föremål för att besegra sina motståndare.

I spelet sätter två eller flera spelare ihop en kortlek med 60 kort med olika krafter. De väljer dessa kortlekar från en pool med cirka 20 000 kort som skapats när spelet utvecklades. Även om det liknar rollspelsfantasispel som Dungeons and Dragons, har det betydligt fler kort och mer komplexa regler än andra kortspel.

Och det väcker en intressant fråga: bland verkliga spel (de som folk faktiskt spelar, i motsats till de hypotetiska som spelteoretiker brukar tänka på), var hamnar magi i komplexitet?

Idag får vi svar tack vare Alex Churchills arbete, en oberoende forskare och brädspelsdesigner i Cambridge, Storbritannien; Stella Biderman vid Georgia Institute of Technology; och Austin Herrick vid University of Pennsylvania.

Hans team har mätt spelets beräkningskomplexitet för första gången genom att koda det på ett sätt som kan spelas av en dator eller Turing-maskin. Denna konstruktion slår fast det Magic: The Gathering är det mest beräkningsmässigt komplexa verkliga spelet känt i litteraturen, säger de.

Först lite bakgrund. En viktig uppgift inom datavetenskap är att avgöra om ett problem kan lösas i princip. Till exempel, att bestämma om två tal är relativt primtal (med andra ord, om deras största gemensamma divisor är större än 1) är en uppgift som kan göras i ett ändligt antal väldefinierade steg och är därför beräkningsbar.

I ett vanligt schackspel kan man också räkna ut om vit har en vinnande strategi. Processen innebär att man testar alla möjliga sekvenser av drag för att se om vit kan tvinga fram en vinst.

Men även om båda dessa problem är beräkningsbara är de resurser som krävs för att lösa dem väldigt olika.

Det är här begreppet beräkningskomplexitet kommer in. Detta är en rankning baserad på de resurser som krävs för att lösa problemen.

I det här fallet kan beslutet om två tal är relativt primtal lösas i ett antal steg som är proportionella mot en polynomfunktion av de ingående talen. Om ingången är x , är den viktigaste termen i en polynomfunktion av formen Cxn , var C och n är konstanter. Detta faller i en klass som kallas P , där P står för polynomtid.

Däremot måste schackproblemet lösas med brute force, och antalet steg som detta tar ökar i proportion till en exponentiell funktion av inmatningen. Om ingången är x , den viktigaste termen i en exponentiell funktion är av formen Cnx , var C och n är konstanter. Och som x ökar, blir detta större mycket snabbare än Cxn . Så detta faller in i en kategori med större komplexitet som kallas EXP, eller exponentiell tid.

Utöver detta finns det olika andra kategorier av varierande komplexitet, och till och med problem för vilka det inte finns några algoritmer för att lösa dem. Dessa kallas icke-beräknbara.

Att ta reda på vilken komplexitetsklass spel faller in i är en knepig sak. De flesta spel i den verkliga världen har ändliga gränser för deras komplexitet, till exempel storleken på en spelbräda. Och detta gör många av dem triviala ur komplexitetssynpunkt. Mest forskning inom algoritmisk spelteori för spel i den verkliga världen har i första hand tittat på generaliseringar av vanliga spel snarare än de verkliga versionerna av spelen, säger Churchill och co.

Så endast ett fåtal verkliga spel är kända för att ha icke-trivial komplexitet. Dessa inkluderar Dots-and-Boxes, Jenga och Tetris. Vi tror att inget verkligt spel är känt för att vara svårare än NP innan det här arbetet, säger Churchill och co.

Det nya verket visar att Magic: the Gathering är betydligt mer komplex. Metoden är i princip okomplicerad. Churchill och co börjar med att översätta krafterna och egenskaperna hos varje kort till en uppsättning steg som kan kodas.

De spelar sedan ett spel mellan två spelare där spelet utspelar sig i en Turing-maskin. Och slutligen visar de att att avgöra om en spelare har en vinnande strategi motsvarar det berömda stoppproblemet inom datavetenskap.

Detta är problemet med att avgöra om ett datorprogram med en specifik ingång kommer att sluta köras eller fortsätta för alltid. 1936 bevisade Alan Turing att ingen algoritm kan bestämma svaret. Problemet är med andra ord oberäkningsbart.

Så Churchill och cos nyckelresultat är att det inte går att beräkna resultatet av ett spel Magic. Detta är det första resultatet som visar att det finns ett verkligt spel där det inte går att beräkna den vinnande strategin, säger de.

Det är intressant arbete som väcker viktiga grundläggande frågor för spelteorin. Till exempel säger Churchill och co att den ledande formella teorin om spel antar att alla spel måste vara beräkningsbara. Magic: The Gathering stämmer inte överens med antaganden som vanligtvis görs av datavetare när de modellerar spel, säger de.

Det tyder på att datavetare måste ompröva sina idéer om spel, särskilt om de hoppas kunna producera en enhetlig beräkningsteori för spel. Helt klart representerar Magic en fluga i den förtrollade salvan vad det gäller detta.

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

Dölj