Onder heel specifieke omstandigheden is niet uit te rekenen hoe een potje van het kaartspel Magic: The Gathering zal aflopen, hebben drie onderzoekers aangetoond. Volgens hen zet dat algemeen geldende ideeën binnen de algoritmische speltheorie op de tocht.

Hoewel bord- en kaartspellen bij hun spelers tot flink wat gepeins, gezucht en gesteun kunnen leiden, zijn ze voor wetenschappers die zich bezighouden met complexiteitstheorie allemaal behoorlijk simpel. Die noemen een spel pas moeilijk als het uitrekenen van een goede strategie in principe onmogelijk is. Dat soort spellen zullen voor ons mensenbrein per definitie te hoog gegrepen zijn, zou je denken. Toch hebben drie onderzoekers aangetoond dat het kaartspel Magic: The Gathering ook voor complexiteitstheoretici in de categorie écht complex kan vallen.
 

Simulatie in een kaartspel

Nu is Magic: The Gathering, kortweg Magic, geen spel als schaken of go. Dit verzamelkaartspel kwam in 1993 op de markt en sindsdien zijn er elk jaar meerdere uitbreidingssets verschenen, waardoor er inmiddels meer dan 15.000 verschillende kaarten bestaan. Uit de kaarten die ze bezitten, stellen spelers hun eigen stapel samen; hun zogenoemde deck. Daarmee spelen ze dan tegen een of meer andere spelers die ook elk een eigen deck hebben geconstrueerd.

Wat de Brit Alex Churchill, onafhankelijk onderzoeker en bordspellenontwerper, nu samen met twee Amerikaanse wetenschappers heeft gedaan, is een computersimulatie ín Magic: The Gathering bouwen. Wouter Koolen, machine-learning-expert aan het Centrum voor Wiskunde en Informatica te Amsterdam, legt uit wat dat inhoudt. ‘Twee mensen die een potje Magic spelen, voeren met hun handelingen als het ware een computerprogramma uit. Daarbij geldt dan dat een speler ófwel verliest, ófwel doorspeelt en zo de computersimulatie een stapje verder helpt.’ Als de simulatie stopt, betekent dit dus dat een van beide spelers heeft gewonnen.

Probleem is alleen dat je voor een computerprogramma in de regel niet kunt uitrekenen of het ooit zal stoppen, vervolgt Koolen. En dat geldt ook voor dit ‘programma’. Je kunt dus niet op voorhand bepalen wie er zal winnen, wat het potje Magic ‘onbeslisbaar moeilijk’ maakt.
 

Oneindig veel informatie

Betekent dit dan dat Magic onvoorstelbaar complex is en iedereen die het met enig succes speelt dus briljant? Nou nee. Churchill en consorten hebben het in hun artikel over een héél specifiek potje Magic. Alleen dáárvan hebben ze aangetoond dat het onbeslisbaar moeilijk is. ‘Dat is erg knap gedaan’, zegt Koolen. ‘Het moet een enorm zoekwerk zijn geweest naar kaarten die op precies de juiste manier combineren.’

Een cruciale rol is daarbij weggelegd voor zogenoemde token creatures. Bij Magic geldt normaal gesproken dat één kaart gelijk staat aan één creature; een monster waarmee je bijvoorbeeld je tegenstander kunt aanvallen. Maar er bestaan ook kaarten die zélf grote aantallen monsters kunnen genereren. ‘Zulke creatures komen dus niet uit je deck, maar ontstaan als het ware uit het niets. En daarmee kun je een oneindig grote hoeveelheid informatie creëren op het spelbord zonder dat je daarvoor de spelregels hoeft aan te passen.’

Verder leggen Churchill en collega’s hun Magic-potje allerlei beperkingen op – maar ook dat gebeurt netjes binnen de spelregels. Zo maken de onderzoekers dankbaar gebruik van een kaart die zegt dat geen van de spelers meer automatisch elke beurt een nieuwe kaart trekt. Op die manier wordt uitgesloten dat een van de spelers het spel verliest doordat zijn stapel kaarten opraakt. Een andere kaart zorgt ervoor dat de spelers niet meer mogen worden aangevallen door monsters, zodat ook dat mechanisme om het spel te beëindigen niet meer werkt.
 

Bijzondere balans

Kortom, het gaat hier om een heel gekunsteld potje, dat weinig heeft te maken met hoe het kaartspel normaal gesproken verloopt. Toch: omdat Churchill en collega’s volledig binnen de regels van het spel hebben gewerkt, vinden ze dat ze het nog mogen presenteren als een real-world game. Dat wil zeggen: een spel zoals dat tussen echte mensen wordt gespeeld, in plaats van een ‘veralgemeniseerde’ versie bedacht door wetenschappers, zoals een schaakbord met oneindig veel vakjes. Accepteer je die kwalificatie, dan is met dit onderzoek aangetoond dat Magic de meest ‘computationeel complexe’ real-world game is die tot nu toe in de wetenschappelijke literatuur is besproken, zo meldt het wetenschappelijke artikel van het drietal.

Volgens de onderzoekers is hun vondst zelfs in strijd met algemeen aangenomen ideeën in hun vakgebied. In de woorden van Koolen: ‘Het gaat om de vraag wanneer een spel interessant is voor mensen. Het moet wel uitdagend zijn, maar niet zo ingewikkeld dat je er geen structuur in ziet; dat het geen zin meer heeft om strategieën te bedenken. Er is dus sprake van een heel bijzondere balans – en Magic gaat daar als onbeslisbaar ingewikkeld spel vér overheen.’

Zelf zet Koolen het resultaat wat minder groots neer. ‘Ik zie het als een leuk weetje over Magic dat verder geen toepassingen heeft. Maar ik vind het wel ontzettend gaaf dat dit de onderzoekers is gelukt.’

Openingsbeeld: Oliver Hallmann/CC BY 2.0 DE