🧮

Wordleのソルバーを作ってみた

2022/01/23に公開約2,700字

最近TwitterでWordleをいうパズルゲームを見かけます。

https://www.powerlanguage.co.uk/wordle/

簡単なソルバーを作れそうに思ったので作ってみました

https://github.com/zat-dev/wordle-solver

Wordleのルール

隠された5文字の英単語を当てるゲームです。
何か単語を入力すると、それぞれの文字に対して

  • 答えに含まれていない
  • 含まれているが位置が違う
  • 位置と文字が正しい
    という結果が返ってきます。
    6回の入力以内で答えを当てればクリアです。
    1日一題出題されています

ソルバーを作る

入力英単語に対する結果から、答えの候補を絞っていくことを考えます。
最終的に1つに絞ることができれば、それが答えです

シミュレーションにかかる時間を見積もる

まずは6ターンのすべての入力と結果を事前にシミュレーションし、
最も良い入力パターンを事前計算することを考えます

6ターンのシミュレーション内容

起こりえる結果すべてをシミュレーションすると次のようになります

計算量から時間見積もり

  • すべての5文字英単語が12000通り
  • すべての5文字英単語の各単語に対して
    • 単語を入力した際に考えられるすべての結果が 3^5 = 243通り
    • 現在の答えの候補を1つずつ見て、入力と結果に矛盾しないものを残す
      * 最初は全5文字英単語が候補なので12000通り

1ターン目だけでもシミュレーションで 12000 * 243 * 12000 の計算量がかかります。
6ターン目までシミュレーションするとこれの6乗で10の63乗ほどとなります。
10の7乗が1秒程なので、まず間に合いません。

(2ターン目以降は答えの候補が減っていくはずですが、大勢に影響しませんので試算では考慮しません)

しかし、計算量の見積もりから、1ターンだけのシミュレーションであれば、最大でも約1時間で答えが出せそうです。

1ターンごとに一番答えの候補を減らせる見込みのある入力を探索する


次の手順で1ターンだけ見た最適な入力を探索することにします。
5文字英単語の各単語に対して、次を全探索します

  • 入力した際に起きえるすべての結果
  • 結果から絞られた答えの候補数
    全探索で得られる各候補数の平均が最も小さいものが、一番候補を減らせる見込みが高いものと言えそうです。

なので、ソルバーの挙動としては次を繰り返すことにします

  • そのターンで最も答えの候補を減らせる見込みのある入力を提示
  • ユーザーはその入力をWordleに入力
  • ユーザーはWordleに表示された結果をソルバーに入力
  • ソルバーは結果から答えの候補を絞り込み
  • 残りの候補を最も絞る見込みのある入力を探索

並列化で速くする

  • 賢い方法ならもっと速くできそうですが、思考停止でできるお手軽な高速化として並列化をします。

  • 毎ターンどの入力が最も絞れるかを全5文字英単語から探索しますが、この5文字英単語の探索を分割して同時実行します。

  • 10CPUなら10倍の高速化です

  • pythonだとmultiprocessingPoolを使うと簡単に並列化できます

PARARELL = 10
def pararell_search(ans_candidates):
    p = Pool(PARARELL)
    search_size = len(all_5letter_words)//(PARARELL - 1)
    # 探索対象の単語リストを分割
    search_domains = [
        all_5letter_words[i*search_size:(i+1)*search_size]
        for i in range(PARARELL)
    ]
    # multiprocessingのPoolは1引数しか与えられないので他の引数をタプルでまとめる
    args = list(map(lambda x: (ans_candidates, x), search_domains))
    # argsの各要素にsearch_best_inputを適用することを並列でやってくれる
    results = p.map(search_best_input, args)
    return min(results, key=lambda x: x[0])[1]

実際にやってみた

https://twitter.com/zatjapan/status/1484913357555912704

感想

  • たぶんデータ構造とアルゴリズムをちゃんとすればずっと速くできそう
    • 特に絞り込みの部分
  • 他の人のソルバーを見ていると、文字の選択は情報量を使うのがより良いのかも
  • 平均を使っているところは、最初は全入力英単語について「全結果から絞られる答え候補数の最大」を計算し、それが最小のものとしてました
    • 最悪ケースが起こる想定ですべての入力単語を調べ、最も被害の少なそうな入力単語を選ぶ感じです
    • どっちがいいかは分かっていませんが、ターンの途中で状況に応じて切り替えるとかはありそう

追記

絞られる答え候補数の平均だと6ターンで解けないケースを見つけたので、
感想に記述した「最も絞れなかったケースでの候補数が最小のものを選ぶ」に変更しました

追記2

力技で決定木(記事中の6ターンすべてをシミュレーションに相当)を構築した人がいました。
どんな答えも6ターン以内に正解できるそうです。

https://www.poirrier.ca/notes/wordle/

*「最も絞れなかったケースでの候補数が最小のものを選ぶ」はmin-max法と呼ばれるみたいです

  • Wordleは実はマイナーな単語は除いているようで、2000語ほどしか入力できないみたいです

Discussion

ログインするとコメントできます