Wordleは4つの単語を覚えるだけで必ず正解できる

# Wordleとは？

フィードバックを頼りに、隠された 5 文字の英単語を当てるゲームです。
要は「マスターマインド」や「ヌメロン」等と呼ばれるゲームの英単語版です。

知らない方でも以下のような奇妙なツイートは目にしたことがあるかもしれません。
![スクリーンショット 2022-01-29 19.53.07.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/123809/c2650482-269b-3b99-b792-283a59cca814.png)

# この記事は何？

Wordleにおいて、最初に**ある4つの単語を入力すれば 100% 正答にたどりつける**ことが Python を使った解析でわかりました。

具体的には、
- **それら 4 つの単語を入力した時点で解の候補が平均 1.1 個まで絞られる**
- **96% 以上の確率で 5 回で正答できる**
- **100% の確率で 6 回以内に正答できる**
といった感じです。

本記事では、それらの単語をどのように探したかをザックリ解説しつつ（ネタバレ防止のため）最後にその4つの単語をご紹介します。

（結果だけ見たい方は[こちら](https://qiita.com/POPOPON/items/9c4e002d70d7d11ff871#100-%E6%AD%A3%E8%A7%A3%E3%81%AB%E3%81%9F%E3%81%A9%E3%82%8A%E3%81%A4%E3%81%91%E3%82%8B%E7%B5%84)）

# 方法

色々な英単語の組み合わせに対し「それらを入力したとき、平均して何語まで解の候補が絞れるか」を計算し、その値が最も少なくなる組を探しました。

しかし Wordle で入力可能な単語は約 13000 語（そのうち答えになるのは 2315 語）もあるため、全単語の組み合わせについて計算するのは困難です。

そこで今回は、様々なヒューリスティックを用い、優秀そうな単語や組み合わせに絞って探索していくことにします。

まずはどのような組み合わせであるべきかを考察していきます。

### 使用文字が重複していないこと
できるだけ多くのフィードバックを得るためには、可能な限り同じ文字を使わないことが重要と考えられます。
そのため使用文字が被っていない単語の組についてだけ検討します。

要は、候補文字を重複なくローラーしていけるような組を探していくということです。

### 4 語の組であること

アルファベットは 26 文字あるので、文字が被らないように 5 文字の単語を作るとき、最大 5 つまで作ることが可能です。

しかし Wordle では 6 回しか回答チャンスがないため、5 回もローラーに費やすのは悪手と思われます。

また 4 回目の時点で 20 文字分のフィードバックが得られており、残り 6 文字についてもある程度は判明してきます。
（そして出現頻度の低い`j, k, q, w, x, z`辺りは実際情報が得られる可能性が低いと考えられます）

そういった理由から最大でも4つあれば十分と判断しました。

またプレイした実感から 3 語では答えを絞りこめないと思われたため、今回はひとまず 4 語からなる組のみを探すことにします。 

-------------------------------------
以上が単語の組に課す条件です。
続いては単語自体に課す条件を見ていきます。

### Wordleで入力できる単語であること

これは当然ですね。こちらは Wordle 自身から取得しました。

### 同じ文字を1度しか使わない単語であること

Wordle の単語リストには例えば「class」のような、同じ文字を2回以上使う単語が入っています。

先述の条件と同様に、そのような単語では多くの場合 4 文字分以下しかフィードバックが得られず、期待できる情報量が少なそうなのであらかじめ除外します。

```python
word_list = [word for word in word_list if len(set(word)) == 5]
```

これにより 8322 個まで単語が減らせました。

:::note info
:tada:クイズコーナー:tada:
記事の主題とは関係ないですが、同じ文字を 3 回使う 5 文字の単語もありました。
一つはエンジニアがよく目にする単語なのですが、何だかわかりますか？
（答えは記事の最後に）
:::

#### よく知られた単語であること
探索のためには 8322 語だとまだ多過ぎるため、一般的な単語に絞ってみることにしました。
（「waqfs」とか「vozhd」といった耳慣れない単語を使うのが何となく面白味に欠けるというのもあります）

これには [Googleの一般的な10000の単語リスト](https://github.com/first20hours/google-10000-english/blob/master/google-10000-english-no-swears.txt)をダウンロードし、その中に含まれる単語のみを使うようにしました。

```python
# あらかじめ単語リストは落としておく
with open('path/to/common_word_list.txt', mode='r') as f:
    common_word_list = f.read().split('\n')

word_list = [word for word in word_list if word in common_word_list]
```

これで最終的に 837 個まで単語数を減らすことができました。

------------------------------------------
あとは残った 837 語から先述の条件を満たす組を探していきます。

ここは泥臭くループを回しているだけなのでコードは省略します。

一つ工夫を上げるとすれば「同じ文字は一回しか使わない」という条件により、一度使った文字を含む単語を探索候補から消していることくらいです。

（一応[コードはこちらにあります。](https://github.com/Masa-Shin/make-4-five-letter-words-without-repetition/blob/master/src/get_4_five_letter_words.py)全く整理はされていないです）

# 結果

837語の候補単語に対し条件を満たす組を探索したところ、
`album, depth, rocky, swing`
など計 2264 組が見つかりました。

<details><summary>結果をさらに見る</summary>album, depth, rocky, swing

album, fight, rocky, spend
awful, bring, empty, shock
awful, might, rocky, spend
badge, lunch, proxy, swift
badly, grove, punch, swift
badly, quick, sperm, thong
batch, funky, pixel, sword
black, depth, forum, swing
black, fight, sperm, wound
black, judge, proxy, shift
black, judge, proxy, smith
black, judge, proxy, swift
black, sperm, width, young
blame, crowd, funky, sight
blame, crowd, funky, sixth
blame, dutch, proxy, swing
blame, funky, pitch, sword
blank, judge, proxy, shift
blank, judge, proxy, smith
blank, judge, proxy, swift
blank, judge, proxy, witch
blend, proxy, quick, shaft
blink, judge, match, proxy
blink, judge, proxy, shaft
blink, judge, proxy, watch
block, empty, fraud, swing
brick, empty, flash, wound
brick, empty, flush, wagon
brown, depth, lucky, sigma
brown, empty, flash, quick
bunch, medal, proxy, swift
cable, funky, might, sword
child, funky, grove, stamp
climb, forth, judge, spank
climb, forty, judge, spank
climb, judge, party, shown
climb, judge, proxy, shaft
...
</details>

### 最も優秀な組はどれか？
この 2264 組について「4語すべて入力した後に残る解候補数の期待値」を計算しました。

解候補数の期待値が最も少なかったのは、
`cyber, might, spank, would`
で、平均 1.07 語まで絞れるという結果になりました。

（使用しない文字は`f, j, q, v, x, z`）

**93.3%の確率で解候補数が 1 つに定まるため、ほとんどの場合 5 回目で正答することができます。**

残る単語数は最大でも 3 語で、その最大値を取る正解単語は 18 個だけありました。

この 18 個について「残り 2 回のチャンスで確実に正答できるか」を検証するのは面倒だったので「解候補数が2つ以下になる確率が最も高い組」を探し、それについて検証することにします。

### 100% 正解にたどりつける組
解候補数が 2 つ以下になる確率が最も高かったのは、
`moved, plans, rugby, witch`でした。

（使用しない文字は`f, j, k, q, x, z`）

**93.0%の確率で解候補が1つになり、99.7%の確率で解候補が2個以下になりました。**
差し引き 6.7 % の確率で候補が 2 個になる計算で、その場合でも一回の当てずっぽうで 1/2 の確率で正解できるため、5 回で正答できる確率は少なくとも 93.0% + (6.7 / 2)% = 96.4% 以上あることになります。

三つ以上候補が残るような正解単語は 8 語だけしかなく、
残る単語のパターンとしては、
- `['aloft', 'float', 'allot']` 
- `['tease', 'stake', 'skate', 'feast', 'state']`
の2通りしかありませんでした。
そして、どちらもあと一回で解を判別できることが簡単に検証できます。

**そのため 3 つ以上候補が残った場合も 6 回までには確実に正答できます。**

つまり理論的には`moved, plans, rugby, witch`と入力すれば、
- **96% 以上の確率で 5 回で正答できる**
- **100％ の確率で 6 回までに正答できる**
ということです。

期待値や確率の計算に使ったコードは一応[こちら](https://github.com/Masa-Shin/make-4-five-letter-words-without-repetition/blob/master/src/calculate_expected_remained_answer.py)にあります（整理はされていないです）。

### 追記：ヒントが多く得られる組
記事公開後、次のような声がありました。
- 「確かに絞られるが、ヒントが少ないと正解単語が思いつかない」
- 「確かに確実に解けるが、もっと早いターンに解きたい」

そのため「人間が解きやすい組」 = 「得られるヒントが最も多かった組」も一応載せておきます。
`grove, swift, badly, punch`

平均して緑マス 2.7 個分くらいのヒントが得られるので、早いターンで当たりを付けたりもしやすいかもしれません。
（黄色マスの価値は、その黄色マスの文字が入りうる所が n 箇所あれば「緑マスひとつ分の価値 / n」と単純に計算しています）

# まとめ
わりと単純なヒューリスティックスとコードで探索しましたが「Wordle を（ソルバーを使わず人力で）確実に攻略できる手順を見つける」という目的は果たせました。

ただ「5回目までにほぼ正答できる」というのは、戦略なしの場合と比較しそれ程優れているわけでもないので、さらに強い単語の組を見つけるのが今後の課題です。

<details><summary>クイズ「同じ文字を3文字含む5文字の単語は？」の答えを見る</summary>error, mammy, daddy, geese など
</details>