最近、twitterで🟩🟩🟨⬜⬜みたいな謎の色付き正方形がいっぱいシェアされてくるようになりました。
これは「Wordle」というパズルゲームで、５文字の単語を入力して得られた手がかりから、正解の５文字の単語を当てるゲーム（その文字が正解に含まれていて位置もあっていたら🟩、含まれているが位置はあっていないときは🟨でヒントが出る*1）です。
www.powerlanguage.co.uk
Wordle、おもしろいですよね。
aseruneko.github.io
日本語版も有志によって作られたようです。
この記事では、インターネット上で囁かれているさまざまなWordleの戦略を概観・レビューした後、情報量を用いたもっとも効率的な単語の選び方を実践・解説します。
パッと思いつく戦略
プレイしていてまず思いつく戦術はこんなところでしょうか：
①いろんな単語によく含まれる文字はヒントになりやすいはず
- qとかzが含まれる単語は少ないので、手がかりに入れてもあんまり参考にならなそうなので
②一度🟩で確定したところに次またその文字を置くのは損
③なるべく多くまだ使ってない文字を入れたほうがいい
- ⬜で単語中に使われていないことが確定した文字を使うのは、ヒントを得るチャンスを逃しているので
Wordleでは最初は色のヒントなしで単語を入力するわけですが、では、このときにより多くの情報が得られる「初手」の単語は何がいいでしょうか？
巷ではさまざまなヒューリスティックな手法による初手５文字が提唱されています。
文字ベースの手法
試み①：出てくる頻度が多い順に文字を使う
slc.is
先ほどのパッと思いつく戦略で挙げたように、「とりあえず色のヒントが得られやすそうな単語を使おう」というのがいちばんはじめの発想です。Wordle全単語リスト*2 （wordleのjsファイルから候補として入れられる単語リストを取り出してきたもの）で登場したアルファベットを上から順番に並べてみると、次のようになります。
上記のブログでは、上から順にs, e, a, o, r, i, l, t,.n, u,... がよく使われているので、上位５つを含む単語、aeros, soare, aroseがいいんじゃない？ 二手目もunlitあたりがいいんじゃない？ というアイデアを提示しています。
初手案：aeros, soare, arose
試み②：その位置ごとの出現頻度が多い順に文字を使う
では、aeros, soare, aroseの三つがあったとき、どれがいちばん色のヒントを得やすいでしょうか？
ここで上記のブログが提案しているのが、位置ごとの文字の出現頻度です。
「q」を含む単語を例にとって考えてみましょう。qで始まる単語はあっても、qで終わる単語はほぼないので、５番目にqがある単語よりも１番目にqを置いたほうがよりたくさんヒントが得られそうです。
そこで、彼らは位置ごとの文字の出現頻度を比較して、aeros, soare, aroseの中でもっともスコアが高いものを選びました。
それぞれの位置でのアルファベットの出現が独立と仮定して、
P(aeros) ∝ P(1番目がa) P(2番目がe) P(3番目がr) P(4番目がo) P(5番目がs)
の近似をするのに近い発想ですね（ブログではスコアは加算していますが）。
結果、試み①で得られたうち、aerosのスコアが高かったとのことで、文字ベースでは「aeros」がいい！と結論されています。
初手案：aeros*3
文字ベース手法の課題
位置ごとの文字頻度を考える方法はいい線いっているように見えますが、仮定が多かったり根拠が不明瞭だったり、文字順にある相関（sのあとはaがきやすい、qのあとは必ずuがくる、など）等の情報をとりこぼしたりしています。
なるべく多くの色のヒントが出そうな初手にしよう、という発想はよさそうなのですが、そもそも、「よく出る文字がいっぱい入ってるのがいい手がかり」ってどういう根拠なのでしょうか？ なんとかして単語のよさを定量的にはかることはできないのでしょうか？
ここからは、これらの手法がある程度よい方法になっている背景の原理や、原理から直接的に導かれるもっとよい手法を考えてみましょう。
単語ベースの方法
Wordleというゲームは、換言すれば、手がかりとなる単語を入力して出てきた色のパターンをヒントに、全12972単語から候補を1つに絞りこんでいくゲームです。
上で紹介した文字ベースの手法は、「よくある文字でできた単語を手がかりにすると、色のパターンにバリエーションが出やすい→絞りこみやすい」ことから、ヒューリスティクスとして有用だったわけで、原理そのものである「その単語はどれくらい単語候補を絞れるか？」を直接計算して比較するのが、以下の単語ベースの戦略になります。
Automatic Wordle Solving. Taking out the fun of Wordle is fun by… | by Yotam Gafni | Jan, 2022 | Towards Data Science
手がかり単語を入力したときに出てくる色のパターンは🟨🟩⬜⬜⬜とか🟩🟩🟨⬜⬜とかですが、これは逆に見ると、12972単語あったのが、手がかり単語によってそのパターンに属する単語のグループだとわかった、と解釈できます（たとえば、"aeros" を入力してパターン⬜🟨⬜🟩🟨 が返ってくるのは、答えが escot, estoc, estop, eusol, sheol, shmoe, syboe のどれかだったときだけ）。
ここで、ミニマックス法は、「「最悪の場合（属する単語数が最多の色のパターン）でも○○個までは絞りこめますよ」の、○○がいちばん小さくなる手がかり単語を見つける」考え方です。
この手法の利点は、「最悪でもn回でゴールできる」が言えることで、ミニマックス法を使えば、５回以内に必ずクリアできる（決まった手続きに従って単語を出せば、当てられない単語はない）ことが保証されています。
初手案：aesir
しかし、この方法でもまだ絞り込みが最悪ではなかった場合の色のパターンにそれぞれ何単語が属しているかの情報が使えておらず、平均のスコアをあげるのにまだ改善の余地があります。
属する単語が最悪（マックス）付近の個数のパターンがたくさんあるのか、満遍なく小さく分割されているかで状況が変わってくるわけです。使える情報を余すことなく活用するのが、以下の平均情報量（エントロピー）最大化の手法です。
ここから先はパッとみた感じ公開された試みがなかったので、自分で実装してみることにしました。
試み④：平均情報量最大化（Greedy）
情報量は、簡単にいうと、「その事象が発生した」という情報がどれくらい意味をもつか、という尺度です。よくあることだと小さいし、滅多に起きないことだと大きな値になります。
確率pでおこる事象が観測されたとき、その事象がもつ情報量は - log(p) であらわされます。pが小さければ小さいほど大きくなるので、滅多にないことが起こったならそれは大きな情報を持っている、とする定義になっています。
確率試行で得られる情報量の期待値が平均情報量です。とれる選択肢のうち、平均情報量が最大になる試行を選ぶことで、得られる手がかりを最大にすることができます。
Wordleにおける確率試行とは何か？ その答えは、単語を入力してカラーパターンを得ることです。
得られるカラーパターン（🟩🟩🟨⬜⬜, ⬜⬜⬜⬜⬜, ⬜🟨⬜⬜🟨など）の組み合わせは、色数（🟩, 🟨, ⬜）の文字数（5）乗で243通り*4あり、「どのカラーパターンが実現するか」を確率として考えることで平均情報量が計算できます。
平均情報量Hの表式を書き下すとこんな感じになります：
ここで、それぞれのパターンになる確率は、p(🟩🟩🟨⬜⬜) = (色パターンが 🟩🟩🟨⬜⬜になる解候補の数)/(解候補の総数)のように計算されます。
平均情報量が最大になるのはカラーパターンに属する単語の数がパターンによらず均等に近いときで*5、すべての単語について平均情報量を計算することで、一回の手がかりで得られる情報の期待値が最大になる単語を明示的・定量的に発見することができます。
計算してみると、tares（スズメノエンドウ）が6.2bitほどで最大（平均的に一手めで候補を12972個から200個程度まで絞れる）になることがわかりました。
初手案：tares
とりあえず一手目だけみると、もっとも多くの情報を得ることができる単語は、TARESです。
試み⑤：平均情報量最大化（多層）／なんかすごい人
ここまできたら正直もうあんまり変わらないんですが、実は、もうちょっとだけ考えることがあります。
というのも、taresは十分強い選択ですが、平均情報量最大化は実は一手目だけで考えるのはあまりよくない（一手目では最大でも、二手目以降の影響でひっくり返りうるGreedyな選択のため）です。
全体最適まで考えると計算量が爆発してしまうので、二手目まで＆候補に残った単語だけのリストから新たに選ぶ、という制約で二手目時点での平均情報量を最大化してみたところ、salet（中世の鎧）（二手目時点で10.3bit）が最良の初手、となりました（taresだと10.25bit）。「SALET wordle」などで検索するとSALETがトップのなんかすごい別アプローチの手法なども出てきたので、このへんも読むと楽しいかもしれません（ぼくはまだしっかり読めてません）。Wordleチートシートもあるよ！
The best strategies for Wordle - Things (various)
読め
英単語を勉強し、Wordleに勝て
情報理論を学び、Wordleに勝ち、競馬にも勝て
おまけ
あとでSALETの記事を読んでいて引っかかったのだが（というかこの記事を書いていて見つけたのだが）、どうもWordleの答えは回答として使える12972単語より少ない頻出2315リストからとられている（マニアックな単語ではなく、ある程度身近な単語が使われている）らしく（wordleの実行ファイルのjavascriptを見ると「La」と「Ta」という形で単語リストの変数が分けられており、どうも解答はLa側からのみ選ばれているっぽい）、解答候補がLaのみと仮定して計算してみると、taresではなくsoareがgleedyな場合の平均情報量最大（5.89bit）となる（Taのほうの「回答可能だが解答ではない」単語はさまざまな単語の複数形が含まれるため、末尾のsが強くなっていたと思われる）。
ちなみにsoare(イギリス英語で若鷹)もtares同様、Laの解答候補リストをうまく分割はするものの、これ自体はTa単語なので一発正解はなさそうである。
Laリストのみの出現アルファベットの頻度を見るとsがだいぶ順位を下げているのがわかる
なんかもう飽きたのでやらないが……
ルールのスクリプト（参考：GitHub - yotam-gafni/wordle_solver: A python wordle solver）
def cue_to_color(cue, ans):
color = [0 for i in range(5)]
for c_ind in range(5):
if cue[c_ind] == ans[c_ind]:
color[c_ind] = 2
ans = f"{ans[:c_ind]}*{ans[c_ind+1:]}"
for c_ind in range(5):
if cue[c_ind] in ans and color[c_ind] == 0:
color[c_ind] = 1
ind_app = ans.find(cue[c_ind])
ans = f"{ans[:ind_app]}*{ans[ind_app+1:]}"
return color
単語セットからのエントロピー計算（wordのリストは前出のgithubにあります）
import numpy as np
words = [word.strip() for word in open("words.txt","r").readlines()]
def cue_to_patterns(cue, answers):
patterns = {}
for answer in answers:
color = cue_to_color(cue, answer)
if tuple(color) not in patterns:
patterns[tuple(color)] = [answer]
else:
patterns[tuple(color)].append(answer)
return patterns
def patterns_to_entropy(patterns):
counts = np.array([len(patterns[item]) for item in patterns])
freq = counts/counts.sum()
entropy = -freq.dot(np.log2(freq))
return entropy
patterns = cue_to_patterns("salet", words)
entropy = patterns_to_entropy(patterns)
