1.Wordle
皆さんは、Wordleって知っていますでしょうか？
5文字の英単語をヒントをもとに推測し、6手までに当てると言うシンプルな内容です。
私も挑戦してみました！
Wordle 242 4/6
— あめふり てる* (@Amefuri_Tell) February 15, 2022
🟨⬜⬜⬜⬜
🟩🟨⬜⬜⬜
⬜🟨⬜⬜⬜
🟩🟩🟩🟩🟩
面白いですね。ただ、これは最初の単語選びが大切そうです。
そこで今回は、初手3単語までを最適化しようをします。3単語で15文字。15/26なら結構わかりそうという感覚でやっていきます。
2. 最適化手法の話
では、最適化手法を何にしようかと考えた結果、私の大好きなアルゴリズムである、遺伝的アルゴリズムを使うことにしました。理由としては、
- 書くのが簡単
- 組み合わせ問題が得意なアルゴリズム
- すでに書いたことがある
の3点です。焼きなまし法や貪欲法、DPなんかもできそうですがこれでやっていこうかと思います。
1. 遺伝的アルゴリズム
遺伝的アルゴリズムとは、生物の進化を模したアルゴリズムと言われることが多いです。
強い個体同士を掛け合わせて、より強くするというとても単純なものです。
強い * 強い = 最強
みたいなやつで、これだけ抑えておけばだいたいわかります。
そして、最強と最強を掛け合わせて、スーパー最強にしていくというのがこのアルゴリズムです。
ちゃんとした話
遺伝的アルゴリズム(Genetic Algorithm:GA)は、以下の5ステップから成ります。
- ランダムな染色体を持った個体を生み出す
- 各個体の適応度を算出する
- 適応度をもとに個体同士を掛け合わせ、新たな染色体を持った個体を作る(交叉)
- 突然変異を起こす
- 2に戻る
染色体とは、問題に対する解を表すものです。この染色体は解く問題に対してとても柔軟に変化します。
今回の単語の組み合わせ最適化で使うもので例として上げると、
単語辞書の番号の集合です。
たとえば、{1, 10, 1000}のような染色体があったときこれらは、{"abase", "abbey", "house"}のような単語の組み合わせを示します。
ちなみに、集合の要素一つ一つを遺伝子と呼びます。
適応度とは、この問題に対してどれくらい良い答えなのかということを数値化したものです。
今回の場合は、例えば、この3単語でアルファベットの出現率の合計だったり、絞れる単語数といった数です。これらは、どれが一番良い解なのかを示してくれます。
ちなみに、これを出す関数のことを適応度関数と呼ぶそうです。
突然変異とは、両親の染色体になかったような遺伝子に変化させるものです。
局所解に陥ったり、収束しなくなったりすることに極めて大きく作用します。
突然変異を起こすと、今まで最適だと思っていた局所最適解と呼ばれる、もっといい最適解があるのにその値に落ち着いてしまうという事故を防ぐことができます。
しかし、突然変異が起きすぎると解が一つに定まらなくなってしまうという欠点が存在します。
あとは、エリート保存戦略や交叉するときの親の選び方、交叉方法など、手法は様々ありますがここでは割愛します。
3. いよいよ最適化
では、最適化していきます。
まずは、辞書を用意します。ここでは以下の方の辞書を使わせていただきました。
それでは、作っていきましょう。
ちなみに、コードはGitHubに上げてあるので見たい人は見てね。
詳しい話
4.結果
4つ同時に学習した結果、すべてが
aeros(arose)
clint
dumpy
の3単語に落ち着きました。
これは…間違いないのでは！？
最後に
これ以外にもいい感じの三手があるはずなので、みんなも最適化してみてね！私もやったんだからさ。