Wordleの初手考察

はじめに

今回の記事はタイトルにもあるようにWordleの初手について考察を行っていく。Wordleは非常に有名なゲームなのでそのルールの説明はここでは省略するが、Wordleをやったことがある人なら誰しも一度は「これ初手は何にするのが最適なんだ？」と疑問を覚えたことがあると思う。今回の記事ではそんなお悩みを解決するべくあやふやな議論でWordleの初手としてふさわしい単語とは何か、について考えていこうと思う。

Wordleというゲームの性質

まず、Wordleの著しい特徴として「一人有限確定完全情報ゲーム」である、というのが挙げられる（ラノベ風、間違ってたらごめんなさい）。つまり、プレイヤーは一人で、有限の手順で終了し、確率的要素がなく、全ての情報がプレイヤーに公開されている。そしてこれらの特性から「Wordleには終了までの回答数の期待値を最小化するような最適な戦略が存在する」ということがわかる。これについて詳しく説明するために、これからの議論で重要になってくる考え方や概念を書いていく。
まず、ゲームのある段階において、「それまでの結果と矛盾しない解の候補」の集合をAとし、Aの要素数をBとする。例えば初手について考えると、AはWordleに登録されている全ての単語の集合と一致する。また、ゲームの最後の方ではAに含まれる要素数、つまりBが2〜3個になっていることもあるだろう。
このようにA、Bを設定すると、Wordleというゲームは「AやBをなるべく小さくしていくことが重要そうだ」ということがわかる。
ここで、まだ何も回答していない時のA,BをA (0),B(0)とし、i回目の回答をした後のAをA(i)、その時のBをB(i)とすると、さらにいろいろなことがわかる。まず、B(i)は狭義単調減少である（同じ回答を入力することは明らかに最適な戦略ではないため）。次に、i+1回目の回答で正解する確率は1/B(i)である。（ここでは登録されている全ての単語について、それらが解となる確率は均等であるとしているが、そうでなくても適切な重みづけを行うことで同じような議論ができると思う。）
また、n回目までの回答で正解する確率もB(i)(i=0,1,,,,n-1)を用いて計算できる（式は簡単だけど面倒なので省略）。

Wordleの最適解

そして最適解を考える上で非常に重要なのが、A(i-1)とi番目の回答からB(i)の期待値を決定することができる、ということだ。具体的な計算方法としては、i番目の回答を決定すると、A(i-1)に含まれる全ての解候補aについて、aが実際の解だったらA(i)がどのような集合になるかを決定することができる。そしてそれぞれのA(i)についてB(i)を計算し、その平均を取ることでその回答をした際のB(i)の期待値を計算することができる。
さらにこの計算はそのままA(i+1),A(i+2),,,と続けていくことができる（計算量は爆発的に増えてしまうが）。そのため、最初のA(0)さえ与えられれば、あるnについてB(n)の期待値が最小となるような回答集合や、n回目までの回答で正解する確率が最大となる回答集合を決定することができる。もちろん、実際に入力した回答とそれによって得られた情報からB(i)などをその都度計算し直すこともできるので、常に最適な戦略をとり続けることが計算で可能となる。そのため、コンピュータ的にはこれで今回の話はおしまいである。（一応言っておくと、十分な量のアカウントがあればA(0)は調べることができる）

じゃあ僕たちはどうするんだ

しかし、当然ながら手計算でそれらの計算を行うことはほとんど不可能に近く、またコンピュータを用いようとしてもそもそもA(0)は与えられていない（調べることはできるし、たかだか26^5程度のサイズだということはわかっているが）。
そのため、ここからはいくつかの正しそうな仮定を置くことで、計算や考え方を簡略化し、実際に実行できそうなアイディアを考えていくこととする。
まずは大胆な仮定として「あるA(i-1)が与えられた時のi番目の最適な回答は、B(i)を最小化するもの」をおく。本来は考えたいあるnについてB(n)の値を最小化する回答集合、あるいはn回目までに正解となる確率を最大化する回答集合が最適なものであるが、B(i)が単調減少であることと僕の勘が、この仮定をおいてもそこまで最適な戦略からは外れないはずだと言っているのでこの案を採用する。すると考えなければならない回答の数が一つだけとなり、計算量がグッと減ることがわかる。
次に、重要な事実として「k=0,1,,,,i-1番目に回答した単語に含まれていないアルファベットをi番目の回答に含めると、必ずB(i)は小さくなる」というのを考える。そしてこれの最も重要なところが、B(i)がどれくらい小さくなるかを簡単に計算することができる、ということだ。
具体例を挙げると、A(0)が与えられた時に最初の回答として「watch」を入力したとする。そして「watch」の「w」に注目すると、A(0)に含まれる各単語は必ず「w」を含むか含まないかで分けることができる。A(0)に含まれる全ての単語のうち、「w」を含むものの割合をpとすると(0<p<1)、正解の単語に「w」が含まれる確率もpとなる。そのため、初手で「watch」と回答してB(0)からB(1)に解候補のサイズが減少する際の「w」の寄与分を考えると、確率pでBのサイズがp倍され、確率(1-p)でBのサイズが(1-p)倍されることがわかる。
この減少量について確率で重み付けした平均を考えると、
p*p+(1-p)*(1-p) =2p^2-2p+1
                             =2(p-1/2)^2+1/2
となる。つまり、初手に「w」を含んだ単語を回答すると、解候補の集合のサイズB(1)が平均して2(p-1/2)^2+1/2倍される、ということだ。さらにこの2(p-1/2)^2+1/2という式はp=1/2で最小化されることが容易にわかる（要は二分探索）。
ここで、さらに二つの仮定を置く。
①pが1/2に近いアルファベットがたくさん含まれている単語ほど、B (i)を小さくする
②全てのアルファベットについてp≤1/2が成り立つ
仮定について少し説明すると、まず①はまあそんなに的外れではないと思う。実際は回答した際に得られる情報にはそのアルファベットが含まれるかどうかだけではなく、位置が正しいかどうかというのも含まれているが、今回は特に初手について考えているので、そこまで大きく影響はしないと思う。
②は少し怪しい気もするけど、僕の体感として出現確率が大きそうなsやeなどでもその確率は1/2を下回っていると思うので、おそらく大丈夫（もしかしたらアルファベットにおけるジップの法則のようなものがあるかもしれないけど）。
そして②を仮定することで、①を達成するにはとにかく出現確率が大きそうなアルファベットがなるべく多く含まれた単語が最適である、ということがわかる。
そして、これが今回の結論である。

Wordleの初手で有効なのは、出現確率が高いアルファベットがなるべく多く含まれている単語

おすすめの初手

初手で有効そうな単語の条件は上で挙げたので、その条件を満たす単語を二つ紹介する。それが「scent」と「earth」だ。どちらも、単語を構成するほとんどのアルファベットが、他の単語でもよく出てきそうな顔をしているのがわかると思う。

といったところで今回の記事は終了です。最適な戦略をとり続けた時の、正解に辿り着くまでに必要な回答数の期待値などもなんとなく計算できそうだけど、それはまた今度気が向いたら。
意見や反論があったらぜひ言ってください。それでは。