Merlijn Sevenster onderzocht hoe je de moeilijkheidsgraad van een spelletje of een puzzel kunt meten. Kun je de moeilijkheid van twee verschillende soorten spelletjes vergelijken? Is een puzzel als sudoku moeilijker of makkelijker dan spellen voor twee spelers, zoals schaken en Stratego? Deze vragen behandelt hij in Branches of imperfect information: logic, games and computation, waarop hij 4 oktober promoveerde.

Volledige versus onvolledige informatie

In zijn onderzoek maakt Sevenster onderscheid tussen twee typen spellen: spellen met volledige informatie en spellen met onvolledige informatie. Een duidelijk voorbeeld van een spel met onvolledige informatie is het bordspel Scotland Yard, waarin de politie een boef moet inrekenen, die zijn locatie slechts op gezette tijden prijsgeeft. Ook Zeeslag, Mastermind, kwartetten en Memory zijn spellen met onvolledige informatie: meestal is de speler niet van de gehele situatie op de hoogte, waardoor hij niet alles weet dat nuttig is om een strategie te bepalen. Bij schaken en bij sudoku’s is de speler wél altijd op de hoogte van de gehele stand van zaken; we spreken dan van spellen met volledige informatie.

Wat is moeilijker?

Zijn spellen met onvolledige informatie moeilijker dan spellen met volledige informatie? Sevenster gebruikt technieken uit de theoretische informatica om te bepalen wat de moeilijkheid van een spel is. In de combinatorische speltheorie wordt de moeilijkheid van een spel gelijkgesteld aan de complexiteit van het beste computerprogramma dat een ‘pad naar succes’ vindt. Dat betekent dat bij een sudoku zo’n programma de oplossing moet vinden, en bij een spel moet het een winnende strategie (een strategie die er altijd voor zorgt dat jij wint, ook als de tegenspeler steeds de slimste zet doet) vinden. Als spellen op deze manier met elkaar vergeleken worden, blijken sudoku en Zeeslag even moeilijk te zijn. Ook heeft Sevenster een wiskundige abstractie van het bordspel Scotland Yard onder de loep genomen. Sevenster stelde de moeilijkheid van de volledige informatievariant van Scotland Yard vast en kwam tot de verrassende conclusie dat deze variant volgens de complexiteitstheorie niet makkelijker is dan Scotland Yard met onvolledige informatie.

Toepassingen

De speltheorie heeft veel toepassingen. Het wordt bijvoorbeeld gebruikt om radiofrequenties te verwerven en om het voortplantingsgedrag van natuurlijke organismen te analyseren. Zodoende wordt het woord ‘speler’ bijzonder veelomvattend gebruikt binnen de speltheorie: commerciële bedrijven zijn spelers, maar ook de Nederlandse overheid, en bloemetjes en bijtjes. Evenzo heeft het woord ‘spel’ een ruimere betekenis dan het doorgaans toegekend wordt in het Nederlands.