Was zum Flop wird und was zum Trend, ist oft schwer vorherzusagen. Aber dass das Scrabble-artige Spiel "Wordle" mit seinen uralten Mastermind-ähnlichen Spielregeln im Jahre 2022 noch zum Internet-Schlager aufsteigt, damit hätte wohl niemand gerechnet ([2]). Ganze Magazinartikel beschäftigen sich mit dem Phänomen ([3]), Arbeitskollegen protzen täglich mit ihren Ergebnissen, und die Zeitung New York Times hat es dem Entwickler mittlerweile für einen Millionenbetrag abgekauft ([4]). Auch deutsche Klons sind verfügbar ([5]), wenngleich es bei ihnen mit den Umlauten hapert.
Im Spiel geht es darum, ein Wort aus fünf Buchstaben zu erraten. Falls der Spieler das Wort richtig rät, ist das Spiel gewonnen. Weicht das Wort des Spielers noch vom zu erratenden Wort ab, markiert der Automat diejenigen Buchstaben in Grün, die an der richtigen Stelle liegen, und diejenigen in Ocker, die zwar im Wort vorkommen, aber an anderer Stelle. Buchstaben im Rateversuch, die das gesuchte Wort nicht hat, markiert Wordle in Grau. Der Spieler muss das Wort in höchstens sechs Versuchen erraten, indem er die Hinweise der App möglichst schlau umsetzt.
Erlaubt ist der Scrabble-Wortschatz, allerdings schließt Wordle bei den zu erratenden Wörtern Konjugationen oder Mehrzahlbildungen aus, also käme in der englischen Version "camel" vor, aber nicht "calms". Bei den Rateversuchen lässt Wordle hingegen alle fünfbuchstabigen Scrabble-Wörter zu, von denen es im Englischen 12.972 gibt. Die deutsche Wortliste hat hingegen nur 7.564 Einträge der Länge fünf, wenn man Umlaute wie Ü durch UE ersetzt, was die deutschen Wordle-Versionen (leider noch) machen.
| |
| Abbildung 1: Ein in drei Zügen gelöstes Wordle ... |
 |
| Abbildung 2: ... allerdings mit Hilfe eines Go-Programms. |
Die simplen Spielregeln schreien nun geradezu danach, einen Computer auf die Rätsel anzusetzen. Wenn Wordle einen Rateversuch farblich bewertet, kann ein Programm diese Hinweise nutzen, um Einträge aus einer vollständigen Wortliste herauszufiltern und so die Möglichkeiten in jedem Durchgang immer weiter reduzieren. Dabei gibt der Spieler dem Knackprogramm die Wordle-Hinweise kodiert weiter, eine "2" steht für einen ganz richtigen Buchstaben, eine "1" für einen Buchstaben an der falschen Stelle und "0" für Lettern, die gar nicht vorkommen. Wäre das gesuchte Wort zum Beispiel "camel" und der Spieler tippt auf "lamer", wäre der Code "12220", denn das "l" am Anfang des Tippversuchs steht an der falschen Stelle, die mittigen Lettern "ame" sind genau richtig und das abschließende "r" kommt im gesuchten Wort nicht vor.
 |
| Abbildung 3: Wordles Vorläufer: Das olle Mastermind-Spiel aus den 70er-Jahren. |
In Abbildung 2 schlägt das Knackerprogramm wordle als erstes Wort "oater" vor, das englische Wort für einen Western, denn Pferde fressen gerne Hafer (englisch "oat"). Der wahre Grund für dieses ungewöhnliche Wort ist freilich seine Häufung gängiger Vokale, deren Prüfung oft schnell zur Lösung führt, dazu später mehr. Abbildung 1 zeigt, dass das vorgeschlagene Wort auf der offiziellen Wordle-Seite drei ockerfarbene Halbtreffer für "o", "a" und "r" liefert, diese Buchstaben also im gesuchten Wort vorkommen, aber an anderer Stelle. Gibt der User diese Information mit "oater 11001" an den Knacker weiter, zeigt der mit "110 matches" an, dass somit noch 110 Wörter aus der Liste übrig bleiben, der Rest wurde aufgrund der Bewertung eliminiert. Mit dem Befehl "l" könnte der User diese 110 Wörter auflisten und manuell eines auswählen, stattdessen folgt er aber blind dem Vorschlag "abord" des Knackers.
Die Wordle-Webseite in Abbildung 1 bewertet diesen neuen Versuch mit zwei grünen Volltreffern für "a" und "o", und "r" steht wegen dem ockernen Halbtreffer noch immer an der falschen Stelle. Leitet der User dieses Ergebnis mit "abord 20210" an den Knacker weiter, schließt dieser sofort, dass nur zwei Wörter aus der langen Liste übrig bleiben, nämlich "aroha" und "aroma", und zeigt diese gleich an. Da es unwahrscheinlich ist, dass die New York Times das neuseeländische Maori-Wort für Liebe und Zuneigung, "aroha", als Lösung will, tippt der User auf "aroma" und ignoriert den Vorschlag des Knackers, und Abbildung 1 bestätigt, dass das die richtige Lösung ist.
Um den Wordle-Knacker nicht nur auf Englisch sondern auch mit deutschem Vokabular zu betreiben, ist natürlich einiger Internationalisierungsaufwand notwendig, auf Anfrage des Produktmanagers geben wir vorsichtshalber vier Wochen Portierungszeit an. Haha, kleiner Scherz, natürlich funktioniert das Spiel dank Gos vorbildlicher Behandlung von akzentuierten Zeichen in utf8 ohne jegliche Anpassung. Statt der englischen Scrabble-Wortliste muss nur eine deutsche her, und fertig ist der Lack. Allerdings versteht die deutsche Wordle-Web-Applikation auf [5] keine Umlaute, also müssen wir aus der deutschen Liste ([7]) alle "ü"s auf "ue" portieren, denn so will die Web-Applikation die Wörter haben.
Der deutsche Klon auf [5] lässt übrigens überhaupt keine Konjugationen zu, auch nicht beim Raten. Abbildung 4 zeigt den Aufruf des Knackers mit --lang=de im Deutschmodus. Wegen der schwachen Bewertung des Ausgangswortes "radio" schlägt der Knacker im zweiten Zug "belog" vor (die Vergangenheitsform von "belügen", aber das lehnte das deutsche Wordle als ungültig ab. Daraufhin wählte der Spieler "lotus" aus der angezeigten langen Liste mit 722 Einträgen und prompt stellen sich die ersten beiden Buchstaben auf der Webseite in Abbildung 4 als Volltreffer in Grün heraus; das abschließende "S" ist ein Teilerfolg in Ocker. Die Eingabe "lotus 22001" leitet die Bewertung in Abbildung 5 an den Knacker weiter, der daraufhin vier Vorschläge macht, von denen nur einer, nämlich "LOSEN", zulässig ist. Prompt bestätigt der das Spiel auf der Webseite das Ergebnis mit grünen Lettern.
 |
| Abbildung 4: Der deutsche Klon des Wordle-Spiels |
 |
| Abbildung 5: Der Wordle-Knacker gegen den deutschen Klon. |
Wie funktioniert nun das Programm? Als erstes muss der Wordle-Knacker in Go die zugelassenen Wörter aus einer Datei einlesen. Für die Original-Version in englischer Sprache bietet sich die Liste mit Scrabble-Wörtern auf [9] an. Darin stehen in Großbuchstaben pro Zeile ein Wort, insgesamt ist sie 279.496 Zeilen lang. Da Wordle aber nur 5-buchstabige Kombinationen zulässt, filtert Zeile 23 alles andere aus, übrig bleiben 12.972 Einträge. Im Fall der deutschen Scrabble-Datei aus [7] stehen im Original 594.104 Einträge, und übrig bleiben 7.564 mit ersetzten Umlauten. Ginge es beim deutschen Wordle mit rechten Dingen zu und Umlaute würden als solche gehandelt, blieben 7.565 Einträge mit fünf Buchstaben übrig.
Listing 1 legt die Wortlänge in der Konstanten WordleLen in Zeile 10 fest, wäre also jederzeit gewappnet, mit einer einzeiligen Änderung auch 6-buchstabige Wordles zu knacken. Die Funktion dictRead() ab Zeile 12 nimmt den Namen der Datei mit der Wortliste entgegen, öffnet sie zum Lesen in Zeile 15 und setzt in Zeile 20 einen zeilenweisen Scanner auf, der ab Zeile 21 die Wörter der Reihe nach einliest. Die Listen enthalten die Wörter entsprechend der Scrabble-Lettern in Großbuchstaben, also konvertiert Zeile 22 auf Kleinbuchstaben um, damit der User später beim Eingeben über die Tastatur nicht dauernd die Shift-Taste gedrückt halten muss.
01 package main
02
03 import (
04 "bufio"
05 "os"
06 "strings"
07 "unicode/utf8"
08 )
09
10 const WordleLen = 5
11
12 func dictRead(file string) ([]string, error) {
13 words := []string{}
14
15 f, err := os.Open(file)
16 if err != nil {
17 return words, err
18 }
19
20 s := bufio.NewScanner(f)
21 for s.Scan() {
22 word := strings.ToLower(s.Text())
23 if utf8.RuneCountInString(word) != WordleLen {
24 continue
25 }
26 words = append(words, word)
27 }
28 err = s.Err()
29 if err != nil {
30 return words, err
31 }
32
33 return words, nil
34 }
Fremdsprachen mit Multi-Byte-Kodierungen verkomplizieren übrigens einfache Computer-Algorithmen wie das Zählen von Lettern in einem String. Während in Opas altem ASCII einfach jedes Byte eines Strings einen Buchstaben repräsentiert, und der Rechner zur Ermittlung der Stringlänge einfach die Bytes zählt, handelt es sich zum Beispiel bei Umlauten im utf8-Format um Einträge mit 2 Bytes Länge, also muss sich die Funktion utf8.RuneCountInString() in Zeile 23 mühselig von Rune zu Rune hangeln, der in Go üblichen Ausdrucksweise für Buchstaben, die in der utf8-Kodierung entweder ein oder mehrere Bytes umfassen können.
Alle gefundenen Wörter sammelt die Funktion dictRead() im Array-Slice words und reicht sie am Ende an den Aufrufer zurück. Das Hauptprogramm in Listing 2 sammelt in main() ab Zeile 18 erst einmal mit dem Paket flag den Wert des Kommandozeilen-Flags --lang ein. Steht es auf "de" (ohne Angabe ist "en" voreingestellt), kommt die deutsche Wortliste zum Einsatz, deren Dateinamen scrabble-de.txt unter dem Schlüssel de in der Hashmap dictFileMap ab Zeile 10 steht. Sonst liest wordle die Datei scrabble.txt ein.
01 package main
02
03 import (
04 "flag"
05 "fmt"
06 )
07
08 var dicts = map[string]string{
09 "de": "scrabble-de.txt",
10 "en": "scrabble.txt",
11 }
12
13 var startWords = map[string]string{
14 "de": "radio",
15 "en": "oater",
16 }
17
18 func main() {
19 lang := flag.String("lang", "en", "de|en")
20 flag.Parse()
21
22 dict, err := dictRead(dicts[*lang])
23 if err != nil {
24 panic(err)
25 }
26
27 nw := startWords[*lang]
28
29 for round := 0; ; round++ {
30 list(dict, false)
31
32 if round != 0 {
33 nw = bestBang(dict)
34 }
35 fmt.Printf("Try next: '%s'\n", nw)
36 fmt.Printf("hints(%d)> ", len(dict))
37
38 var word, score string
39 fmt.Scanf("%s %s", &word, &score)
40 if len(score) == 0 {
41 if word == "l" {
42 list(dict, true)
43 } else {
44 fmt.Printf("Invalid input\n")
45 }
46 continue
47 }
48 dict = filter(dict, word, score)
49 }
50 }
51
52 func list(matches []string, full bool) {
53 if len(matches) > 30 && !full {
54 fmt.Printf("%d matches ('l' to list).\n", len(matches))
55 } else {
56 for _, w := range matches {
57 fmt.Printf("%s\n", w)
58 }
59 }
60 }
Die for-Schleife ab Zeile 29 in Listing 2 führt den User durch die Raterunden. Die Funktion Scanf in Zeile 39 wartet entweder auf die Eingabe des Kommandos "l", mit dem der User die Wörter listen kann, die noch im Rennen sind, oder das Ergebnis eines Rateversuchs im Format "oater 01201" in den Automaten eingeben. Wünscht der User die Listfunktion, ruft Listing 2 list() ab Zeile 52 auf, um die verbleibenden Worte im Array-Slice dict zeilenweise aufzulisten. Das Flag full bestimmt dabei, ob list() auch ellenlange Listen anzeigt oder nur solche mit höchstens 30 Wörtern. Letzteres macht wordle() in jeder Runde automatisch, die volle Liste zeigt es nur auf expliziten Wunsch mit "l" an.
Der eigentliche Grips des Knackers steckt in der Funktion filter() der das Hauptprogramm den bis dato verfügbaren Wortschatz in dict, den neuesten Rateversuch und dessen Bewertung durch die Wordle-Online-App mitgibt. Zurück kommt eine nach den Regeln der Bewertung reduzierte Wortliste, die das Hauptprogramm gleich wieder dict zuweist, das auf diese Weise stetig schrumpft, bis nur noch die Lösung übrigbleibt.
01 package main
02
03 import (
04 "strconv"
05 )
06
07 type Grade int
08
09 const (
10 NoMatch Grade = iota
11 OtherPos
12 Match
13 )
14
15 func grades(guess, want string) string {
16 hints := make([]Grade, len(guess))
17 for i, _ := range hints {
18 hints[i] = NoMatch
19 }
20
21 wantMap := map[byte]int{}
22
23 // wanted letter counts
24 for i := 0; i < len(want); i++ {
25 wantMap[want[i]] += 1
26 }
27
28 // full matches
29 for i := 0; i < len(guess); i++ {
30 guessRune := guess[i]
31 if guessRune == want[i] {
32 hints[i] = Match
33 wantMap[guessRune] -= 1
34 }
35 }
36
37 for i := 0; i < len(guess); i++ {
38 guessRune := guess[i]
39 if hints[i] == Match {
40 continue
41 }
42 if wantMap[guessRune] > 0 {
43 hints[i] = OtherPos
44 wantMap[guessRune] -= 1
45 }
46 }
47
48 res := ""
49 for _, hint := range hints {
50 res += strconv.Itoa(int(hint))
51 }
52 return res
53 }
54
55 func filter(words []string, guess, graded string) []string {
56 res := []string{}
57
58 for _, word := range words {
59 if graded == grades(guess, word) {
60 res = append(res, word)
61 }
62 }
63
64 return res
65 }
66
67 func bestBang(words []string) string {
68 best := ""
69 count := 0
70
71 for _, word := range words {
72 runes := map[rune]bool{}
73
74 for _, rune := range word {
75 runes[rune] = true
76 }
77
78 if count == 0 || len(runes) > count {
79 count = len(runes)
80 best = word
81 }
82 }
83
84 return best
85 }
Die Implementierung von filter() steckt in Listing 3, samt einer Funktion grades() die, ganz wie die Online-App, einen Rateversuch gegenüber einem gesuchten Wort auswerten kann und dem User sagt, welche Buchstaben richtig sind, welche an der falschen Stelle stehen, und welche gar nicht vorkommen. Die Funktion grades() gibt dazu zu einem gesuchten Wort im Parameter want und einem Rateversuch in guess einen String zurück, der die Bewertung als String im Format "01201" enthält.
Um die Bewertung eines Rateversuchs zu ermitteln, legt Zeile 16 einen Array-Slice mit Integern an, dessen Positionen denen der Buchstabem im Ratewort entsprechen. Steht an der entsprechenden Position später eine 2, ist der Buchstabe im Ratewort an der richtigen Stelle, und so weiter. Zur Initialisierung des Array-Slices setzt die For-Schleife ab Zeile 17 erst einmal alle Einträge auf NoMatch, also 0, wegen der Enum-ähnlichen Konstanten in Zeile 10, die das Schlüsselwort iota von 0 aufsteigend durchnumeriert.
Dann legt Zeile 21 eine Hash-Map wantMap an, die zu jedem Buchstaben dessen erforderliche Anzahl im Wort abgezählt hat. Das zu erratende Wort "LOOSE" wiese zum Beispiel den Buchstaben "L", "S" und "E" den Wert 1 zu, und dem Buchstaben "O" den Wert 2. Die For-Schleife ab Zeile 29 fährt dann alle Buchstaben des Rateworts ab und setzt die entsprechenden hints-Einträge auf 2, falls der Buchstabe exakt mit der Lösung in want übereinstimmt. Jeder dieser Treffer reduziert den Wert der insgesamt benötigte Anzahl dieses Buchstabens in wantMap um Eins.
Ab Zeile 37 kommt nun der Teil, der die Positionen bewertet, die einen Buchstaben enthalten, der eigentlich woanders stehen sollte. Ist die aktuelle Position kein Volltreffer, enthält aber einen Buchstaben aus der wantMap, kommt in den hints-Array-Slice an der aktuellen Positition der Wert 1 zu stehen, und der Zähler in der wantMap reduziert sich um Eins. Taucht der Buchstabe später im Wort nochmals auf, und ist dessen Zähler in wantMap immer noch nicht erschöpft, käme dort eine weitere 1 zu liegen.
Zum Schluss wandelt grades() den Integer-Array-Slice mit den Bewertungen der einzelnen Buchstaben mittels der Konvertierungsfunktion strconv.Itoa() noch elementweise in einen String um, um ihn als Kompaktpaket an den Aufrufer zurückzugeben. Fertig ist der Bewertungsalgorithmus! Auf der Wordle-Webseite dürfte etwas Ähnliches laufen.
Was aber hat das Ganze jetzt mit dem Ausfiltern von Wörtern zu tun, die aufgrund der Bewertung von Rateversuchen durch die Wordle-Seite nicht mehr als Lösung in Frage kommen? Zum Ausfiltern nicht mehr möglicher Wörter nutzt der Algorithmus in filter() einen Trick: Er geht Wort für Wort durch die verbleibende Wortliste, und nimmt in jeder Runde an, das wäre nun das gesuchte Wort. Dann zieht Zeile 59 den Bewerter grades() zurate und fragt ihn, was denn nun die Bewertung des aktuellen Rateworts gegenüber der angenommenen Lösung aus der Wortliste wäre. Und nun der Clou: Kommt grades() mit der gleichen Bewertung zurück wie der Algorithmus der Wordle-Webseite, ist das angenommene Lösungswort ein echter Kandidat für die Lösung, andernfalls kann der Filter es löschen. Simpel, aber effektiv.
Damit das Hauptprogramm mit Try next einen guten Vorschlag aus der Liste der verbleibenden Kandidaten wählen kann, sucht die Funktion bestBang() ab Zeile 67 in Listing 3 ein Wort mit möglichst vielen verschiedenen Buchstaben aus. So erhöht sich die Wahrscheinlichkeit, dass einer oder mehrere dieser Buchstaben tatsächlich im Lösungswort enthalten sind, und der User im nächsten Schritt gleich noch mehr falsche Lösungen eliminieren kann. Dazu zählt bestBang() pro Wort in einer Hash-Map runes dessen unterschiedliche Buchstaben, und merkt sich das Wort mit dem höchsten Zähler (also mit der höchsten Entropie), das es abschließend an den Aufrufer zurückgibt.
Um die Listings zu kompilieren, reicht der Aufruf
go build wordle.go dict.go filter.gound schon steht in wordle ein lauffähiges Binary bereit, denn der Knacker kommt ohne Fremdbibliotheken, nur mit dem Fundus von Gos Standardbibliothek aus. Die zum Betrieb notwendigen Scrabble-Dateien gibt's auf [7] und [9] zum kostenlosen Herunterladen.
Wer als Erster ins Ziel fahren will, tut gut daran, zügig als Erster von der Startlinie loszufahren, und das ist nicht nur in der Formel Eins so. Mittlerweile haben sich sogar Wissenschaftler damit befasst, welches Wort im Wordle-Spiel am Anfang den besten Schwung bringt ([6]). Allgemein sind Wörter mit vielen verschiedenen Buchstaben gut, und dabei sind Buchstaben, die häufig vorkommen, extrem wertvoll, denn sie erhöhen die Wahrscheinlichkeit, gute Hinweise auf ihr Vorhandensein oder sogar ihre Positon im gesuchten Wort zu bekommen. Der Knacker nutzt darum im englischen Modus das Wort "oater", im deutschen das Wort "radio".
Soweit der Wordle-Knacker, aber wie immer sind am Ende des Snapshots noch nicht alle Möglichkeiten ausgeschöpft, denn selbstgeschriebene Programme laden zum Experimentieren ein.
 |
| Abbildung 6: Der Automat spielt gegen sich selbst. |
Abbildung 6 zeigt eine Erweiterung der vorgestellten Funktionen, die den Automaten gegen sich selber spielen lassen. So lassen sich neue Algorithmen auf ihre Effizienz testen und fortlaufend verbessern. Im Beispiel spielt der Automat mit dem deutschen Wörterbuch. Anfangs wählt er das Wort "yawls", fängt mit "abeis" zu Raten an, bekommt die Bewertung 10002 als Ergebnis, und arbeitet sich über "dalks" in sechs Schritten bis zum Ergebnis "yawls". Wer übrigens bezweifelt, dass "yawls" oder "dalks" im deutschen Scrabble zugelassenen Wörter sind, sollte sich eine deutsche Scrabble-Ausgabe und ein entsprechendes Wörterbuch zulegen. Dort lernt der erstaunte Student, dass ein "Yawl" ein zweimastiges Sportsegelboot ist, "yawls" die Mehrzahl davon. Und ein "Dalk" ist eine Mönchskutte, mit "Dalks" als Mehrzahl. Die besten Scrabble-Spieler behalten solche Monsterlisten aus ungewöhnlichen Worten im Kopf. Automaten sind bei den Wettbewerben aber leider nicht zugelassen.
Listings zu diesem Artikel: http://www.linux-magazin.de/static/listings/magazin/2022/05/snapshot/
Wordle, https://www.powerlanguage.co.uk/wordle/
Ian Bogost, "I Figured Out Wordle's Secret", https://www.theatlantic.com/technology/archive/2022/01/solving-wordle-puzzle/621413/
New York Times buys Wordle, https://www.theguardian.com/games/2022/jan/31/wordle-new-york-times-buys
Deutscher Wordle-Klon: https://wordle.uber.space/
Bestes erstes Wort: https://www.inquirer.com/science/wordle-starting-word-answer-win-play-20220203.html
Deutsche Wortliste: https://rdrr.io/github/strategic-games/sg.data/man/Scrabbledict_german.html
Wordle archive (Englisch): https://www.devangthakkar.com/wordle_archive/?226
Liste mit englischen Scrabble-Wörtern: https://boardgames.stackexchange.com/questions/38366/latest-collins-scrabble-words-list-in-text-file
 |
Michael Schilliarbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen verschiedener Programmiersprachen. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen. |
Hey! The above document had some coding errors, which are explained below:
Unknown directive: =desc