Der Wordle-Solver: ein Algorithmus aus der Informationstheorie

Was ist Wordle überhaupt?

In 6 Versuchen ein 5-Buchstaben-Wort erraten. Nach jedem Rateversuch färbt das Spiel jeden Buchstaben:

• A grün — Buchstabe ist an der richtigen Position im Lösungswort
• A gelb — Buchstabe kommt im Lösungswort vor, aber an einer anderen Position
• A grau — Buchstabe ist nicht im Lösungswort

Beispiel: das Lösungswort ist INSEL. Du rätst SPIEL. Wordle färbt:

SPIEL

E und L sitzen schon an der richtigen Stelle (Position 4 und 5) — grün. S und I sind zwar in INSEL enthalten, aber an anderen Positionen (gelb): S müsste an Position 3 stehen, I an Position 1. P kommt in INSEL gar nicht vor (grau). Aus diesen Hinweisen grenzt sich die Lösung Schritt für Schritt ein — in diesem Fall genug, um beim nächsten Versuch INSEL direkt zu treffen.

Zwei Wortlisten

Im deutschen Wordle (Basis: 6mal5.com) gibt es zwei Wortlisten, und das ist wichtig:

• Lösungswörter (~1070): die kuratierte Menge derer, aus denen das Spiel das tägliche Rätselwort zieht. Gängige Wörter, keine Eigennamen, kein Fachvokabular.
• Erlaubte Rateversuche (~3500): alles was man als Versuch eingeben darf, inklusive seltener Wörter und alter Schreibweisen. Werden nie als Lösung gewählt, helfen aber Information zu sammeln (man kann z.B. ein seltenes Wort raten nur um viele Buchstaben gleichzeitig auszuprobieren).

Wenn der Solver später Vorschläge zeigt, markiert er Wörter, die auch in der Lösungswörter-Liste stehen — das heißt: dieser Vorschlag könnte zugleich die echte Lösung sein, nicht nur eine Informations-Probe.

Das Solver-Tool

Auf /wordle/solver/ gibt es ein kleines Tool: man trägt seine bisherigen Wordle-Versuche samt Farb-Feedback ein, und das Tool schlägt die mathematisch besten nächsten Versuche vor. Wie funktioniert das? Die Antwort kommt aus der Informationstheorie — und ist erstaunlich kompakt, ungefähr 100 Zeilen Python.

Das Problem

Nach jedem Versuch im Wordle weißt Du mehr über das Lösungswort. Aus den Farb-Hinweisen (grün/gelb/grau) lässt sich die ursprüngliche Menge von ~1070 möglichen Lösungen Schritt für Schritt einschränken: alle Wörter, die nicht zum bisherigen Feedback passen, fallen raus.

Die Wörter, die nach allen bisherigen Versuchen noch übrig sind — also alle Farb-Hinweise erfüllen —, nennen wir die verbliebenen Kandidaten. Sie sind genau die Wörter, die noch die Lösung sein könnten.

Beispiel: Zu Beginn hast Du 1070 Kandidaten. Du rätst RATEN, Wordle färbt:

RATEN

Damit fallen alle Wörter raus, die ein R, T oder N enthalten, oder die kein A bzw. kein E haben, oder bei denen das A an Position 2 / das E an Position 4 steht. Übrig bleiben — beispielsweise — noch 18 Kandidaten. Jetzt brauchst Du Versuch Nummer 2.

Naive Strategie: Du rätst eines der 18 verbliebenen Wörter direkt. Mit etwas Glück trifft Du — die Wahrscheinlichkeit ist 1/18 ≈ 5,5%. Mit weniger Glück (94,5% der Fälle) eliminierst Du genau ein Wort aus der Liste, kriegst noch etwas Farb-Feedback, und schaust auf vielleicht 5–8 verbleibende Kandidaten — denn ein Versuch aus der Kandidatenliste filtert oft nicht besonders scharf. Verschwenderisch in dem Sinn: Du nutzt Versuch Nummer 2 hauptsächlich, um eine einzelne Möglichkeit abzuhaken, statt Information über alle 18 zu sammeln.

Bessere Strategie: Du rätst ein Wort, das nicht unbedingt selbst zu den 18 Kandidaten gehört — Hauptsache, es teilt die 18 Kandidaten gut auf, je nach Farb-Feedback, das es zurückbekommt. Ideal: das Feedback zerlegt die 18 in viele kleine Gruppen mit je 1–2 Wörtern. Egal welches Feedback dann tatsächlich kommt, Du landest in einer kleinen Gruppe und weißt damit fast schon die Lösung.

Statt also „1 von 18 eliminieren" zu versuchen, will man „die 18 auf 1–2 zusammenstauchen" — und das geht oft besser mit einem Wort außerhalb der Kandidatenliste, das aber neue, noch unbekannte Buchstaben durchprobiert.

Das ist eine klassische Aufgabe aus der Informationstheorie.

Feedback-Pattern

Bei jedem Rateversuch gibt es 3 Farben pro Position und 5 Positionen — also 3⁵ = 243 mögliche Feedback-Muster, von „alles grau" bis „alles grün".

Beispiel (wie oben): Versuch SPIEL gegen Lösung INSEL ergibt:

SPIEL

Als kompakte Notation: ?.?!! (mit . = grau, ? = gelb, ! = grün).

Jedes Pattern teilt die Menge der Lösungs-Kandidaten in 1 von 243 Gruppen ein — die Wörter, die zu diesem Pattern passen. Ein gutes Rate-Wort verteilt die Kandidaten möglichst gleichmäßig über viele Patterns; ein schlechtes klumpt viele Wörter in wenige Patterns zusammen. Konkret an zwei Beispielen, jeweils gegen die 1070 deutschen Lösungs-Kandidaten:

SARTE als Startwort: die 1070 Lösungen verteilen sich auf 122 verschiedene Feedback-Muster, die größte Gruppe enthält 94 Wörter. Die Verteilung fällt sanft ab — viele kleine Gruppen, ein paar mittelgroße, keine riesigen Klumpen.

ELLEN als Startwort: nur 63 verschiedene Patterns — und die größte Gruppe enthält 209 Wörter (das ist 1/5 aller Kandidaten!). Mit doppeltem L und doppeltem E hat das Wort wenig Buchstaben-Vielfalt; viele Lösungen kollabieren auf dasselbe Pattern (z.B. „alles grau" — kein L, kein E, kein N). Im schlimmsten Fall, wenn Wordle Dir nach ELLEN „alles grau" zurückgibt, weißt Du nur „die 4 Buchstaben sind nicht im Wort" — und schaust auf 209 verbleibende Kandidaten.

Beide Wörter haben die gleichen 1070 möglichen Lösungen — aber die Verteilung im Pattern-Raum ist komplett unterschiedlich. Das ist der zentrale Effekt, den der Solver misst und maximiert.

Entropie als Maß

Die Informationstheorie liefert das passende Maß: die Entropie \(H(g)\) eines Rate-Worts \(g\) gegenüber einer Kandidatenmenge \(C\).

Für jedes Pattern \(p\) aus den 243 Möglichkeiten ist \(P(p \mid g, C)\) der Anteil der Kandidaten in \(C\), die bei \(g\) das Pattern \(p\) erzeugen würden. Die Entropie ist dann:

Ein paar Intuitionen:

• Wenn \(g\) alle Kandidaten auf ein einziges Pattern lenkt, ist \(H(g) = 0\) — null neue Information, der Versuch war nutzlos.
• Wenn \(g\) die Kandidaten auf 8 gleich große Gruppen verteilt, ist \(H(g) = \log_2 8 = 3\) Bits.
• Wenn \(g\) jeden Kandidaten auf ein eigenes, eindeutiges Pattern abbildet (im Idealfall), ist \(H(g) = \log_2 |C|\) Bits — die maximale Information die geht.

Beste Wahl: das Rate-Wort \(g\) aus dem Erlaubt-Pool, das \(H(g)\) maximiert. Genau das tut der Solver.

Algorithmus in Python

Der Code ist erstaunlich kurz. Drei Funktionen reichen.

Schritt 1: das Feedback-Pattern eines Versuchs gegen ein Ziel berechnen. Wordle-Feedback hat einen Kniff bei Doppelbuchstaben — den verbreiteten zweistufigen Algorithmus:

def pattern(guess: str, target: str) -> int:
    """Wordle-Feedback als int (ternary, 5 Stellen).
    0 = grau, 1 = gelb, 2 = grün."""
    result = [0, 0, 0, 0, 0]
    remaining = list(target)
    # Pass 1: grün (exakte Position). Verbraucht den Buchstaben im Target.
    for i in range(5):
        if guess[i] == remaining[i]:
            result[i] = 2
            remaining[i] = None
    # Pass 2: gelb (im verbliebenen Target enthalten).
    for i in range(5):
        if result[i] == 0:
            try:
                j = remaining.index(guess[i])
            except ValueError:
                continue
            result[i] = 1
            remaining[j] = None
    # Kodiere als ternäre Zahl
    p = 0
    for v in result:
        p = p * 3 + v
    return p

Der Zwei-Pass-Trick ist wichtig: wenn man BEERE gegen RENTE rätst, ist das erste E (Position 2) grün (Position 2 in RENTE ist E), das zweite E (Position 3) ist gelb (es gibt nur ein E in RENTE, und das ist schon verbraucht für die grüne Position). Naiv (ohne Pass-1-Verbrauch) würde man fälschlich zwei gelbe E zeigen.

Schritt 2: Entropie eines Rate-Worts gegen eine Kandidatenmenge.

def expected_entropy(guess: str, candidates: list[str]) -> float:
    counts = defaultdict(int)
    for t in candidates:
        counts[pattern(guess, t)] += 1
    n = len(candidates)
    h = 0.0
    for c in counts.values():
        p = c / n
        h -= p * math.log2(p)
    return h

Schritt 3: das beste Rate-Wort aus dem erlaubten Pool finden.

def top_n_hints(candidates, guess_pool, n=3):
    cand_set = set(candidates)
    scored = []
    for g in guess_pool:
        h = expected_entropy(g, candidates)
        scored.append((h, g, g in cand_set))
    # Tie-Breaker: bei gleicher Entropie bevorzuge Kandidaten
    scored.sort(key=lambda x: (-x[0], not x[2], x[1]))
    return scored[:n]

Das war's. Drei Funktionen, vielleicht 30 Zeilen ohne Kommentare.

Performance

Für die initiale deutsche Wordle-Lösungsliste (1070 Wörter) und den Erlaubt-Pool (3604 Wörter) macht der Solver

In Python ohne Optimierung läuft das in etwa 6 Sekunden — schnell genug, dass kein Caching nötig ist. Nach dem ersten Versuch ist die Kandidatenmenge typischerweise auf 50–200 reduziert, dann braucht der Solver weniger als eine Sekunde.

In der erweiterten Variante (Standard + ngerman, ~3650 Lösungen × ~5600 Erlaubt) verlängert sich die initiale Berechnung auf etwa 30 Sekunden. Die Box im Solver zeigt einen Lade-Hinweis während dieser Zeit. Sobald man einen Versuch eingegeben hat, ist auch hier die Antwort unter einer Sekunde.

Top-Startwörter (Standard-Liste)

Was sind die besten ersten Versuche? Der Solver hat klare Favoriten:

Die Spalte „Auch Lösungswort?" sagt, ob das Rate-Wort auch in der ~1070-er Lösungs-Liste steht — also als tatsächliches Tagesrätsel-Wort in Frage kommt. „nein" heißt: das Wort dient nur zur Information, kann aber nie die Lösung sein.

Kurz zu SARTE — das Wort steht zwar im Duden, kennt aber kaum jemand: Sarten (von russisch Sart) war im 19. Jahrhundert die ethnologische Bezeichnung für die türkischsprachige, sesshafte Bevölkerung im russisch beherrschten Teil Zentralasiens; in der ersten Hälfte des 20. Jahrhunderts kam der Begriff außer Gebrauch. Mathematisch ist SARTE damit zwar der optimale Startwort, praktisch eine schlechte Wahl — niemand würde es im Spiel raten.

5.89 Bits heißt: nach dem ersten Versuch eliminiert man im Schnitt 98% der Kandidaten. Die 1070 Lösungen schmelzen auf typischerweise 17–20 zusammen.

Praktisch besser als SARTE ist RATEN: fast genauso gut (5.82 vs 5.89 Bits) und gleichzeitig selbst ein Lösungskandidat. Im Glücksfall trifft man direkt; sonst hat man trotzdem viel Information gewonnen.

Übrigens: die englischen Top-Startwörter (SALET, CRANE, SLATE) folgen demselben Muster — fünf verschiedene Buchstaben aus den häufigsten der Sprache (E, A, R, I, O, T, N, S, L). Im Deutschen sind das dieselben außer dem O — dafür kommen die häufigen Endungen -EN, -ER, -TE ins Spiel.

Endphasen-Heuristik

Es gibt einen Fall, in dem der Solver bewusst vom „maximalen Info-Gewinn"-Prinzip abweicht: wenn nur noch ein oder zwei Kandidaten übrig sind, rät er direkt einen Kandidaten statt ein maximal-explorativ informatives Wort.

Logik: bei zwei Kandidaten ist die Wahrscheinlichkeit ½, beim Raten direkt zu treffen. Eine maximal-explorative Probe (die nicht selbst Kandidat ist) eliminiert garantiert einen — aber kostet trotzdem einen Versuch. Erwartete verbliebene Versuche:

• Kandidat raten: \(\tfrac{1}{2} \cdot 0 + \tfrac{1}{2} \cdot 1 = 0.5\)
• Explorations-Probe: \(1 + 0 = 1\)

Also lieber gleich raten. Ab drei Kandidaten kippt die Rechnung schon — dann ist Explorieren wieder besser. Aber das ist Edge-Case; der Solver behandelt nur die ≤2-Kandidaten-Endphase als Sonderregel.

Was der Solver nicht tut

Das gezeigte Verfahren ist Greedy mit Ein-Schritt-Lookahead: für jeden Versuch wählt es das Wort mit höchster Entropie jetzt, ohne weiter in die Zukunft zu schauen.

Mathematisch optimal wäre Multi-Step-Lookahead: für jeden Versuch nicht nur die direkte Entropie maximieren, sondern auch berücksichtigen, welche Folge-Versuche dann optimal sind. Alex Selby hat das für englisches Wordle 2022 komplett durchgerechnet — Ergebnis: SALET als bester Start, garantiert maximal 5 Versuche, Durchschnitt 3.42. Das ist deutlich aufwändiger (rekursive Minimax-Suche), bringt aber praktisch wenig zusätzlich: greedy mit Entropie liegt schon nahe am Optimum.

Für deutsches Wordle ist mir keine analoge Komplettlösung bekannt — wäre aber rechenbar.

Code und Spielen

Der Solver-Code lebt in der Wordle-App von PyGround: wordle/solver.py ist eine reine Python-Bibliothek (~100 Zeilen), die pattern(), expected_entropy() und top_n_hints() bereitstellt.

Selber spielen: Wordle DE auf /wordle/. Selber rechnen lassen: der Solver auf /wordle/solver/.