… Och Scrabble visade sig vara PSPACE-komplett

Efter att ha uppfunnits i USA i mitten av 1900-talet är Scrabble nu tillgänglig på dussintals språk och säljs i antal mätt i hundratals miljoner. Det gör det till ett av de mest populära spelen i världen.

Det har naturligtvis väckt spelteoretikers intresse. Eftersom Scrabble är ett så framgångsrikt spel blir det en naturlig fråga att avgöra beräkningskomplexiteten för att hitta ett optimalt spel, säger Michael Lampis vid Kungliga Tekniska Högskolan i Sverige och några kompisar.

Samma fråga har framgångsrikt ställts till många brädspel, som schack, Go och Othello, som tenderar att vara PSPACE- eller EXPTIME-kompletta. Men Scrabble är knepigare eftersom spelarna inte vet i vilken ordning brickorna kommer att dras vilket innebär att slumpen spelar en större roll.

Frågan som Lampis och co försöker svara på är denna: givet en Scrabble-position hur svårt är det att bestämma den bästa spelstrategin?

De påpekar att i varje given omgång konfronteras en Scrabble-spelare med två uppgifter: att bestämma vilket ord som ska bildas och att bestämma var det ska placeras på brädet. Dessa uppgifter är relaterade eftersom orden som kan bildas beror på bokstävernas placering på tavlan.

Men vilken av dessa uppgifter är det som gör Scrabble svårt? Vad Lampis och co visar är att båda är svåra och ger ett bevis på var och en för att stödja deras påstående. Det är imponerande eftersom det tillåter oss att 'se' varför Scrabble är svårt.

Vi konstaterar att under ett spels gång behöver Scrabble-spelare inte utföra en, utan två beräkningsmässigt svåra uppgifter, vilket förmodligen är anledningen till att Scrabble är så roligt att spela, skriver de.

Det betyder inte att beräkningskomplexitetsteoretiker är färdiga och dammade med Scrabble. Deras nästa uppgift är att upptäcka om det finns en polynom-tidsalgoritm för att bestämma draget som skulle maximera poängen som uppnåddes i denna omgång.

Nu skulle det vara praktiskt!

Ref: arxiv.org/abs/1201.5298 : Scrabble är PSPACE-komplett

Dölj