wordleとは
wordleとは5文字の英単語あてゲームである.
ユーザーは5文字の英単語を入力すると, 答えの単語との一致度から文字が色分けされる
- 緑=答えの英単語とその文字が位置も含め一致
- 黄=答えの英単語にそのアルファベットが含まれる
- 灰色=答えの英単語にそのアルファベットが含まれない
この入力→色づきを繰り返すことで最終的に答えの単語(緑緑緑緑緑)を引き出すゲームである.
入力できる単語には制限があり, 答えに選ばれる単語は約2300語, 質問に入力できるのは約13000個である.
↑wordleのサンプル画像. wikipediaより
wordle最適解の定式化
wordleの平均手数について考察する.
答えの単語が2300個から等確率で選ばれたとする.
その際に, 2300個の単語を以下のような木構造で分類し, その平均深さがwordleの平均手数となる.
すなわちwordleの最適解での平均手数とは, 質問(上図ではsushiやshari)に適切な単語を選ぶことで, 木構造の平均深さの最小値を求める問題である.
これは以下の２つの式を使い再帰的に計算することができる
①すべての質問をぶつけて, そのなかで最も小さい手数を探せばいい.
$$ D(W)=\min_Q \tilde{D}(Q,W)$$
②質問が$Q$のときの平均手数は1+｢そのノード(文字色)が選ばれる率｣×｢そのノード(文字色)内の平均最小手数｣で計算できる
$$ \tilde{D}(Q,W)=1+\sum_A p_A D(\mathcal{W} \cap (Qの答えがA) )$$
- $\mathcal{W}=回答候補単語の集合$
- $D(W)=回答候補が\mathcal{W}のときの平均最小手数$
- $Q=質問単語$
- $\tilde{D}(Q,W)=次の質問がQの際の平均最小手数$
- A=回答 , 緑緑緑緑緑から灰灰灰灰灰までの計238通り
この式を解くことによりwordleの最適解を求めることができるが, 計算量的に不可能である.
そのため, 次章では数値的近似解について求めていく
wordle最適解の計算高速化テクニック
可能性の高い単語に絞る
内部で木構造を作り回答$\mathcal{W}$を分類するため, これは$|\mathcal{A}|$分木の分類木と解釈できる.
分類木において, 一様分布に近い=シャノンエントロピーが大きな分類木が筋の良いそれとされている.
そのため, 各質問$Q$においてシャノンエントロピー$S$を事前に計算させ, そのうち上位$n$件を候補として採用することにした.
$$S(Q)=-\sum_A p_A(Q)\cdot \log_{ |\mathcal{A}|} p_A(Q)$$
$$p_A(Q)=\frac{|\mathcal{W}\cap(Qの回答がA)|}{|\mathcal{W}|}$$
計算打ち切り
各ノードの要素数から, そのノードにおける平均深さの下限を計算することができる.
暫定最小値を逐次計算しておき, それを下回る可能性がなくなったノードから計算を打ち切ることで計算を高速化させた.
計算結果
シャノンエントロピー上位30件まで探索したところ, 最小の平均手数は3.240手であった.
グラフの形状から3.1~3.2手でクリアできそう
ちなみに, 最初の単語はtraceがいいみたいです.
最後に
｢可能性の高い単語に絞る｣はシャノンエントロピー導出の際にアルファベットの共起性などを導入,
｢計算打ち切り｣はA*アルゴリズムで別階層間のノードとも比較をすれば, 多分もっと高度に求められると思います.
興味のある方は是非
加えて, 定式化に関しましては, このサイトを参考にさせていただきました.
謹んで感謝いたします
http://www.shinshu-u.ac.jp/faculty/engineering/chair/elec001/archive.htm