とても有名な Wordle というゲームがあります。隠された 5 文字の英単語をヒントを手がかりに見つけるゲームなのですが、最大 6 回までしか入力が許されていないため、4 回目を超えたあたりから緊張感につつまれるよく出来たゲームです。

以前 YouTube で「Wordle ソルバーを30分弱で作ってみた【JavaScript実況プログラミング】」という動画を発表し、そこの冒頭でゲームの解説をしておりますので、ご存知のない方はご覧になって頂ければと思います。

さて、上記の動画で簡単なソルバーを作ったのですが、それは単純なアルゴリズムで生成されたソルバーであり、Hard モードを 6 回以内に確実に解くことは出来ません。そこで上記の録画の後、必ず 6 回以内で解けるソルバーを作成しました。この記事では、ハードモード対応の 6 回以内で確実に解けるソルバーをどのように作ったかについてご紹介します。

なおソルバーはこちらから遊べます。実際に触って楽しんでみてください。

前提

Wordle には、2 つの単語リストがあります。一つは「答えになりうる単語」で、2,315 単語あります。この 2,315 単語を確実に 6 回で確定させるのが今回のソルバーの目的です。もう一つは、「答えにはならないが、入力を受け付ける単語」で、10,657 単語あります。Wordle はランダムな文字の羅列は入力として受け付けず、このどちらかのリストに入っている合計 12,972 単語のみを入力として受け付けます。

https://gist.github.com/tkihira/271b4c3c59a4f587dbf1af181ccb2d05

その単語をこの gist に用意しました。1 行目が答えになりうる単語リストで、2 行目が答えにはならないが入力を受け付ける単語リストです。Wordle のソースコードに書かれていたもののコピーになります。当然ながらこれらの仕様は将来的に変更される可能性があります。

ソルバーの基本的な考え方

過去に色々な方々が色々なソルバーを作っていますが、基本的な考え方は大体共通しています。 2,315 単語の集合（以下「正解候補単語集合」と呼びます）に対して単語を入力することで、その集合を効率よく小さくしていき、最終的な答えを導き出す方法です。

例えば川口さんが書かれたソルバーがありますが、ベースはそのような考え方であり、そこからいかに最適化するかを考えておられます。最終的に相当精度のよいソルバーを開発されていましたが、最適解ではないことは自認していらっしゃるようです。余談ですが、正解候補単語集合の大きさが小さく、かつ文字の出現率に大きな偏りがあるので、個人的にはブルートフォース以外で最適解は出せないのではないかと思っております。

さて、上記のアルゴリズムはハードモードでも平均入力回数が 3.543 回という大変優れたものなのですが、残念ながら 7 回ならびに 8 回の入力単語が計 7 個発生してしまっています。今回のソルバーは、平均入力回数は度外視し、全ての単語を必ず 6 回以内に解くことを目的にします。

回数を抑える時のポイント

ハードモードではすでに正解が確定した文字を変更することが出来ませんが、これが 6 回以内の正解を狙う時に大変厄介な仕様となります。例えば上記の動画で実装した単純なソルバーでは最初の入力は「shake」を提案しておりますが、実はこれを最初に入力した瞬間に 6 回以内は不可能になります。もし最初の入力で結果が 🟩🟩🟩⬜🟩 となってしまうと、そこからは 4 文字目を変えて入力することしか出来ません。しかし「答えになりうる単語」リストの中に shade、shake、shale、shame、shape、share、shave、と 7 個の sha.e が存在するため、結果として、この状態になった瞬間に上記の 7 単語のどれかは必ず 7 回の入力が必要になってしまうわけです。実際の Wordle での敗北あるあるネタですね。

逆に考えると、回数を抑えるためには「一つの結果に解が集中しすぎないようにすれば良い」と考えることも出来ます。今回作成するソルバーは、この考え方に立ったものになっています。

アルゴリズム実装

上記の考え方を取り入れて、次のようなアルゴリズムを書いてみました。ある正解候補単語集合から一つの入力候補を選ぶにあたり、

• 現在の正解候補単語集合に対して、その集合の中から 1 つを選ぶ
• その単語を正解候補単語集合の中の全ての単語に対して入力し、その結果の数をカウントする
  • 例えば solve という入力に対し ⬜⬜⬜⬜⬜ は 342 通り、⬜⬜⬜⬜🟨 は 266 通り、⬜⬜⬜⬜🟩 は 135 通り、⬜⬜⬜🟨⬜ は 7 通り…
• そのカウントの中で、最も大きかったものを単語と合わせて記録しておく
  • 上記の場合は 342 通りのが一番大きいカウントだったので、solve と 342 とをペアで記録しておく
• 全ての単語で繰り返し、記録された最大カウントが最も小さい単語を選ぶ

簡単に言うと、入力に対して出力される結果に紐づく単語の数の最大値が最も少ない単語を選ぶ、という形でアルゴリズムを書きました。（今回は最大カウントを利用しましたが、分散の最大値を求めるやり方でもそこそこ良い結果が出ました。しかし後述の人為的な調整が上手くいきませんでした）

最初の入力の選定

アルゴリズムが決まったところで、単純にこのアルゴリズムを走らせると、最初の入力は「raise」になり、最終的な結果は以下の通りになりました。

1 guesses: 1
2 guesses: 131
3 guesses: 883
4 guesses: 975
5 guesses: 258
6 guesses: 52
7 guesses: 12
8 guesses: 3

15 個も 7 回以上の入力が必要な単語が出てしまっています。しかし、ここまでの試行錯誤で、最初の入力値はその後の結果に大きな影響を与えることがわかっていました。よって、入力の許されている全 12,972 単語を最初の入力として投入し（最初の入力のみをこちらが直接指定し）、その中で 6 回以下で終わる単語が出てこないか探索することにしました。

なお私の書いていたコードは、普通に実行すると 1 単語の探索に 2 分半ほどかかりました。単純計算で、全 12,972 単語の確認に 23 日かかる計算です。そこで手軽な高速化として、失敗した（7 回以上必要になった）単語を正解候補単語集合の先頭まで移動してから次の探索を行うようにしました。失敗しやすい単語はどの入力でも共通なので、前の方に集めることでとっとと失敗してもらう作戦です。他細かい最適化も入れて、結果として全単語の探索が 2 時間弱で終わるようになりました（並列化などで、さらなる最適化も可能でしょう）。こういう最適化は最悪時間計算量を減らさないので軽視されがちですが、実務的には大きな成果を挙げることもあるのでテクニックとしては有用です。

しかし、それだけ頑張っても、全ての単語を 6 回以内で解ける最初の入力値は存在しませんでした。以下が得られた中で最も良かった結果です。初期値は howls という単語で、shave という単語のみにおいて 7 回の試行が必要になってしまっていました。

2 guesses: 80
3 guesses: 710
4 guesses: 1155
5 guesses: 338
6 guesses: 31
7 guesses: 1

人為的なアルゴリズムの変更

ここで得られた初期値の単語「howls」に対して、shave が具体的にどのような入力によってどのように失敗してしまっているのかを出力して確認することにしました。

shave:
[howls] => 🟨⬜⬜⬜🟨
[share] => 🟩🟩🟩⬜🟩
[shade] => 🟩🟩🟩⬜🟩
[shame] => 🟩🟩🟩⬜🟩 
[shape] => 🟩🟩🟩⬜🟩
[shake] => 🟩🟩🟩⬜🟩
[shave] => 🟩🟩🟩🟩🟩

このように、2 回目の入力で 🟩🟩🟩⬜🟩 という穴に落ち込んでしまい、その時点で候補が 5 つ（shade, shame, shape, shake, shave）あったために失敗していることがわかります。

1 回目の入力で 🟨⬜⬜⬜🟨 という結果が出た時には、以下の 58 単語に絞られていました

ashen, brash, brush, bushy, chase, chasm, chest, crash, crush, fishy,
fresh, gnash, marsh, mushy, phase, pushy, quash, shack, shade, shady,
shaft, shake, shaky, shame, shank, shape, shard, share, shark, sharp,
shave, shear, sheen, sheep, sheer, sheet, sheik, shied, shift, shine,
shiny, shire, shirk, shirt, shrub, shrug, shuck, shunt, shush, sight,
sixth, smash, smith, stash, sushi, these, trash, usher

2 回目の入力において、この中の単語から r d m p k v のいずれかを二文字以上含む単語を指定すれば、とりあえず shave で失敗することはなくなるはずです。というわけで、

shard, marsh, sharp, shirk, shark

この 5 単語を「1 回目の入力で 🟨⬜⬜⬜🟨 という結果が出た時は、強制的にこの単語を入力する」という処理のもと差し込んでみました。結果として、全ての単語で 6 回以内で完結させられることがわかったので、最も結果の良い（平均試行回数が小さくなる）shark を採用することにしました。その結果はこちらになります。

2 guesses: 80
3 guesses: 706
4 guesses: 1160
5 guesses: 338
6 guesses: 31

全ての単語が 6 回以内に解答されていることが確認出来ました。人為的な条件分岐が入っているためにアルゴリズムとしては汚ないのが残念ではありますが、なにはともあれ 6 回以内で正解までたどり着けるソルバーを書き上げることが出来ました。

（なお上の方で「分散の最大値を求めるやり方でもそこそこ良い結果が出ました」と書きましたが、分散だとこの人為的に単語を抽出する作業が上手くいきませんでした。端的に言うと、人為的に解が見つかったのは運が良かったのだと思います）

ソルバーの紹介

今回のソルバーの出力結果はこのようになります。

https://gist.github.com/tkihira/2a68345de9865c390f666f98c3e601c9

Wordle の出力によってソートされており、美しい出力結果ですね。単語ごとの出力はこうなります

https://gist.github.com/tkihira/c5e6a829a03909cdb0ec2049b37f5933

記事の冒頭で紹介しましたが、実際に手で触れるソルバーを用意しております。

ソルバーのソースコードはこちらです。

https://github.com/tkihira/wordle-solver/blob/main/solver.js

記事中で触れていた、人為的な調整を入れているのはこの部分になります。

まとめ

結局うまくハマる解がたまたま見つかりました、という結論になってしまいましたが、それはそれとして解が存在することが確認出来てスッキリしました。つい先日に Wordle でまさかの一発正解を成し遂げたのですが（そしてそれが Wordle のソルバーを書くキッカケになったのですが）、その運の良さをそのまま引き継いで今回も良い結果を得ることが出来たなと思います。

なお、今回のソルバーは極めてギリギリの状況で成立しており、例えば初期入力の 2,315 個の単語の並びの順番が入れ替わると、最悪 6 回以内に全ての単語が完了しないこともあります。そういった点でも色々と運に左右された中での達成であったなと思います。もう少しここら辺を美しく解決出来ていたら、より価値が高まっていたと思います。

もしさらに改良していくならば、より美しいアルゴリズムで解を求めるか、もしくは平均解答回数を減らす方向に最適化していくのかな、と思います。現在は平均 3.799 回の試行となっていますが、これをもっと短くしていく方向です。個人的にはハードモードを確実にクリア出来ることを証明したところで満足してしまったのですが、興味のある方は是非挑戦してみてください。

別のアプローチの解もあり得ると思います。今回はトップダウンで探索しましたが、ボトムアップで下から単語を選んで行く解法も可能かもしれないですね。動的計画法などで計算量を大きく削減出来るかもしれません。もしくは、枝刈りをうまく実装できれば全探索も可能かもしれないです。ハードモードではない状態での最適解をひたすら求めるのも面白そうです。

Wordle のソルバーという題材は、アルゴリズムの実装の素振りには適したお題なのだろうと思います。入力値のデータセットも小さいですし、よければ皆さんも是非挑戦してみてください。