W0RDLEの攻略法について

一部の界隈で急に流行りだした[**WORDLE**](https://www.powerlanguage.co.uk/wordle/)の**攻略法**を考えました。すぐ終わるだろうと軽い気持ちで取り組んだのですが、**思いの外に奥深いテーマ**だったので取り上げます。
## WORDLEのルール
基本的なルールは、**1人版のHIT&BLOW**と考えて差し支えありません。**5文字の英単語**を、**6回以内**の予測で当てることができれば成功です。1回の予測につき、「**位置のあっている文字**」と「**位置は間違っているが、正解の中に含まれる文字**」をそれぞれ知ることができます（詳しいルールは割愛します）。WORDLEに特徴的だと思われる点は以下です。
### 正解の単語中に同じ文字が2つ以上含まれている場合がある
通常のHIT&BLOW（あるいはヌメロン）では、同じ文字が2度以上含まれる単語は正解（の候補）としないことが多いです。一方WORDLEでは、例えば"**SILLY**"といった、**同じ文字が2度以上用いられる単語も正解**となることがあります。

### 予測する単語中に同じ文字が2つ以上含まれる場合の挙動
予測する単語に同じ文字が含まれる場合、**どちらも黄色や緑色となることはありません**。おそらく、**以下のような手順**で緑や黄色の判定が行われています[1]。

1. 入力単語の1文字目から順番に、緑色になるかどうかをチェックする。緑色になったら、**答えの単語中の該当文字を削除する**（ただし、残った文字の左詰めなどはしない）。
2. 入力単語の1文字目から順番に、答えの単語と左から一文字ずつ、黄色になるかどうかを判定する。黄色になったら、**答えの単語中の該当文字を削除する**（左詰めしない）。
3. 残りの文字を黒色にする。

太字の部分が特徴的です。これによって、挙動は以下のようになります（緑をG、黄色をY、黒色をBでそれぞれ表記。文献[1]で示されていた例をお借りしました）。

- 答え:"HOTEL"　予測:"SILLY"　→　結果:"BBYBB"
- 答え:"DAILY"　予測："SILLY"　→　結果:"BYBGG"

### 「予測できる単語」と「正解となりうる単語」のワードセットが異なる
5文字を適当に構成できるわけではなく、**英単語として意味のある5文字**を選ばなければいけません。この時、予測に使える単語かどうかは[**12972個**からなるワードセット](https://github.com/alex1770/wordle/blob/main/wordlist_all)に含まれているかで判断されます。一方で、答えとなりうる単語は[**2315個**からなる、別のワードセット](https://github.com/alex1770/wordle/blob/main/wordlist_hidden)に含まれているもののいずれかです。比較的メジャーな単語が答えとなる一方、幅広い単語を予測に使えるという特徴があります。

## 解く
### 前座
解きましょう。ここからが本題です。様々なアプローチが考えられますが、直感からすると**以下の事柄が成り立ちそう**です。

1. **緑**を引くと、**一気に絞れる**
2. **黄色**は、緑ほどではないが、あると**そこそこ絞れる**
3. **灰色**は単体ではあまり役に立たないが、**全て灰色だとそれはそれで絞れる**

3.を無視すれば、**緑や黄色をできるだけ多く含む単語を試すのが得**（すなわち、"q"のような出現頻度の低い文字を含む単語をテストするのは損）と言えます。これを踏まえれば、テストする単語は以下のようにすることで上手く選べそうです。

```python
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**](
http://sonorouschocolate.com/notes/index.php?title=The_best_strategies_for_Wordle)ではさらに興味深い手法を提案しています。まだしっかりと読めていませんが、本手法と同様に再帰的に必要な手数を求めていく方針のようです。

## 所感
定式化と実装がかなり楽しかったです。きれいに実装できたときは図書館で静かに感動しました。そのうち2段階目での近似なども行ってみたいです。読んでいただきありがとうございました。
## 文献
[1] [**The best strategies for Wordle**](
http://sonorouschocolate.com/notes/index.php?title=The_best_strategies_for_Wordle) By Alex Selby, 19 January 2022.
[2] [**Wordleの最善手をめぐる巷説と、真の答え**](https://xcloche.hateblo.jp/entry/2022/01/24/212558#f-96c5f13f) By xcloche,  24 January 2022.