211service.com
… I Scrabble Udowodniło PSPACE-Complete
Scrabble, wynaleziony w Stanach Zjednoczonych w połowie XX wieku, jest obecnie dostępny w dziesiątkach języków i sprzedawany w liczbach mierzonych w setkach milionów. To sprawia, że jest to jedna z najpopularniejszych gier na świecie.
To naturalnie wzbudziło zainteresowanie teoretyków gier. Ponieważ Scrabble jest tak udaną grą, naturalnym pytaniem staje się określenie złożoności obliczeniowej w znalezieniu optymalnej gry, mówi Michael Lampis z Królewskiego Instytutu Technologicznego KTH w Szwecji i kilku kumpli.
To samo pytanie zadano z powodzeniem w przypadku wielu gier planszowych, takich jak szachy, Go i Othello, które zazwyczaj są wypełnione PSPACE lub EXPTIME. Ale Scrabble jest trudniejsze, ponieważ gracze nie znają kolejności losowania płytek, co oznacza, że szansa odgrywa większą rolę.
Pytanie, na które Lampis i spółka próbują odpowiedzieć, brzmi: biorąc pod uwagę pozycję w Scrabble, jak trudno jest określić najlepszą strategię gry?
Wskazują, że w każdej rundzie gracz Scrabble ma do czynienia z dwoma zadaniami: podjęciem decyzji, które słowo ma uformować, oraz podjęciem decyzji, gdzie umieścić je na planszy. Zadania te są ze sobą powiązane, ponieważ słowa, które można ułożyć, zależą od położenia liter na tablicy.
Ale które z tych zadań sprawia, że Scrabble jest trudne? Lampis i spółka pokazują, że obaj są twardzi i dają dowody każdego na poparcie swoich roszczeń. To imponujące, ponieważ pozwala nam „zobaczyć”, dlaczego Scrabble jest trudne.
Ustalamy, że w trakcie gry gracze w Scrabble muszą wykonać nie jedno, ale dwa trudne obliczeniowo zadania, co prawdopodobnie jest powodem, dla którego gra w Scrabble jest tak fajna, jak piszą.
Nie oznacza to, że teoretycy złożoności obliczeniowej są gotowi i odkurzeni w Scrabble. Ich kolejnym zadaniem jest odkrycie, czy istnieje algorytm wielomianowy do określenia ruchu, który zmaksymalizuje wynik osiągnięty w tej rundzie.
Teraz byłoby to przydatne!
Nr ref.: arxiv.org/abs/1201.5298 : Scrabble jest PSPACE-Complete