Wordleのソルバーを作ってみた
最近TwitterでWordleをいうパズルゲームを見かけます。
簡単なソルバーを作れそうに思ったので作ってみました
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だと
multiprocessingのPoolを使うと簡単に並列化できます
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]
実際にやってみた
感想
- たぶんデータ構造とアルゴリズムをちゃんとすればずっと速くできそう
- 特に絞り込みの部分
- 他の人のソルバーを見ていると、文字の選択は情報量を使うのがより良いのかも
- 平均を使っているところは、最初は全入力英単語について「全結果から絞られる答え候補数の最大」を計算し、それが最小のものとしてました
- 最悪ケースが起こる想定ですべての入力単語を調べ、最も被害の少なそうな入力単語を選ぶ感じです
- どっちがいいかは分かっていませんが、ターンの途中で状況に応じて切り替えるとかはありそう
追記
絞られる答え候補数の平均だと6ターンで解けないケースを見つけたので、
感想に記述した「最も絞れなかったケースでの候補数が最小のものを選ぶ」に変更しました
追記2
力技で決定木(記事中の6ターンすべてをシミュレーションに相当)を構築した人がいました。
どんな答えも6ターン以内に正解できるそうです。
*「最も絞れなかったケースでの候補数が最小のものを選ぶ」はmin-max法と呼ばれるみたいです
- Wordleは実はマイナーな単語は除いているようで、2000語ほどしか入力できないみたいです
Discussion