211service.com
... En Scrabble bleek PSPACE-compleet
Scrabble, dat halverwege de 20e eeuw in de VS is uitgevonden, is nu beschikbaar in tientallen talen en wordt verkocht in aantallen van honderden miljoenen. Dat maakt het een van de meest populaire games ter wereld.
Dat heeft natuurlijk de interesse gewekt van speltheoretici. Omdat Scrabble zo'n succesvol spel is, wordt het een natuurlijke vraag om de computationele complexiteit van het vinden van een optimaal spel te bepalen, zeggen Michael Lampis van het KTH Royal Institute of Technology in Zweden en een paar vrienden.
Dezelfde vraag is met succes gesteld aan veel bordspellen, zoals schaken, Go en Othello, die meestal PSPACE of EXPTIME-compleet zijn. Maar Scrabble is lastiger omdat spelers niet weten in welke volgorde de tegels worden getrokken, wat betekent dat het toeval een grotere rol speelt.
De vraag die Lampis en co proberen te beantwoorden is deze: gegeven een Scrabble-positie, hoe moeilijk is het om de beste speelstrategie te bepalen?
Ze wijzen erop dat een Scrabble-speler in een bepaalde ronde met twee taken wordt geconfronteerd: beslissen welk woord moet worden gevormd en beslissen waar het op het bord moet worden geplaatst. Deze taken zijn gerelateerd omdat de woorden die kunnen worden gevormd afhankelijk zijn van de positie van letters op het bord.
Maar welke van deze taken maakt Scrabble moeilijk? Wat Lampis en co laten zien, is dat beide moeilijk zijn en een bewijs van elk geven om hun bewering te staven. Dat is indrukwekkend omdat het ons in staat stelt te 'zien' waarom Scrabble moeilijk is.
We stellen vast dat Scrabble-spelers tijdens een spel niet één, maar twee rekenkundig moeilijke taken moeten uitvoeren, wat waarschijnlijk de reden is waarom Scrabble zo leuk is om te spelen, schrijven ze.
Dat wil niet zeggen dat computationele complexiteitstheoretici klaar zijn en bestrooid zijn met Scrabble. Hun volgende taak is om te ontdekken of er een polynomiaal-tijdalgoritme is om de zet te bepalen die de in deze ronde behaalde score zou maximaliseren.
Nou dat zou handig zijn!
Referentie: arxiv.org/abs/1201.5298 : Scrabble is PSPACE-Compleet