Die Nähe zur Unendlichkeit

    • Die Nähe zur Unendlichkeit

      Bei der letzten DM in Stuttgart wurde natürlich auch am Abend - nach anstrengenden Spielen - (fast nur) über SCRABBLE gesprochen. Kein Wunder. Doch nahm ich an einem Gespräch teil, das mir sehr zu denken gab. Johann-Georg Dengel warf die Frage auf:

      Wie viele mögliche Spiele gibt es beim Scrabble?

      Sind es mehr oder weniger als beim Schach (oder GO etc.). Er hatte erstaunliches anzubieten. Unter anderem die Behauptung, es seien wohl mehr als da Atome im gesamten Universum sind ... WOW! Das gab zu denken. Ich mochte ihm nicht widersprechen, obgleich mir die angebotenen Zahlen 'obskur' erschienen; es gab da ein paar kleine Verwechslungen (Die Anzahl der Atome mit 1040 erschien mir viel zu klein, die Anzahl der möglichen Schach-Spiele mit 1080 sehr, sehr groß, obgleich das Verhältnis von 1040 mal mehr Spielmöglichkeiten als Atome erstaunlicherweise - siehe weiter unten - dem geschätzten Wert nahekommt!)

      Fangen wir etwas einfacher an: Wieviele verschiedene Startbänkchen gibt es im Scrabble? Das lässt sich - wenn auch etwas kompliziert - berechnen. Wir müssen dazu in Betracht ziehen, dass wir 102 Buchstabensteine haben, davon eine Reihe identischer. Damit kann maximal auf der ersten Bank nur einmal ein J;P;Q;V;W;X;Y;Z;Ä;Ö oder Ü liegen; maximal zweimal B;C;F;K oder Blanko; maximal dreimal G;L oder O vorkommen; maximal viermal D;H oder M; fünfmal das A, sechsmal I,R,U oder T und schließlich siebenmal E,N oder S.

      Trägt man all das zusammen, dann ergibt sich eine gewaltige Zahl: sie beträt knapp 4 Millionen Möglichkeiten (4 x 106).

      Wer es nicht glauben will, wird sich vielleicht von der sehr viel einfacheren Berechnung überzeugen lassen: Angenommen, alle Buchstaben wären einzigartig im Säckchen, dann wäre die Anzahl der Möglichkeiten schlicht 102!/95!x7!, wobei das Zeichen '!' die Fakultät angibt, d.h.n! 'Alle Zahen von 1 bis n werden miteinander multipliziert'. Mathematisch ist das der Binomialkoffizient C(102;7). Das Ergebnis ist dann ca. 1010, mit anderen Worten 10 Milliarden, größer also als die Erdbevölkerung.


      Mit weiteren solcher Binomial-Koeffizienten ist auch das Ergebnis weiter oben gewonnen.


      Zum Vergleich: Beim Schachspiel sind es rein theoretisch im ersten Zug 20 Züge, von denen Experten abernur zwei oder drei für 'sinnvoll' halten. Nichts desto trotz: Die Anzahl der (theoretisch) möglichen Schachspiele wird mit der Shannon Zahl mit ca. 10120 abgeschätzt; das wiederum sind etwa 1040 mal mehr Spiele als Atome im bekannten Universum vorhanden sind (ca. 1080).


      Und Scrabble-Spiele? Im Gegensatz zu 16 Spielsteinen pro Spieler und einem Brett von 64 Feldern, haben wir 102 Spielsteine, 225 Felder, zudem auf diesem unterschiedliche Prämiefelder - da wird schon bald klar, dass wir an die Grenze der (fassbaren) Endlichkeit stossen werden. Sie übersteigt die Shannon Zahl bei weitem *).


      Warum ist das so? Ich erkläre es an einem Beispiel: Nehmen wir an, der Anziehende hat das Wort ABECE H4w gelegt und sein Gegenspieler hat die Bank AEINRST. Hier gibt es allein über 50 Bingos! Berechnet man alle Züge (dazu gehören neben 'Passen' auch Tausch von 1,2,3,... Buchstaben), dann ergibt es bereits über 2000 Möglichkeiten (!) und das wiederholt sich nicht nur sondern wächst noch mit der Möglichkeit, an mehreren Stellen anzulegen (in der Theorie u.a. nur ein Buchstabe). Ich habe es Überprüft. Legt z.B. der Gegenspieler EINRASTE (H8s) und beschere ich nun dem Anziehenden dieselbe Bank wie dem Gegenspieler, so steigt die Zahl aller möglichen Züge bereits auf > 3000.


      Doch ein Versuch von einer anderen, praktischeren Betrachtungsweise her:


      Ein kleiner Überblick über Partien unserer besten Spieler zeigt, dass sie in der Regel ca. 450 Punkte in jeder Partie sammeln, im Mittel pro Zug knapp 30 Punkte einheimsen und ca. 15 Züge pro Spieler, zusammen also 30 Züge spielen. Nun nehme ich - ähnlich wie bei den Abschätzungen im Schach - an, dass ein solcher Spieler pro Zug etwa vier bis fünf Möglichkeiten in Betracht zieht. Beachte: Das bedeutet nicht (immer) fünf verschiedene Wörter, sondern auch nur zwei Wörter, aber in verschiedenen Positionen z.B. Das bringt eine erste Abschätzung, denn 5 Möglichkeiten in ca. 30 Zügen bringt uns auf 530. Das sind dann ca. 1021 Variationen des Spieles. Doch HALT! Wir haben dann im Gegensatz zum Schach, wo es immer nur eine Anfangsposition gibt, die Anfangskonfiguration nicht berücksichtigt.Das sind aber neben den ca. 4 x 106 Möglichkeiten für den Startspieler noch eine (geringfügig) kleinere Zahl von Möglichkeiten für die Bank des Gegenüber. Zusammen also etwa 8 x 1012 solcher Startpositionen. Diese Eigenschaft katapultiert SCRABBLE sicher am Schachspiel vorbei. Wir kommen jetzt schon zu knapp 1034 unterschiedlichen Möglichkeiten.


      Interessant an dieser Abschätzung dürfte noch folgendes sein: Schwächere Spieler zeigen eher eine größere Anzahl von Zügen (ca. 20 pro Spieler) und bedenken häufig mehr als 4 - 5 Möglichkeiten pro Zug; sie tendieren zu 7 bis 8. Nun zeigt die Abschätzung von 740 (das sind ca. 6 x 1033 Möglichkeiten) und die natürlich unveränderte Anfangskonfiguration, so dass die Anzahl aller so möglichen Spiele nun auf fast 1046 ansteigt.


      Zum Vergleich: Unser Körper enthält ca. 7 x 1027 Atome, unser Planet Erde ca. 1050, das (bekannte) Universum ca. 1080.

      Aber auch ohne diese Zahlen: Vielleicht denken wir einmal kurz nach einer gerade abgeschlossenen Partie: Sie ist einzigartig!



      *) Eine erste Abschätzung mit 1000 Möglichkeiten im Mittel pro Zug bringt bei 40 Zügen bereits 10120 x 8 x 1012 , das sind ca. 10133. Beachte: 40 Züge bedeutet ein Mittelwert, denn in allen Möglichkeiten ist natürlich auch enthalten, dass nach einem Anfangszug mit 2 Buchstaben, immer nur 1 Buchstabe angelegt wird (oder getauscht oder gepasst wird!). Damit sind bis zu 101 Züge möglich. Tatsächlich ist die Anzahl aller möglichen Scrabblespiele noch (erheblich?) größer, da wir 'Tauschen' (beliebig oft) und 'Passen' (nach TSO nicht mehr als zweimal hintereinander von beiden Spielern) einfliessen lassen können. Ich ahnte, dass Scrabble weit mehr Varianten als Schach aufweist.
    • Also, da wir ja theoretisch beliebig oft tauschen können, kommen wir in der theorieschon auf "unendlich"; wobei man dazu natürlich auch unendlich schnell spielen müsste.
      Auch das mögliche Legen ungültiger Wörter, würde die theoretische Zahl natürlich schon extrem in die Höhe treiben.

      Eigentlich interessant wäre statt der theoretisch möglichen verschiedenen Partien daher wohl eher die Frage, wie viele Partien wohl gespielt werden müssten, bis man zweimal einen identischen Verlauf hat (wie auch immer man das genau definiert).
      Natürlich hinge auch das davon ab, wer die Partien bestreitet.
    • ...Hinzu kommt, dass das Regelwerk bei Scrabble nicht fix ist und immer wieder geändert wird. z.B. neulich die Regel, wann bei Zeit-Überziehung abgebrochen wird. Auch die Wortliste wird immer wieder erweitert.
      Und, wie gerade gesagt, man kann eine Zillion Phonys legen, die angezweifelt werden oder auch nicht. Und man kann sich leicht verzählen, was auch den Spielausgang beeinflussen kann.

      Also halten wir fest: Scrabble ist das komplexeste Spiel im Universum 8o
    • Zum Beitrag 2: Die Abschätzung zum Spiel 'GO', das ich selber schätze (aber nur auf dem Level 'Intermediate' spiele), halte ich nicht für 'seriös' - im Beitrag 3 weist Vektor auf solche 'Ungereimtheiten' schon hin. Was meine ich damit genau? Dazu wähle ich einmal dieselbe Berechnungsgrundlage, wie sie für 'GO' verwendet wurde: Unser Spielfeld besteht aus 15 x 15, also 225 Feldern. Auf jedes Feld lässt sich die Mannigfaltigkeit von 29 verschiedenen Buchstaben unseres Vorrats (ohne Einschränkungen, da alle sowohl die Anfangs-, Schluss- als auch jede dazwischenliegende Position einnehmen können) einbringen. Das ergibt also 29225 Möglichkeiten (!) - berechnet sind das ca. 2 x 10332, also ebenfalls eine 10 mit mehr als 300 Nullen (siehe Link unter # 2). Es folgt dann eine Bemerkung: Aber nur ca. 1 % davon sind 'tatsächlich' möglich. Dazu fehlt eine genaue Begründung. M.E. ist dieser Bruchteil viel zu hoch gegriffen. Nehme ich dieselben Voraussetzungen für das Scrabblespiel, dann wird die Anzahl der möglichen Partien (Ohne 'Tausch und Passen mit einer Anzahl von 50 Spielzügen) bereits > 10600 . Wähle ich die (mögliche, aber eher unsinnige) Annahme von 100 Zügen, dann komme ich auf > 10800.

      Solches wollte ich in meinem Zugang über 'tatsächliche' Verläufe meiden; ähnlich wie beim Vergleich mit Schach. Dort werden aus der (berechneten) Schanon Zahl von 10120 ebenfalls heftig reduziert aus typischen Abläufen schließlich etwa 1020.

      Zu Beitrag 3: Ich stimme Vektor zu: Theoretisch kommen wir auf unendlich viele (aber abzählbare) Scrabble-Spiele, daher mein Titel: Die Nähe zur Unendlichkeit. Wir müssen übrigens nicht unendlich lange oder unendlich schnell spielen (was sollte letzteres auch sein?), wir müssen nur für jeden folgenden Zug die Hälfte des Zeit des vorangegangenen einhalten. Dann dürfen wir für den ersten Zug sogar bis zu 15 Minuten gebrauchen und halten die vorgegebene Zeit von 30 Minuten locker ein ... :P

      Zur letzten Frage mit zwei identischen Partien (realitätsnah): Das wiederholt sich sicher nach 1034, wahrscheinlich bereits einiges eher. Martin Läuter (Leipzig) hat uns gerade mit einem Clusterrechner 2000000 Scrabblespiele ausgewertet. Dazu benötigt der Rechner pro Spiel etwas weniger als eine Sekunde. Bleiben wir bei einer Sekunde, dann können wir es kurz einmal mit der (geschätzten) Lebensdauer unseres Universums von ca. 13,5 x 109 y, entsprechend 4 x 1017 s vergleichen. WOW! Selbst unter der Annahme einer solch hohen Rechengeschwindigkeit - keine Chance!

      Größte Hochachtung vor 'unseren Neuronen und ihrem Netzwerk' - dort liegen auch die Versuche, solche Problemstellungen mit Rechnern anzugehen.