Magic: The Gathering er officielt verdens mest komplekse spil

Et billede af pakker med Magic: The Gathering-spillekort Nathan Rupert

Magic: The Gathering er et kortspil, hvor troldmænd kaster trylleformularer, tilkalder skabninger og udnytter magiske objekter til at besejre deres modstandere.

I spillet samler to eller flere spillere hver et kortspil med 60 kort med forskellige kræfter. De vælger disse kortspil fra en pulje på omkring 20.000 kort, der blev skabt efterhånden som spillet udviklede sig. Selvom det ligner fantasy-rollespil som Dungeons and Dragons, har det betydeligt flere kort og mere komplekse regler end andre kortspil.

Og det rejser et interessant spørgsmål: blandt spil i den virkelige verden (dem som folk rent faktisk spiller, i modsætning til de hypotetiske spilteoretikere normalt overvejer), hvor falder magi i kompleksitet?

I dag får vi et svar takket være Alex Churchills arbejde, en uafhængig forsker og brætspilsdesigner i Cambridge, Storbritannien; Stella Biderman ved Georgia Institute of Technology; og Austin Herrick ved University of Pennsylvania.

Hans hold har målt spillets beregningsmæssige kompleksitet for første gang ved at kode det på en måde, der kan spilles af en computer eller Turing-maskine. Denne konstruktion fastslår det Magic: The Gathering er det mest beregningsmæssigt komplekse virkelige spil kendt i litteraturen, siger de.

Først lidt baggrund. En vigtig opgave inden for datalogi er at afgøre, om et problem principielt kan løses. For eksempel at afgøre, om to tal er relativt primtal (med andre ord, om deres største fælles divisor er større end 1) er en opgave, der kan udføres i et endeligt antal veldefinerede trin og derfor kan beregnes.

I et almindeligt skakspil kan det også beregnes, om hvid har en vinderstrategi. Processen involverer at teste enhver mulig sekvens af træk for at se, om hvid kan tvinge en sejr.

Men selvom begge disse problemer kan beregnes, er de nødvendige ressourcer til at løse dem vidt forskellige.

Det er her, begrebet beregningsmæssig kompleksitet kommer ind i billedet. Dette er en rangordning baseret på de ressourcer, der kræves for at løse problemerne.

I dette tilfælde kan beslutningen om, hvorvidt to tal er relativt primtal, løses i et antal trin, der er proportional med en polynomisk funktion af inputtallene. Hvis input er x , er det vigtigste led i en polynomisk funktion af formen Cxn , hvor C og n er konstanter. Dette falder ind under en klasse kendt som P , hvor P står for polynomisk tid.

I modsætning hertil skal skakproblemet løses med brute force, og antallet af skridt dette tager stiger proportionalt med en eksponentiel funktion af inputtet. Hvis input er x , er det vigtigste led i en eksponentiel funktion af formen Cnx , hvor C og n er konstanter. Og som x stiger, bliver denne større meget hurtigere end Cxn . Så dette falder ind under en kategori med større kompleksitet kaldet EXP eller eksponentiel tid.

Ud over dette er der forskellige andre kategorier af varierende kompleksitet, og endda problemer, for hvilke der ikke er nogen algoritmer til at løse dem. Disse kaldes ikke-beregnelige.

Det er en vanskelig forretning at finde ud af, hvilken kompleksitetsklasse spil falder ind under. De fleste spil fra den virkelige verden har begrænsede begrænsninger for deres kompleksitet, såsom størrelsen af ​​en spilleplade. Og dette gør mange af dem trivielle ud fra et kompleksitetssynspunkt. Det meste af forskningen i algoritmisk spilteori af spil i den virkelige verden har primært set på generaliseringer af almindeligt spillede spil snarere end de virkelige versioner af spillene, siger Churchill og co.

Så kun nogle få spil fra den virkelige verden er kendt for at have ikke-triviel kompleksitet. Disse omfatter Dots-and-Boxes, Jenga og Tetris. Vi mener, at intet spil i den virkelige verden er kendt for at være sværere end NP forud for dette arbejde, siger Churchill og co.

Det nye værk viser, at Magic: the Gathering er væsentligt mere kompleks. Metoden er i princippet ligetil. Churchill og co begynder med at oversætte kræfterne og egenskaberne for hvert kort til et sæt trin, der kan kodes.

De spiller derefter et spil mellem to spillere, hvor spillet udfolder sig i en Turing-maskine. Og endelig viser de, at det at afgøre, om en spiller har en vinderstrategi, svarer til det berømte stopproblem inden for datalogi.

Dette er problemet med at beslutte, om et computerprogram med en bestemt input vil køre færdig eller fortsætte for evigt. I 1936 beviste Alan Turing, at ingen algoritme kan bestemme svaret. Med andre ord, problemet er ikke-beregneligt.

Så Churchill og co's nøgleresultat er, at det ikke er muligt at beregne resultatet af et spil Magic. Dette er det første resultat, der viser, at der eksisterer et spil i den virkelige verden, hvor det ikke er muligt at beregne den vindende strategi, siger de.

Det er interessant arbejde, der rejser vigtige grundlæggende spørgsmål for spilteori. For eksempel siger Churchill og co, at den førende formelle teori om spil antager, at ethvert spil skal kunne beregnes. Magic: The Gathering passer ikke til antagelser, der almindeligvis er lavet af dataloger, mens de modellerer spil, siger de.

Det tyder på, at computerforskere er nødt til at genoverveje deres ideer om spil, især hvis de håber at producere en samlet computerteori om spil. Det er klart, at Magic repræsenterer en flue i den fortryllede salve, hvad dette angår.

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

skjule