Wordle のソルバーを Python で実装する

Wordle

戦略

※早く実装を見せろという方のためのソルバーの実装はこちら

Wordle では序盤は当てずっぽうで単語を入力して情報を得ていき、その情報をもとに後半で正解を狙いに行くというのが一般的な戦略かと思われます。
本ソルバーではできるだけ当てずっぽうの精度を高めた単語を入力していき、候補が一意に定まった際に解答を提出するという戦略を取ります。

精度向上

精度の定義

本記事では、当てずっぽうの精度を高めるということを、ある単語を入力した際に得られる情報量を最大化することであると定義します。

情報量の定義は以下です。

I=\log \frac{1}{p}=-\log{p}

$p$ はある事象が起こる確率です。
正解候補 (初手は5文字の単語全て) が $C$ 個あるとしたら、情報量は $-\log{1/C}$ となります。
入力によって得られる情報で候補 $c$ 個まで減らせるとすると、得られる情報量は以下のようになります。

\begin{align}
-\log{1/c} - (-\log{1/C}) &=& \log{C} - log{c} \\
&=& log C/c
\end{align}

従って、$c$ を最小化することで得られる情報量を最大化できることがわかります。

c の期待値

現在の正解候補のうち $i$ 番目のものを $C_i$ とすると、ある文字列 $s$ を入力した際の $c$ の期待値は以下のようになります。

E[c] = \frac{1}{C}\sum_{i=1}^{C}cand\_num(s, C_i)

ここで、 $cand\_num$ は正解が $C_i$ のとき、文字列 $s$ を入力すると、正解の候補がいくつに絞られるかを計算する関数です。

入力結果から得られる情報について

$cand\_num$ では入力結果から得られた情報を使って、現在の正解候補から値を絞っていくことになります。
得られる情報は自明だとは思うのですが、個人的に失念していたものがあるので一応整理しておきます。

• 緑色
  • 正解文字列のそのマスがその文字であること
• 黄色
  • 正解文字列にその文字が含まれていること
  • 正解文字列のそのマスがその文字ではないこと
• 灰色
  • 正解文字列にそのマスが含まれていないこと

計算コスト削減

文字列　$s$ を正解候補の中から選択すると、上記の $c$ の期待値を $C$ 回 計算することになります。
$cand\_num$ の計算は $ \mathcal{O}(C)$ でやっているので合計の計算量は $\mathcal{O}(C^3)$ になります。
後述する実装の部分で5文字英単語の辞書を作るのですが、5文字の英単語は約6000語あり、$\mathcal{O}(C^3)$ を計算するのは中々時間がかかります。
そこで、

• 灰色より緑色、黄色が出た方が情報量が多い (※定式化はできてない)
• 単語内の出現頻度が高い文字を使えば緑色、黄色が出やすい
• 同じ文字を２度使わない方が、黄色による情報量増加を狙いやすい

ということから1手目~何手目までかは、出現頻度上位の文字のみで作られた単語を入力し、その後 $E[c]$ の計算を行うこととします。
(1手目については共通で計算できるので事前に計算すればよいのですが、執筆時点でまだ計算終わってないです…)

$N$ 手までの場合、

• 出現頻度上位 $N\times 5$文字を辞書順にソートしたもの
• $N$ 個の単語を連結し文字を辞書順にソートしたもの

のレーベンシュタイン距離が最小になるような単語の組み合わせを探します。

実装

実装は以下のリポジトリにあります。
https://github.com/yush1ga/wordle_solver

実装にはPythonを利用します。

5文字単語辞書の作成

Python の自然言語処理系ライブラリであるnltkに実装されているコーパスから5文字の英単語を抽出します。
辞書は2000語程度のものと、6000語程度のもの2種類作りました。
2000語のものはコスト削減用のレーベンシュタイン距離最小の単語群の探索に使います。
また、常用される単語の方が出題されやすそうな気がするため、単語は一応頻度順に並べておきます。

import itertools
from collections import Counter

import nltk

nltk.download("brown")
nltk.download("words")

perm = set(
    ["".join(v) for v in itertools.permutations("abcdefghijklmnopqrstuvwxyz", 5)]
)

# small dictionary
with open("5_characters_dictionary.txt", "w") as f:
    words = [
        k
        for (_, k) in sorted(
            [(v, k) for k, v in Counter(nltk.corpus.brown.words()).items()]
        )[::-1][:60000]
        if len(k) == 5 and k in perm
    ]
    f.write("\n".join(words))


# large dictionary
with open("5_characters_dictionary_large.txt", "w") as f:
    words = [
        k
        for (_, k) in sorted(
            [
                (v, k)
                for k, v in Counter(
                    nltk.corpus.brown.words() + nltk.corpus.words.words()
                ).items()
            ]
        )[::-1]
        if len(k) == 5 and k in perm
    ]
    f.write("\n".join(words))

コスト削減のためのN手目までの単語の探索

結構な割合が計算コスト削減戦略の単語になってしまって少し残念なのですが、色々試した結果　$N=3$ としました。

import itertools
from collections import Counter

import Levenshtein
from tqdm import tqdm

with open("5_characters_dictionary.txt") as f:
    dictionary = f.read().rstrip().split("\n")
print("num of words:", len(dictionary))

frequency = sorted([(v, k) for k, v in Counter("".join(dictionary)).items()])[::-1]
print("character frequency", frequency)
top = "".join(sorted([v for _, v in frequency[:15]]))
print(top)

min_dist = (1e9, 1e9)
min_combinations = []
for v in tqdm(itertools.combinations(dictionary, 3)):
    joined_part = "".join(sorted(v[0]) + sorted(v[1]) + +sorted(v[2]))
    joined_all = "".join(sorted("".join(v)))
    dist = (
        Levenshtein.distance(top, joined_all),
        Levenshtein.distance(top, joined_part),
    )
    if dist == min_dist:
        if dist == 0:
            print(v)
        min_combinations.append(v)
    elif dist < min_dist:
        print("update dist", dist)
        min_dist = dist
        print(v)
        min_combinations = [v]
print(min_dist, min_combinations)

結果は ["dance", "hilum", "ports"] となりました。

ソルバー

後は上記に基づいてソルバーを実装するだけです。
長いので GitHub 上で御覧ください。
https://github.com/yush1ga/wordle_solver/blob/bc63adda114dc28239e513d4b266f6b897e4574c/solver.py#L7-L79

結果

solver.py を main で実行するとシミュレータが辞書にある単語が正解であった場合に対してシミュレーションを行います。

$ poetry run python solver.py
couldn't solve 27 ['wears', 'waxed', 'gears', 'cages', 'binds', 'waker', 'wafer', 'unbog', 'unbet', 'unbed', 'taver', 'taker', 'scrab', 'sayer', 'sawer', 'saker', 'pager', 'liber', 'lager', 'kiver', 'fudge', 'firth', 'brith', 'boist', 'bield', 'barth', 'barse']
mean turn of solution 4.153631742908674

６回以内に解けなかった単語は6126単語中27単語ありました。
解けた場合は4.15回で解けているようです。

本日の Wordle

インタラクティブなソルバーも実装したので、これを用いて実際の Wordle を解くことができます。

$ poetry run python interactive.py

本日の Wordle を解いてみました。

Wordle 218 4/6

⬜⬜⬜🟨⬜
⬜🟨⬜⬜🟨
🟨⬜🟨⬜⬜
🟩🟩🟩🟩🟩