211service.com
Magic: The Gathering er offisielt verdens mest komplekse spill
Et bilde av pakker med Magic: The Gathering-spillekort Nathan Rupert
Magic: The Gathering er et kortspill der trollmenn kaster trolldom, tilkaller skapninger og utnytter magiske objekter for å beseire motstanderne.
I spillet setter to eller flere spillere sammen en kortstokk med 60 kort med varierende kraft. De velger disse kortstokkene fra en pool med rundt 20 000 kort som ble laget etter hvert som spillet utviklet seg. Selv om det ligner på rollespill fantasyspill som Dungeons and Dragons, har det betydelig flere kort og mer komplekse regler enn andre kortspill.
Og det reiser et interessant spørsmål: blant spill i den virkelige verden (de som folk faktisk spiller, i motsetning til de hypotetiske spillteoretikere vanligvis vurderer), hvor faller magi i kompleksitet?
I dag får vi svar takket være arbeidet til Alex Churchill, en uavhengig forsker og brettspilldesigner i Cambridge, Storbritannia; Stella Biderman ved Georgia Institute of Technology; og Austin Herrick ved University of Pennsylvania.
Teamet hans har målt den beregningsmessige kompleksiteten til spillet for første gang ved å kode det på en måte som kan spilles av en datamaskin eller Turing-maskin. Denne konstruksjonen slår fast det Magic the Gathering er det mest beregningsmessig komplekse virkelige spillet kjent i litteraturen, sier de.
Først litt bakgrunn. En viktig oppgave innen informatikk er å finne ut om et problem kan løses prinsipielt. For eksempel, å avgjøre om to tall er relativt primtall (med andre ord, om deres største felles divisor er større enn 1) er en oppgave som kan gjøres i et begrenset antall veldefinerte trinn og kan derfor beregnes.
I et vanlig sjakkspill kan det også beregnes om hvit har en vinnende strategi. Prosessen innebærer å teste alle mulige trekksekvenser for å se om hvit kan tvinge fram en seier.
Men mens begge disse problemene kan beregnes, er ressursene som kreves for å løse dem svært forskjellige.
Det er her forestillingen om beregningsmessig kompleksitet kommer inn. Dette er en rangering basert på ressursene som kreves for å løse problemene.
I dette tilfellet kan det å avgjøre om to tall er relativt primtall løses i en rekke trinn som er proporsjonale med en polynomfunksjon av inngangstallene. Hvis inngangen er x , er det viktigste leddet i en polynomfunksjon av formen Cxn , hvor C og n er konstanter. Dette faller inn i en klasse kjent som P , hvor P står for polynomtid.
Derimot må sjakkproblemet løses med brute force, og antallet skritt dette tar øker proporsjonalt med en eksponentiell funksjon av input. Hvis inngangen er x , er det viktigste leddet i en eksponentiell funksjon av formen Cnx , hvor C og n er konstanter. Og som x øker, blir dette større mye raskere enn Cxn . Så dette faller inn i en kategori med større kompleksitet kalt EXP, eller eksponentiell tid.
Utover dette er det forskjellige andre kategorier med varierende kompleksitet, og til og med problemer som det ikke finnes algoritmer for å løse dem for. Disse kalles ikke-beregnbare.
Å finne ut hvilken kompleksitetsklasse spill faller inn i er en vanskelig sak. De fleste spill i den virkelige verden har begrensede begrensninger på kompleksiteten, for eksempel størrelsen på et spillebrett. Og dette gjør mange av dem trivielle fra et kompleksitetssynspunkt. Mest forskning innen algoritmisk spillteori for spill i den virkelige verden har først og fremst sett på generaliseringer av ofte spilte spill i stedet for de virkelige versjonene av spillene, sier Churchill og co.
Så bare noen få virkelige spill er kjent for å ha ikke-triviell kompleksitet. Disse inkluderer Dots-and-Boxes, Jenga og Tetris. Vi tror at ingen virkelige spill er kjent for å være vanskeligere enn NP før dette arbeidet, sier Churchill og co.
Det nye verket viser at Magic: the Gathering er betydelig mer kompleks. Metoden er i prinsippet enkel. Churchill og co begynner med å oversette kreftene og egenskapene til hvert kort til et sett med trinn som kan kodes.
De spiller deretter et spill mellom to spillere der spillet utfolder seg i en Turing-maskin. Og til slutt viser de at det å avgjøre om en spiller har en vinnende strategi tilsvarer det berømte stoppproblemet innen informatikk.
Dette er problemet med å avgjøre om et dataprogram med en bestemt inngang skal fullføres eller fortsette for alltid. I 1936 beviste Alan Turing at ingen algoritme kan bestemme svaret. Problemet er med andre ord ikke-beregnbart.
Så Churchill og cos nøkkelresultat er at det ikke er mulig å beregne resultatet av et spill med magi. Dette er det første resultatet som viser at det finnes et spill i den virkelige verden der det ikke er mulig å beregne vinnerstrategien, sier de.
Det er interessant arbeid som reiser viktige grunnleggende spørsmål for spillteori. For eksempel sier Churchill og co at den ledende formelle teorien om spill antar at ethvert spill må kunne beregnes. Magic the Gathering stemmer ikke overens med antakelser som vanligvis gjøres av informatikere mens de modellerer spill, sier de.
Det tyder på at informatikere må revurdere ideene sine om spill, spesielt hvis de håper å produsere en enhetlig beregningsteori om spill. Det er klart at Magic representerer en flue i den fortryllede salven når det gjelder dette.
Ref: arxiv.org/abs/1904.09828 : Magic: The Gathering Is Turing Complete