Das populäre Spiel Wordle schreit geradezu danach, einen Computer auf die simplen Worträtsel anzusetzen – etwa mithilfe eines kleinen Go-Programms.

Was zum Flop wird und was zum Trend, das lässt sich oft schwer vorhersagen. Dass aber das Scrabble-artige Spiel Wordle [2] 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 [3], Arbeitskollegen protzen täglich mit ihren Ergebnissen, und die New York Times hat es dem Entwickler mittlerweile für einen Millionenbetrag abgekauft [4]. Auch deutsche Klone sind verfügbar [5], 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 (Abbildung 1).

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

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 das Spiel hingegen alle fünfbuchstabigen Scrabble-Wörter zu, von denen es im Englischen 12 972 gibt [6]. Die deutsche Wortliste [7] umfasst hingegen nur 7564 Einträge mit fünf Buchstaben, wenn man Umlaute wie Ü durch UE ersetzt, was die deutschen Wordle-Versionen (noch) tun.

Die simplen Spielregeln schreien nun geradezu danach, einen Computer auf die Rätsel anzusetzen. Ein Artikel in LinuxUser 04/2022 [1] zeigte bereits, wie sich das Problem durch den Einsatz von Grep und regulären Ausdrücken lösen lässt. Er schloss mit der Anmerkung, dass es sich effizientere Wege gäbe, das Problem anzugehen, und der Aufforderung, uns diese doch vorzustellen. Als Resultat finden Sie im Folgenden eine Möglichkeit, Wordles mit einem in Go geschriebenen Programm zu lösen.

Automatisier mich!

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. Wie Abbildung 1 zeigt, liefert das vorgeschlagene Wort auf der offiziellen Wordle-Seite drei ockerfarbene Halbtreffer für O, A und R. Diese Buchstaben kommen also im gesuchten Wort vor, aber an anderer Stelle. Gibt der Spieler 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.

Abbildung 2: … wobei allerdings ein Go-Programm behilflich war.

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, folgert der 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. Erfreulicherweise 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 Ausgangsworts 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 aus der angezeigten Liste mit 722 Einträgen das Wort LOTUS, 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 im Match 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 Umschalttaste 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 Computeralgorithmen wie das Zählen von Lettern in einer Zeichenkette beträchtlich. Während in Opas altem ASCII einfach jedes Byte eines Strings einen Buchstaben repräsentiert und der Rechner zum Ermitteln 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 das Hauptprogramm in dict den bis dato verfügbaren Wortschatz 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 schrumpft auf diese Weise stetig, 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 Benutzer, 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 eine Zeichenkette zurück, die die Bewertung 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 Position 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. 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.

Künstliche Intelligenz

Soweit der Wordle-Knacker – aber eigentlich sind noch nicht alle Möglichkeiten ausgeschöpft, denn selbst geschriebene Programme laden zum Experimentieren ein. Abbildung 5 zeigt eine Erweiterung der vorgestellten Funktionen, die den Automaten gegen sich selbst 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 als Ergebnis die Bewertung 10002 und arbeitet sich über dalks in sechs Schritten bis zum Ergebnis yawls vor.

Abbildung 5: Schnell zum Ziel: Der Automat spielt gegen sich selbst.

Falls Sie jetzt bezweifeln, dass es sich bei Yawls oder Dalks um im Deutschen vorkommende Wörter handelt, dann sollten Sie sich eine deutsche Scrabble-Ausgabe und ein entsprechendes Wörterbuch zulegen. In Letzterem können Sie nachlesen, 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 wie unserer sind bei den Wettbewerben allerdings nicht zugelassen. (jlu)