はじめに
みなさん。 Wordle やっていますでしょうか。
知らない人のために一応説明しておくと、Wordleとは
Guess the WORDLE in six tries.
Each guess must be a valid five-letter word. Hit the enter button to submit.
After each guess, the color of the tiles will change to show how close your guess was to the word.
というゲームです。（公式引用）
要は、単語当てゲームで、いかに効率的にお題を特定するかが肝となっています。
とりあえず一度やってみればルールは理解できると思うので、やってみましょう。
そして先日、こんな動画を知り合いから教わり見てみたところ、
脳内のリーゼント男がこう言うのです。
「俺、バカだから英語もエントロピーもよくわかんねぇけどよ、
辞書さえあればそんなことしなくてももっと単純に解けるんじゃねぇの？」
ならばと、誰でもわかるような簡単なアルゴリズムで解けるか、挑戦してみたところ
大体の問題を４回答程度で正解できそうなものが出来上がったので、投稿してみることにしました。
基本方針
まず、プログラムに対するI/Oですが、今回はお題の単語（以後解と呼ぶ）の探索が目標なので、
ソルバーが出力した文字列を見てWordleに人間が入力して、そのフィードバックを標準入力するという
超アナログな方法で妥協します。
ChromeDriverとか使ってブラウザ操作までやれなくもなさそうですが、難易度高いので今回はやりません。
そして、解の探索は以下のような基本方針を立てました。
- 解となりえる単語（以後候補と呼ぶ）リストから、文字の出現回数をカウント（1単語に2回以上同じ文字が出るパターンでは、1回でカウントする）
- 既に解に含まれることが分かっている文字のスコアは０として、それ以外の文字のカウントを、文字のスコアとする
- 単語ごとに、文字ごとのスコアを合計して、単語のスコアを計算する
- 最もスコアの高い単語をWordleへ入力
- その回答のフィードバックから、候補を絞り、1からまた繰り返す
ここで、文字順も気にした方が良いとか、共起を考えた方がよいとか、細かいツッコミはいくらでもあるのですが、
多分そんなことしなくても人間よりかなり安定したパフォーマンスを出せるような予感がしたので、気にしません。
しかし、流石にこれだけだと問題があります。それは、どこで探索を終えて、いつから解を当てにいくのか という問題です。
例えば、候補が porin, ronin, zoril, robin の4単語に絞れたとして、
ここから、文字の出現頻度を計算しても、あまり意味はなさそうですよね。
回答権は4回残っているので、ローラーしてもいいのですが、流石にそれでは芸がないし、
解が一意に決まる回答を、ダイレクトに探すのが良さそうです。
この場合、例えば p,b,zの3文字が含まれる単語があれば、4つのうちから一つに特定できるだろうということは想像がつきます。
これを一般化していきます。
候補から解を一意に決めるアルゴリズム
まず、解が一意に決まる回答とは、それぞれ候補を解だと仮定した時のフィードバックを逆算し、そのフィードバックが全ての候補で異なる回答です。つまり、全ての単語と全ての候補の組み合わせについて、これを確認して、当てはまるようなものがあるかを探せば良い ということになります。
また、Wordleのフィードバックは、緑・黄・白(灰？) の3色*5箇所なので3^5=243パターンあります。
つまり理論上、243通り以下に候補が絞れた場合は、
そこから一度の回答で解を一意に決めるられる可能性があるといえます。
よって、この243候補を閾値として、
・ 候補数が閾値以下なら、解を一意に特定できる回答を探索する
・ 閾値より候補数が大、または閾値以下でも解を一意に特定できる回答がなければ、従来の単語スコアリングによる探索を再度行う。
という条件分岐処理を行うことにしました。
閾値なんてなくても極論問題はないのですが、
それをすると最初の段階で単純に辞書の単語数の2乗の計算が必要になってしまい、処理が重そうなので閾値を設定しました。
また、現実的に考えて、仮に候補が243単語あったとして、全ての単語に対して別のFBがもらえるかというと、
おそらく不可能です。が、少しオーバーな分には、探索効率が落ちることはないので、問題はないでしょう。
これでどのタイミングから答えを当てに行くのかという問題もクリアできました。
実装
ここから実装です。
まずは、先程の動画で、Wordleのサイトの main.<version>.js ファイルから、回答できる単語のリストが取得できるということは分かったので、
JSファイルの該当部分を取得してきました。 各々Vimなりなんなりで整形しましょう。
先程の動画で単語数が1.2万くらいだったので、配列の要素数がそれくらいあれば問題ないです
word_list = [
"cigar"
,"rebut"
,"sissy"
,"humph"
,"awake"
,"blush"
,"focal"
,"evade"
# 省略
]
辞書の取得と、アルゴリズムさえ決まってしまえばあとは書くだけです。
そして今回は、まさかのライブラリインポートが不要です。
これなら億泰でも安心して実装できますね。
import wordlist
def make_letter_appearance_count_dict(word_set: set):
# 辞書のキー配列を作成
letters = ["a", "b", "c", "d", "e", "f", "g"
, "h", "i", "j", "k", "l", "m", "n"
, "o", "p", "q", "r", "s", "t", "u"
, "v", "w", "x", "y", "z"]
# 辞書定義して、キーを入れ初期値０を設定
letter_appearance_count_dict = dict()
for i in letters:
letter_appearance_count_dict[i] = 0
# 単語リストを上から順に舐めて、文字の出現回数をインクリメントしていく
for word in word_set:
for letter in set(word):
letter_appearance_count_dict[letter] += 1
return letter_appearance_count_dict
def make_word_score_dict(letter_appearance_count_dict: dict, word_set: set, past_inputs:set):
word_score_dict = dict()
for word in word_set:
score = 0
# 今回は文字の位置は気にしないので、集合として扱う。 これによって重複も消せる
for letter in set(word):
if not letter in past_inputs:
score += letter_appearance_count_dict[letter]
word_score_dict[word] = score
return word_score_dict
def get_new_word_set(fb:str, input_word:str, word_set:set):
fb_list = list(fb) # 配列に変換
new_word_set = set()
for word in word_set:
is_excluded = False
# 緑：同位置に同文字がなければ除外
for i in [i for i, x in enumerate(fb_list) if x == 'g']:
if word[i] != input_word[i]:
is_excluded = True
break
if is_excluded:
continue
# 黄：単語に含まれていなければ除外
for i in [i for i, x in enumerate(fb_list) if x == 'y']:
if not input_word[i] in word:
is_excluded = True
break
if is_excluded:
continue
# 黄：同じ位置だったら除外
for i in [i for i, x in enumerate(fb_list) if x == 'y']:
if word[i] == input_word[i]:
is_excluded = True
break
if is_excluded:
continue
# 白：単語に含まれていれば除外
for i in [i for i, x in enumerate(fb_list) if x == 'w']:
if input_word[i] in word:
is_excluded = True
break
if is_excluded:
continue
# 全ての除外条件に当てはまらなければ、新しい候補リストに追加
new_word_set.add(word)
return new_word_set
def candidate_search(all_words: set, candidate_words: set):
# 閾値の条件を満たしていなければ処理せずreturn
if len(candidate_words) > 243:
return None, None
for word in all_words:
fb_set = set()
ans_patterns = dict()
for candidate_word in candidate_words:
fb = "wwwww" # 草を生やしているわけではなく、フィードバック全て白のパターンで初期化している
for i, letter in enumerate(word):
if letter in candidate_word:
fb_tmp = list(fb)
fb_tmp[i] = "y"
fb = "".join(fb_tmp)
for i, l in enumerate(zip(word, candidate_word)):
if l[0] == l[1]:
fb_tmp = list(fb)
fb_tmp[i] = "g"
fb = "".join(fb_tmp)
ans_patterns[fb] = candidate_word
fb_set.add(fb)
# 単語の数と、FBパターンのユニーク数が一致すれば、解が一意に決められる
if len(fb_set) == len(candidate_words):
return word, ans_patterns
# どの単語でも解が定まらないならNoneを返す
return None, None
def get_wordle_answer():
all_words = set(wordlist.word_list)
current_words = all_words
for i in range(6):
input_word, ans_patterns = candidate_search(all_words, current_words)
if input_word:
print(input_word)
fb = input()
return f'正解は: {ans_patterns[fb]}'
letter_freq_dict = make_letter_appearance_count_dict(current_words)
word_score_dict = make_word_score_dict(letter_freq_dict, current_words, set())
input_word = sorted(word_score_dict.items(), key=lambda x:x[1], reverse = True)[0][0]
print(input_word)
fb = input()
current_words = get_new_word_set(fb, input_word, current_words)
print(f"残り候補数: {len(current_words)}")
return "ごめんなさい 解けませんでした"
if __name__ == "__main__":
answer = get_wordle_answer()
print(answer)
これで、試しに今日(2022/02/14)の問題を解いてみました
ちなみに、最初の入力は、いかなる問題でも変わりませんが、
同率一位に aeros の他に soare もありました。
~/work/wordle $ python3 wordle.py
aeros
wwwww
残り候補数: 574
unity
wyywy
残り候補数: 3
talky
wwwwy
正解は: cynic
と、４回で無事答えに辿り着くことができました。グレートでスよこいつはぁ〜〜〜っ
最後に
とりあえず書き上がりましたが、もうちょっと綺麗になりそうなところも多そうな印象です。(get_new_word_setとか特に)
M1 MacbookAirで実行したところ、速度としては、やはりcandicate_searchメソッドで候補が１００超えるくらいあるとちょっと重いですが、それ以外は一瞬で処理が終わりました。
最初のmake_letter_appearance_count_dict とか、26 * 5 * 1.2万 くらいのループをしているはずなんですが、存外速くて驚きです。
ただ、バグを潰し切った気もしないので、書き方やアルゴリズム含め、気になるところがあればぜひコメントで教えてください。
以上です。 ありがとうございました。