… Og Scrabble viste sig at være PSPACE-komplet

Efter at være blevet opfundet i USA i midten af ​​det 20. århundrede, er Scrabble nu tilgængelig på snesevis af sprog og sælges i antal målt i hundredvis af millioner. Det gør det til et af de mest populære spil i verden.

Det har naturligvis vakt spilteoretikeres interesse. Da Scrabble er så succesfuldt et spil, bliver det et naturligt spørgsmål at bestemme den beregningsmæssige kompleksitet i at finde et optimalt spil, siger Michael Lampis ved KTH Kungliga Tekniska Högskolan i Sverige og et par venner.

Det samme spørgsmål er med succes blevet stillet til mange brætspil, såsom skak, Go og Othello, som har tendens til at være PSPACE eller EXPTIME-komplet. Men Scrabble er vanskeligere, fordi spillerne ikke kender rækkefølgen, som brikkerne vil blive trukket i, hvilket betyder, at tilfældigheder spiller en større rolle.

Spørgsmålet, som Lampis og co forsøger at besvare, er dette: givet en Scrabble-position, hvor svært er det at bestemme den bedste spillestrategi?

De påpeger, at en Scrabble-spiller i en given runde bliver konfronteret med to opgaver: at bestemme hvilket ord der skal dannes og at bestemme hvor det skal placeres på brættet. Disse opgaver hænger sammen, fordi de ord, der kan dannes, afhænger af bogstavernes placering på tavlen.

Men hvilken af ​​disse opgaver er det, der gør Scrabble svært? Hvad Lampis og co viser er, at begge er svære og giver et bevis på hver for at støtte deres påstand. Det er imponerende, fordi det giver os mulighed for at 'se', hvorfor Scrabble er svært.

Vi fastslår, at i løbet af et spil skal Scrabble-spillere ikke udføre én, men to beregningsmæssigt svære opgaver, hvilket nok er grunden til, at Scrabble er så sjovt at spille, skriver de.

Det betyder ikke, at beregningskompleksitetsteoretikere er færdige og støvet med Scrabble. Deres næste opgave er at finde ud af, om der er en polynomiel-tidsalgoritme til at bestemme det træk, der ville maksimere scoren opnået i denne runde.

Nu ville det være praktisk!

Ref: arxiv.org/abs/1201.5298 : Scrabble er PSPACE-komplet

skjule