211service.com
… und Scrabble bewiesen PSPACE-Complete
Mitte des 20. Jahrhunderts in den USA erfunden, ist Scrabble heute in Dutzenden von Sprachen verfügbar und wird in Hunderten von Millionen verkauft. Das macht es zu einem der beliebtesten Spiele der Welt.
Das hat natürlich das Interesse der Spieltheoretiker geweckt. Da Scrabble ein so erfolgreiches Spiel ist, ist es eine natürliche Frage, die rechnerische Komplexität zu bestimmen, um ein optimales Spiel zu finden, sagen Michael Lampis vom KTH Royal Institute of Technology in Schweden und ein paar Freunde.
Die gleiche Frage wurde vielen Brettspielen wie Schach, Go und Othello erfolgreich gestellt, die tendenziell PSPACE oder EXPTIME-komplett sind. Scrabble ist jedoch kniffliger, da die Spieler die Reihenfolge nicht kennen, in der die Kacheln gezogen werden, sodass der Zufall eine größere Rolle spielt.
Die Frage, die Lampis und Co zu beantworten versuchen, lautet: Wie schwer ist es bei einer Scrabble-Position, die beste Spielstrategie zu bestimmen?
Sie weisen darauf hin, dass ein Scrabble-Spieler in jeder Runde mit zwei Aufgaben konfrontiert ist: zu entscheiden, welches Wort er bilden und wo es auf dem Brett platziert werden soll. Diese Aufgaben hängen zusammen, weil die Wörter, die gebildet werden können, von der Position der Buchstaben auf der Tafel abhängen.
Aber welche dieser Aufgaben macht Scrabble schwer? Was Lampis und Co zeigen, ist, dass beide hart sind und für jeden Beweise liefern, um ihre Behauptung zu untermauern. Das ist beeindruckend, denn es erlaubt uns zu „sehen“, warum Scrabble schwer ist.
Wir stellen fest, dass Scrabble-Spieler im Laufe eines Spiels nicht eine, sondern zwei rechenintensive Aufgaben ausführen müssen, was wahrscheinlich der Grund ist, warum Scrabble so viel Spaß macht, schreiben sie.
Das heißt nicht, dass Theoretiker der Computational Complexity mit Scrabble fertig sind. Ihre nächste Aufgabe besteht darin, herauszufinden, ob es einen Polynomialzeitalgorithmus gibt, um den Zug zu bestimmen, der die in dieser Runde erzielte Punktzahl maximieren würde.
Das wäre jetzt praktisch!
Ref: arxiv.org/abs/1201.5298 : Scrabble ist PSPACE-komplett