この記事は「Qiita Engineer Festa 2022」に向けて書いた記事です。
Wordleが好きなので、ソルバーを作ってみる
もうだいぶブームは去った感じがありますが、Wordleというゲームが好きでほぼ毎日回答しています。
５文字の単語を、「その文字が含まれるか」「含まれる位置はどこか」をヒントに当てるというシンプルなゲームですが、英単語であるというところが絶妙に難しさを誘うので、飽きることなく続けられています。
基本的には自分の知っている単語や想像力で解くのが楽しいわけですが、やはりエンジニアなので、ちょっとアルゴリズムを組んでソルバーを作ってみたいなと思いました。
単純に「100％解答が導き出せるソルバー」でも良いですが、やはりなるべく短い回数で答えられた方が嬉しいです。
そこで、目標として、「ほぼ95%以上の正解率で、なるべく早く（回答数少なく）正解に辿り着くソルバー」というところを目指して作ってみることにしました。
アルゴリズムを検討する
自力で解く場合
さて、とりあえず解法を検討するにあたって、まずはとっかかりとして、Wordleを普段自分で解くときに何を考えているか振り返りましょう。
- 英語においても母音(a,i,u,e,o)は重要なアルファベットなので、これを最初に特定できる単語で攻める
- ２つくらいの単語で黄色と緑がある程度出てきたら、その単語から思いつく知っている単語や、存在しそうな単語を検討する
- あとは雰囲気
んー、我ながら、勘に頼った「解法」とは程遠い方法ですね。
もうちょっと、確実に答えに近づけるように細かく検討していきましょう。
ルールからアルゴリズムの見当をつける
やはり何より重要なのは１単語目です。
ここでどれだけ対象の単語を絞り込めるかが鍵になると言えます。
しかし、「単語を絞り込む」と言っても、「全体の単語の情報」がないと何をもって絞り込めたと判断して良いかがわかりません。
恐らくここの前提が変わってしまうと結果も大きく変わってしまうのですが、とりあえず今回はWordleの単語リストとされているものを使用します。
これが本当にWordleで使われている単語リストなのかは調べきれませんでしたが、とりあえずそれっぽいのでよしとしましょう。
さて、こちらの単語リストを確認すると、およそ1万3千個の単語が含まれていることがわかります。
この中から６個選び出して正解を見つけなければならないので、なかなかハードなゲームですね。
ここで今一度ルールを確認しましょう。
「一つ単語を入力すると、その単語のそれぞれの位置の文字について、正解の単語の位置・文字と一致するか、含まれるかどうかがわかる」
このとき、ある位置の一つの文字から受け取れる情報量を考えます。
例えば１文字目にaという文字を含んだ場合、一致・含む・含まないでそれぞれ以下のようなことがわかります。
- 一致・・・正解の単語は１文字目がaで始まる。その他の文字はわからない。
- 含む・・・正解の単語は１文字目以外のどこかにaの文字を含む。
- 含まない・・・正解の単語はaの文字を含まない。
このとき、残りの単語から正解を抽出する際、どれくらい正解候補を減らすことができるでしょうか？
- 一致する場合、１文字目が確定するので、１文字目がaから始まる単語以外は確実に除外することができます。
- どこかに含む場合、１文字目がaから始まる単語は確実に除外することができます。また、aを含まない単語も除外できます。
- 含まない場合、aを含む単語は除外することができます。
これだけだと、どの場合が一番絞り込むことが可能かはなんとも言えません。
ただ、単語のリストがすでにある状態なので、そこから検討することは可能です。
単語リストによると、１文字目がaから始まる単語は737個あります。
aから始まらず、どこかにaを含む単語は4593個あります。
aを含まない単語は7642個あります。
一番絞り込めるのはaで始まる単語に当たった場合です。
これは逆に当たらなかった場合には7642個残るということを意味します。
とはいえ約1万3千件のうちaを含むか含まないかの２択では5330:7642と、比較的どちらに転んでも除外できる数は多めになりそうです。
では逆に使用頻度が少なそうな文字として、xを指定したらどうでしょう。
xから始まる単語は、なんと16個しかありません。
xを含む単語も271個しかないようです。
当たれば大きいですが、外れたら12685個も残ってしまいます。
ちょっと、確実性に欠けますね。
こうして見てみると、発想としては「クイックソート」的な発想で、なるべく半分に近い数に分割できる文字の組み合わせで単語を選ぶことで、効率的に数を減らしていくのがよさそうです。
まずはその方向で１単語目を検討してみます。
１単語目を抽出するアルゴリズム
まずは単語リストの中のアルファベットの出現数から調べて見ましょう。
各アルファベットを含む単語数を取得し、全体の数の半分にどれだけ近いかで判断します。
[
{ alphabet: 's', distance: 550, length: 5936 },
{ alphabet: 'e', distance: 781, length: 5705 },
{ alphabet: 'a', distance: 1156, length: 5330 },
{ alphabet: 'o', distance: 2575, length: 3911 },
{ alphabet: 'r', distance: 2577, length: 3909 },
{ alphabet: 'i', distance: 2897, length: 3589 },
{ alphabet: 'l', distance: 3372, length: 3114 },
{ alphabet: 't', distance: 3453, length: 3033 },
//...以下省略
]
指定したときに一番半分に近い数に分けることができるのは、sでした。
以下e,a,o,r...と続きます。
この上位の文字を使った単語を選ぶと、１単語目としては効果が期待できそうです。
また、２単語目以降についても、同様に残った単語リストの中から出現数とその半分に近く絞り込める文字を抽出していくことで、効率よく検索できそうに見えます。
ということで、これをもとにまず実装してみます。
考え方としては、先ほど計算した各アルファベット毎のdistanceの小さい順にポイントを与え、最もポイントの高い単語を選ぶ、という方法で行きます。
ポイントの付け方は一旦こんな感じでやってみました。
- ２６文字の中でdistanceの小さい順に並べ、(26 - 順位) × 2ポイントを付与することにする
- 解答候補に含まれるアルファベットから上記ポイントを加算する
- 同じアルファベットが含まれる単語はポイントを５ポイント引く
- さらに解答候補の中に使用されないことが確定しているアルファベットが含まれている場合は含まれてる文字数×２ポイントを引く
雰囲気でやってますが、なんとなく良さそうな気がします。
これでとりあえず、１万３千件の単語リストを食わせてみます。
平均回答数：４.4回
正答率：96％
回答時間：２０分
めちゃくちゃ時間かかるし、思った以上に正答率が低い・・・。
これは何か改善の余地があるのかなぁということで、不正解になったものを見つつ、ポイントの与え方を調整したりしてみました。
が、結局96％前後からそんなに改善しない・・・。
もう一度きちんとアルゴリズムを見直すことにします。
位置を加味してなかった
アルゴリズムの見直しをしたところ、解答候補を選ぶ際に、アルファベットの出現位置をちゃんと加味していなかったことに気づきました。
このゲームにおいては出現位置も重要なヒントになります。
大きな仕様漏れです。修正していきます。
とはいえそれで96%まで行ったということは、考えの方向性としては間違っていないということでもあります。
２６文字のアルファベットのみで計算していたのを、２６文字＋単語の中の何文字目か、でポイント付与し、解答候補を選ぶようにしましょう。
最初の例では各文字が含まれている場合に残りの正解候補を半分にする文字をポイント高くしていましたが、そこに何文字目かという位置を加えて、N文字目にその文字を指定した場合に残りの正解候補を半分にする文字＋位置を高ポイントとするようにしました。
また、最初の例ではポイントを単純に順位×２で計算していましたが、この方法では各文字間の重みが平準化されてしまっています。
実際には半分に近いものほどポイント高く、離れるほどポイントが低くなるべきです。
そこで、順位によるポイント制をやめ、単純に半分の単語数からの距離(distance)をそのままポイントとして、一番小さいポイントの単語を候補とするようにしました。
上記の修正と、さらに個別の不正解のパターンに応じた調整を加えて再実行したところ、以下のようになりました。
平均回答数：4.2回
正答率：99%
回答時間：８分
正答に辿り着くまでの回数が減ったため、計算量も減り、回答時間も短くなったようです。
正答率も99%と、なかなかいい数字になったんじゃないでしょうか。
ちなみに100%にはならないのか？と思って、不正解のものを確認したのですが、どう頑張っても最後の一回は運ゲーになるような単語だったのが確認できたので、再現性のあるアルゴリズムとしてはいい結果が出せたのかなと思います。
と同時に、「６回で正解を導く」というゲームのルールも、絶妙なのだなということもよくわかりました。
７回だったら100％になるのは確実なので、６回というのが正解するかどうかギリギリのラインというバランスなのでしょう。
最後に
Wordleの解き方をプログラムで書くというのは、まさに自分の思考の言語化と言える行為で、なかなか学びも多い作業となりました。
アルゴリズムの勉強をするときに、ゲームのルールを元に解法をプログラム化してみるのは、かなりいい方法なのかもしれません。
本来的にはアルゴリズムがどの程度優れているかというのは、計算量などを算出して評価をすべきですが、今回のように現実の問題（？）に対処する場合は、実際に動かして「求める性能を満たすか」という基準で評価しても良いと思います。
また、アルゴリズムは必ずしもロジックだけで決まるものではありません。
Wordleであれば、正解の候補のリストが違うものであれば、選ぶべきアルゴリズムが変わる可能性もあります。
データの偏りによって、うまく計算できなくなるアルゴリズムもあるでしょう。
そういった事態を避けるためにも、まずはアルゴリズムを考える前に、きちんと状況を整理するということが大事だなと感じました。
今回も最初のやり方では「アルファベットの出現位置」という重要な要素を見落としていたために、あまり効率の良いアルゴリズムになっていませんでした。
状況を整理し、必要な情報とそこから見えてくるデータの傾向などを踏まえた上で、より良いアルゴリズムを検討する、という姿勢を忘れないようにしたいなと思いました。