一部の界隈で急に流行りだしたWORDLEの攻略法を考えました。すぐ終わるだろうと軽い気持ちで取り組んだのですが、思いの外に奥深いテーマだったので取り上げます。
WORDLEのルール
基本的なルールは、1人版のHIT&BLOWと考えて差し支えありません。5文字の英単語を、6回以内の予測で当てることができれば成功です。1回の予測につき、「位置のあっている文字」と「位置は間違っているが、正解の中に含まれる文字」をそれぞれ知ることができます（詳しいルールは割愛します）。WORDLEに特徴的だと思われる点は以下です。
正解の単語中に同じ文字が2つ以上含まれている場合がある
通常のHIT&BLOW（あるいはヌメロン）では、同じ文字が2度以上含まれる単語は正解（の候補）としないことが多いです。一方WORDLEでは、例えば"SILLY"といった、同じ文字が2度以上用いられる単語も正解となることがあります。
予測する単語中に同じ文字が2つ以上含まれる場合の挙動
予測する単語に同じ文字が含まれる場合、どちらも黄色や緑色となることはありません。おそらく、以下のような手順で緑や黄色の判定が行われています[1]。
- 入力単語の1文字目から順番に、緑色になるかどうかをチェックする。緑色になったら、答えの単語中の該当文字を削除する（ただし、残った文字の左詰めなどはしない）。
- 入力単語の1文字目から順番に、答えの単語と左から一文字ずつ、黄色になるかどうかを判定する。黄色になったら、答えの単語中の該当文字を削除する（左詰めしない）。
- 残りの文字を黒色にする。
太字の部分が特徴的です。これによって、挙動は以下のようになります（緑をG、黄色をY、黒色をBでそれぞれ表記。文献[1]で示されていた例をお借りしました）。
- 答え:"HOTEL" 予測:"SILLY" → 結果:"BBYBB"
- 答え:"DAILY" 予測："SILLY" → 結果:"BYBGG"
「予測できる単語」と「正解となりうる単語」のワードセットが異なる
5文字を適当に構成できるわけではなく、英単語として意味のある5文字を選ばなければいけません。この時、予測に使える単語かどうかは12972個からなるワードセットに含まれているかで判断されます。一方で、答えとなりうる単語は2315個からなる、別のワードセットに含まれているもののいずれかです。比較的メジャーな単語が答えとなる一方、幅広い単語を予測に使えるという特徴があります。
解く
前座
解きましょう。ここからが本題です。様々なアプローチが考えられますが、直感からすると以下の事柄が成り立ちそうです。
- 緑を引くと、一気に絞れる
- 黄色は、緑ほどではないが、あるとそこそこ絞れる
- 灰色は単体ではあまり役に立たないが、全て灰色だとそれはそれで絞れる
3.を無視すれば、緑や黄色をできるだけ多く含む単語を試すのが得（すなわち、"q"のような出現頻度の低い文字を含む単語をテストするのは損）と言えます。これを踏まえれば、テストする単語は以下のようにすることで上手く選べそうです。
for (w1 in wordlist):
s=0
for (w2 in wordlist):
s+=score(w1, w2) #scoreはw1とw2の"一致度"を返す関数
val[w1]=s
return key(max_val) #valが最大のワードを出力
ここでscore関数、すなわち2つのワード間の一致度は、両者を比較した際のタイルのパターンから、よしなに計算します（例えば緑が1枚あれば+2、黄色が1枚あれば+1）。ただし、この解法はかなりナイーブです。問題点として、上記の事柄1.〜3.がすべて「直感から」成り立っていることが挙げられます。すなわち、「黄色いタイルの枚数が多い」ことが、「正解までの手数を削減する」ことに繋がるという裏付けがありません。
「ワードの良さ」を定量化
前座での問題点を踏まえ、「テストするワードの良さ」を具体的な式で表してみましょう。まず、問題の定式化を行います。一回の試行で得られる情報は5枚のタイルのパターンなので、このタイルのパターンに着目することがポイントです。そのために、それぞれの文字を以下で置きます。
$t$：タイルのパターン(全部で243通り)
$w$：テストするワード
$R$：既に判明した制約を表す集合。例えば元$r\in R$が$r={(w_1,t_1)}$である場合、ワード$w_1$に対する応答がタイルパターン$t_1$であったことを表す。
$p_{w,R}(t)$：制約$R$の元でワード$w$をテストした際に、タイルパターン$t$が返ってくる確率
$S_{R}(w)$:制約$R$の元でワード$w$をテストした際の、ワード決定までに必要な手数の期待値
$\hat{S}_{R}$：制約$R$の元で、ワード決定までに必要な手数の期待値
これらの文字を用いると、制約$R$のもとで$w$をテストした場合の、ワード確定までに必要と見積もられる手数$S_{R}(w)$は以下のように表すことができます。
$$
S_{R}(w) = 1 + \sum_{t}{p_{w,R}(t)\times \hat{S}_{R \cup \{ (w,t) \}}}
$$
したがって、ある状況のもとで最適なテストワードを求めることは、以上の式の最小値を与えるような$w$を求めることに帰着されます。
Sの近似
さて、以上のように問題を定式化しましたが、$p_{w,R}(t)$や$\hat{S}$を求めることは可能なのでしょうか。
$p_{w,R}(t)$は、タイルのパターンが3^5=243通りなので、全探索すれば現実的な時間で求めることが可能です。一方で、$\hat{S}$を正確に求めるのは難しいです。この$\hat{S}$がWORDLEの探索においては重要なポイントなのですが、ここで、決定までに必要な手数の期待値$\hat{S}$を以下の式$\hat{S^{*}}$で近似してみましょう。
$$
\hat{S^{*}_R}=\log(W(R))
$$
ただし、$W(R)$は制約$R$を満たす単語の数とします。探索に必要な手数が対数ベースで与えられるというのは、二分探索などからもイメージしやすいのではないでしょうか。実際のWORDLEでは次の手から二分探索を行っていくわけではないため底が2より大きな対数として表されそうですが、全体の定数倍の違いなので本質的な差はありません。
ここまでの内容をまとめると、WORDLEの攻略は以下の$S_{R}(w)$における、wに関する最小化問題として近似的に解くことができます。
$$
S_{R}(w) = 1 + \sum_{t}{p_{w,R}(t)\times \log(W(R \cup \{(w,t)\}))}
$$
なお、様々なブログで議論されている「最も良い最初の単語は何か？」という問題は、以上で定式化した問題における$R=\emptyset$の場合に対応します。なお、$\hat{S}$を$\log$で近似せず、さらにもう一度タイルパターン$t$に関する和として計算すると、より精度の高い予測が可能です。
ソルバーの作成
以上の内容を踏まえ、上記の最小化問題を解くプログラムを実装しました。感覚としては、3手で終了することと4手で終了することが半々、といった印象です。理論上は5手かかることもあるようですが、今の所経験していません。
他文献との関連
平均情報量（エントロピー）最大化という手法を提案している文献もあります[2]。そのような文献では、
$$
S_{R}^{*}(w) = -\sum_{t}{p_{w,R}(t)\times \log(p_{w,R}(t))}
$$
の最大化を目的としています。今回紹介した式とかなり類似した形で、本質的な差はありません。
他に、[1] The best strategies for Wordleではさらに興味深い手法を提案しています。まだしっかりと読めていませんが、本手法と同様に再帰的に必要な手数を求めていく方針のようです。
所感
定式化と実装がかなり楽しかったです。きれいに実装できたときは図書館で静かに感動しました。そのうち2段階目での近似なども行ってみたいです。読んでいただきありがとうございました。
文献
[1] The best strategies for Wordle By Alex Selby, 19 January 2022.
[2] Wordleの最善手をめぐる巷説と、真の答え By xcloche, 24 January 2022.