© gajus / 123RF.com

Das simple Online-Spiel Wordle hat im Februar die Welt im Sturm erobert. Mike Schilli entwickelt einen Algorithmus, um dort seinen persönlichen Score mit unlauteren Methoden nach oben zu treiben.

Was zum Flop wird und was zum Trend, das lässt sich oft schwer vorhersagen. Dass aber das Scrabble-artige Spiel Wordle [1] mit seinen uralten, Mastermind-ähnlichen Spielregeln im Jahr 2022 noch zum Internet-Schlager aufsteigt, damit hätte wohl niemand gerechnet. Ganze Magazinartikel beschäftigen sich mit dem Phänomen [2], Arbeitskollegen protzen täglich mit ihren Ergebnissen, und die New York Times hat es dem Entwickler mittlerweile für einen Millionenbetrag abgekauft [3]. Auch deutsche Klone sind verfügbar [4], wenngleich es bei ihnen an den Umlauten hapert.

Im Spiel geht es darum, ein Wort aus fünf Buchstaben zu erraten. Falls der Spieler das Wort richtig eingibt, hat er das Spiel gewonnen. Weicht seine Lösung noch vom Lösungswort ab, markiert der Automat diejenigen Buchstaben in Grün, die darin enthalten sind und an der richtigen Stelle stehen, und diejenigen in Ocker, die zwar im Wort vorkommen, aber an anderer Stelle. Buchstaben im Rateversuch, die im gesuchten Wort nicht vorkommen, markiert Wordle in Grau. Der Spieler muss das Wort mit höchstens sechs Versuchen erraten, indem er die Hinweise der App möglichst schlau umsetzt.

Automatisier mich!

Erlaubt ist der Scrabble-Wortschatz, allerdings schließt Wordle bei den zu erratenden Wörtern Konjugationen oder Mehrzahlbildungen aus. In der englischen Version käme also CAMEL vor, nicht aber CAMELS. Bei den Rateversuchen lässt Wordle hingegen alle fünfbuchstabigen Scrabble-Wörter zu, von denen es im Englischen 12 972 gibt [5]. Die deutsche Wortliste [6] umfasst hingegen nur 7564 Einträge mit fünf, Buchstaben, wenn man Umlaute wie Ü durch UE ersetzt, was die deutschen Wordle-Versionen (noch) tun.

Abbildung 1: Dieses Wordle wurde in drei Zügen gelöst …

Abbildung 2: … wobei allerdings ein Go-Programm half.

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 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 “LAMER”, würde der Code 12220 lauten: 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.

In Abbildung 2 schlägt das Knackerprogramm »wordle« als erstes Wort OATER vor, das englische Wort für einen Western, denn Pferde fressen gern 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 noch 110 Wörter aus der Liste übrigbleiben; 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, R steht als ockerfarbener 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, die er gleich anzeigt. 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 AROMA ein und ignoriert den Vorschlag des Knackers. Abbildung 1 bestätigt, dass das die richtige Lösung ist.

Einfach auf Deutsch

Um den Wordle-Knacker nicht nur auf Englisch zu betreiben, sondern auch mit deutschem Vokabular, fällt einiger Internationalisierungsaufwand an – 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 UTF-8 ohne jede Anpassung. Statt der englischen Scrabble-Wortliste muss nur eine deutsche her, und fertig ist der Lack. Allerdings versteht die deutsche Wordle-Webapplikation keine Umlaute, also müssen wir in der deutschen Liste alle Üs in UE umwandeln, denn so will die Webapplikation die Wörter haben.

Der deutsche Klon lässt übrigens überhaupt keine Konjugationen zu, auch nicht beim Raten. Abbildung 3 zeigt den Aufruf des Knackers mit »–lang=de« im deutschen Modus. Wegen der schwachen Bewertung des Ausgangswortes RADIO schlägt der Knacker im zweiten Zug BELOG vor (die Vergangenheitsform von belügen), aber das lehnt das deutsche Wordle als ungültig ab. Daraufhin wählt der Spieler LOTUS aus der angezeigten Liste mit 722 Einträgen, und prompt stellen sich die ersten beiden Buchstaben auf der Webseite in Abbildung 3 als Volltreffer in Grün heraus. Das abschließende S ist ein Teilerfolg in Ocker. Mit der Eingabe »lotus 22001« leitet der Spieler die Bewertung in Abbildung 4 an den Knacker weiter, der daraufhin vier Vorschläge macht, von denen nur einer zulässig ist, nämlich LOSEN. Prompt bestätigt das Spiel auf der Webseite das Ergebnis mit grünen Lettern.

Abbildung 3: Der deutsche Klon des Wordle-Spiels.

Abbildung 4: Der Wordle-Knacker gegen den deutschen Klon.

Knacken nach Liste

Wie funktioniert nun das Programm? Als Erstes muss der Wordle-Knacker in Go die zugelassenen Wörter aus einer Datei einlesen. Für die Originalversion in englischer Sprache bietet sich eine Liste mit Scrabble-Wörtern an. Darin steht in Großbuchstaben pro Zeile ein Wort, insgesamt ist sie 279 496 Zeilen lang. Da Wordle aber nur fünfbuchstabige Kombinationen zulässt, filtert Zeile 23 alles andere aus. Übrig bleiben 12 972 Einträge. Im Fall der deutschen Scrabble-Datei stehen im Original 594 104 Einträge, übrig bleiben mit ersetzten Umlauten 7564. Ginge es beim deutschen Wordle mit rechten Dingen zu und Umlaute würden als solche behandelt, wären es 7565 Einträge mit fünf Buchstaben.

Listing 1 legt die Wortlänge in der Konstanten »WordleLen« in Zeile 10 fest, wäre also jederzeit gewappnet, mit einer einzeiligen Änderung auch sechsbuchstabige 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, damit der User später beim Eingeben über die Tastatur nicht dauernd die Shift-Taste gedrückt halten muss.

package main
import (
  "bufio"
  "os"
  "strings"
  "unicode/utf8"
)
const WordleLen = 5
func dictRead(file string) ([]string, error) {
  words := []string{}
  f, err := os.Open(file)
  if err != nil {
    return words, err
  }
  s := bufio.NewScanner(f)
  for s.Scan() {
    word := strings.ToLower(s.Text())
    if utf8.RuneCountInString(word) != WordleLen {
      continue
    }
    words = append(words, word)
  }
  err = s.Err()
  if err != nil {
    return words, err
  }
  return words, nil
}

Fremdsprachen

Fremdsprachen mit Multi-Byte-Kodierungen verkomplizieren einfache Computer-Algorithmen wie das Zählen von Lettern in einem String beträchtlich. Während in Opas altem ASCII einfach jedes Byte eines Strings einen Buchstaben repräsentiert und der Rechner zur Ermittlung der String-Länge einfach die Bytes zählt, handelt es sich zum Beispiel bei Umlauten im UTF8-Format um Einträge mit zwei Bytes Länge. Daher 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 UTF-8-Kodierung entweder ein oder mehrere Bytes umfassen.

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.

Die For-Schleife ab Zeile 29 führt den Benutzer durch die Raterunden. Die Funktion »Scanf()« in Zeile 39 wartet auf entsprechende Eingaben des Anwenders. Der tippt entweder das Kommando »l«, um die noch im Rennen befindlichen Wörter aufzulisten, oder liefert das Ergebnis eines Rateversuchs im Format »oater 01201«. Für die Listenfunktion ruft der Code »list()« ab Zeile 52 auf, um die verbleibenden Worte im Array-Slice »dict« zeilenweise auszugeben. Das Flag »full« bestimmt dabei, ob »list()« 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.

package main
import (
  "flag"
  "fmt"
)
var dicts = map[string]string{
  "de": "scrabble-de.txt",
  "en": "scrabble.txt",
}
var startWords = map[string]string{
  "de": "radio",
  "en": "oater",
}
func main() {
  lang := flag.String("lang", "en", "de|en")
  flag.Parse()
  dict, err := dictRead(dicts[*lang])
  if err != nil {
    panic(err)
  }
  nw := startWords[*lang]
  for round := 0; ; round++ {
    list(dict, false)
    if round != 0 {
      nw = bestBang(dict)
    }
    fmt.Printf("Try next: '%s'\n", nw)
    fmt.Printf("hints(%d)> ", len(dict))
    var word, score string
    fmt.Scanf("%s %s", &word, &score)
    if len(score) == 0 {
      if word == "l" {
        list(dict, true)
      } else {
        fmt.Printf("Invalid input\n")
      }
      continue
    }
    dict = filter(dict, word, score)
  }
}
func list(matches []string, full bool) {
  if len(matches) > 30 && !full {
    fmt.Printf("%d matches ('l' to list).\n", len(matches))
  } else {
    for _, w := range matches {
      fmt.Printf("%s\n", w)
    }
  }
}

Gehirn des Automaten

Der eigentliche Grips des Knackers steckt in der Funktion »filter()«. Der gibt das Hauptprogramm in »dict« den bis dato verfügbaren Wortschatz und dessen Bewertung durch die Wordle-Online-App mit. 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 korrekte Lösung übrigbleibt.

Listing 3 zeigt die Implementierung von »filter()«, samt einer Funktion »grades()«, die ganz wie die Online-App einen Rateversuch gegenüber einem gesuchten Wort auswerten kann. Sie sagt dem User, welche Buchstaben richtig sind, welche an der falschen Stelle stehen und welche gar nicht vorkommen. Die Funktion »grades()« gibt zu einem gesuchten Wort im Parameter »want« und zu 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 Ganzzahlen an, deren Positionen denen der Buchstaben 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 durchnummeriert.

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ötigten 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-Slices 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()« elementweise in einen String um, um ihn als Kompaktpaket an den Aufrufer zurückzugeben. Ein ähnlicher Bewertungsalgorithmus dürfte auf der Wordle-Webseite laufen.

package main
import (
  "strconv"
)
type Grade int
const (
  NoMatch Grade = iota
  OtherPos
  Match
)
func grades(guess, want string) string {
  hints := make([]Grade, len(guess))
  for i, _ := range hints {
    hints[i] = NoMatch
  }
  wantMap := map[byte]int{}
  // wanted letter counts
  for i := 0; i < len(want); i++ {
    wantMap[want[i]] += 1
  }
  // full matches
  for i := 0; i < len(guess); i++ {
    guessRune := guess[i]
    if guessRune == want[i] {
      hints[i] = Match
      wantMap[guessRune] -= 1
    }
  }
  for i := 0; i < len(guess); i++ {
    guessRune := guess[i]
    if hints[i] == Match {
      continue
    }
    if wantMap[guessRune] > 0 {
      hints[i] = OtherPos
      wantMap[guessRune] -= 1
    }
  }
  res := ""
  for _, hint := range hints {
    res += strconv.Itoa(int(hint))
  }
  return res
}
func filter(words []string, guess, graded string) []string {
  res := []string{}
  for _, word := range words {
    if graded == grades(guess, word) {
      res = append(res, word)
    }
  }
  return res
}
func bestBang(words []string) string {
  best := ""
  count := 0
  for _, word := range words {
    runes := map[rune]bool{}
    for _, rune := range word {
      runes[rune] = true
    }
    if count == 0 || len(runes) > count {
      count = len(runes)
      best = word
    }
  }
  return best
}

Algorithmus filtert

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 infrage kommen? Zum Aussondern 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 derselben 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 ein Wort mit möglichst vielen verschiedenen Buchstaben aus. So erhöht sich die Wahrscheinlichkeit, dass das Lösungswort tatsächlich einen oder mehrere dieser Buchstaben enthält und dass der Benutzer 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. Es merkt sich das Wort mit dem höchsten Zähler (also mit der höchsten Entropie) und gibt es abschließend an den Aufrufer zurück.

Um die Listings zu kompilieren, genügt der Aufruf »go build wordle.go dict.go filter.go«. Danach steht mit »wordle« ein lauffähiges Binary bereit, denn der Knacker benötigt keine Fremdbibliotheken, sondern kommt mit dem Fundus der Go-Standardbibliothek aus. Die zum Betrieb notwendigen englischen und deutschen Scrabble-Dateien lassen sich kostenlos aus dem Netz herunterladen.

Schnell aus der Box

Wer als Erster ins Ziel fahren will, tut gut daran, zügig von der Startlinie loszufahren – das ist nicht nur in der Formel 1 so. Mittlerweile haben sich sogar Wissenschaftler damit befasst, welches Wort im Wordle-Spiel am Anfang den besten Schwung bringt [7].

Allgemein erweisen sich Wörter mit vielen verschiedenen Buchstaben als gut. Dabei sind Buchstaben, die häufig vorkommen, extrem wertvoll, denn sie erhöhen die Wahrscheinlichkeit, gute Hinweise auf ihr Vorhandensein oder sogar ihre Position im gesuchten Wort zu bekommen. Der Knacker nutzt darum im englischen Modus das Wort OATER, im deutschen das Wort RADIO.

Künstliche Intelligenz

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 5 zeigt eine Erweiterung der vorgestellten Funktionen, die den Automaten gegen sich selber spielen lassen. So kann man 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 vor.

Abbildung 5: Der Automat spielt gegen sich selbst.

Wer bezweifelt, dass es sich bei Yawls oder Dalks um im Deutschen vorkommende Wörter handelt, der sollte sich eine deutsche Scrabble-Ausgabe und ein entsprechendes Wörterbuch zulegen. Dort lernt der erstaunte Student, dass eine Yawl ein zweimastiges Sportsegelboot ist (Mehrzahl: Yawls) und es sich bei einem Dalk um eine Mönchskutte handelt (Mehrzahl: Dalks). Die besten Scrabble-Spieler behalten Monsterlisten mit solchen ungewöhnlichen Worten im Begriffen. Automaten sind bei den Wettbewerben allerdings nicht zugelassen … (uba/jlu)