日記 2022/1/23 Wordleのいい感じの解法を調べる
(※なんちゃって技術系の面白くない話なので、ブラウザバック推奨)
Wordleをズルしないで理論的に解いてほしい、みたいな話があったので、調べて考えてみる。
以下調べたこと、考えたこと。その前に以下の注意事項は必ず読んでね。
※注意1
どの解法も、5文字の一般英単語全てを入力として考えておらず、Wordleで入力可能な英単語(12972単語らしい)に限定した話をしている。この12972単語を知る方法は、ソースコード経由と思われる。入力可能な英単語を知ることも許せない！って人は今回の記事は読まないことを推奨。(へらこ的にはゲームとしては入力できるものはオープンにするのが当然だ(何が入力できて何が入力できないかを考えるのはゲームの本質ではない)と思うので、特に問題ないかと考えている(どうせ入力できないものはクエリを投げる前にはじかれるし))
※注意2
手書きの図を入れているが、文字も絵も汚い...。
※注意3
Wordleに答えを入力することを「クエリを投げる」と言っている。
※注意4
日本語が不自由すぎて伝わらない部分あると思います、意味不明なところはコメントしてもらえたら修正します。
結論: 他の人の記事を読め
Automatic Wordle Solving. Taking out the fun of Wordle is fun by… | by Yotam Gafni | Jan, 2022 | Towards Data Science を読め。
下でも紹介するが、上記リンクの記事は今回の記事の内容を全て含んでいると思われる(この記事大体書いた後にヒットした...)ので、上の記事を読めばOK。私は悲しい。
以下、駄文です。
Wordleの解法に対するへらこの認識
へらこがWordleがどういうゲームと認識しているかを説明。
まずは手順。
0. 正解候補(入力できる単語)の集合を用意する。
1. 集合に対してクエリを投げる。
2. クエリに対する答え(例: 白白白白緑)によって、候補が絞られ、新しい候補の集合が次にクエリを投げる対象になる。
3. 1,2を5回(最初を含めたら6回)繰り返し、最終的な候補の集合の要素が1になっていれば勝ち。(もしかして1回多い？)
このとき、2で貰う答えがどのパターン(白白黄白緑や黄白白白白など)でも対応できるように、1で投げるクエリを考える必要がある。
そのために持つべきものは、「6ターン後、要素数が1である候補の集合の数を最大化する、全てのパターンに対して投げるべきクエリ」である。
これを図で表すと、下図のようになる。6ターン後の候補の集合が葉になるような木で表せる。遷移がクエリに対する答え、それぞれのノードはその答えを返すような候補(単語)の集合となっている。今後各解法に対して、下図をベースに図を付ける。
ここまでを理解してもらえているかな...不安(あまりにも説明の仕方が下手で論理的でない)。
愚直な完全な解法
完全な解法は愚直にやればできるが、あまりにも時間がかかり、現実的ではない。
一言で言えば、全てのパターンを計算して最適なパターンを見つける、というもの。
ゲーム中に出てくる可能性のある全ての集合(葉以外のノード)と全てのクエリに対して、上図のような遷移図を全て計算し、クエリを投げた回数が6回以内で中の要素数が1になっている葉が一番多くなるような6回のクエリの投げ方を探す。
これの計算量は、O(N^6)(N=12972)だと思われる。実際はクエリに使う単語の数が葉に行くにつれ減っていくはずなので、ちゃんと計算したらもっと少ないのかな...。計算量理論を勉強してないので知らない。誠にごめんなさい。
完全な解法を効率よくできる？
これができれば最高なのだが、うまく枝刈りする方法(クエリの投げ方に関してすべての組み合わせを見ずとも、どこかで最大の深さを計算し、探索を打ち切ることができる方法)の検討が付かない。この難しさは、絞り込みやすさ(=候補を絞り込み切るまでに必要なクエリの数)と集合の要素数(=残っている候補の数)の関係は必ずしも一致しないため、集合の中身まで見て判断する必要があり、その中身のパターンは多いかつ一般化が難しい、ということにありそう。一般化が難しい理由は何、までくると回答に困るが...。
実際調べても、完全な解法を効率よく行うようなアプローチは見当たらなかった。
現時点ではヒューリスティックに解くしかなさそう
上記のようなことを皆考えているのか、調べた結果、どれもヒューリスティック(理論的な保証がない、経験的な)方法で解いていた。ヒューリスティックな方法の中でも、恐らく全て欲張り法(各ターンにおける最適なクエリを選択、6ターン全体を考慮した選択は行わない)に分類されていると思う。
現時点では、ヒューリテスィックな方法で実際に全ての単語に対して6ターン以内で終わるものがあればそれを使う、というのが一番現実的なWordleの解法かと思う。
ググって調べて出てきた(ヒューリスティックで欲張り法な)解法
一応今日結構調べたり図書いて理解したりしてたので、それを共有する。
最終的な解法だけではなく、最初の単語には何がいいか、で終わってる物もあるので注意。
The Best Starting Word in WORDLE | bertrand fan
最初に投げる単語として最良なのは"SOARE"(若いタカ、という意味の古い単語らしい)である、という主張をした記事。この記事を参照している他記事も結構見た。
クエリとなった各単語が、他の全単語に対して、緑と黄色をどれだけ出すかを総計して、その数が多いものが最良の単語としている。(実際の評価関数は緑2点、黄色を1点としたポイントの総和)
以降で紹介する解法と比べると、恣意性が大きいように感じる。緑2点、黄色1点なんていう点数の付け方なんて特にそう。方針自体も、この評価関数が最大化されるとどう嬉しいのか、があまり直感的ではない気がする(点数が高いことと、候補の絞りこみ精度の高さに相関はありそうだが、具体的にどう相関してるのかの説明が難しい)。
下図がこの方法でやってることのへらこ的直観的理解。
Wordle: What's the Best Starting Word?
最初に投げる単語として最良なのは"SOARE"である+自分の解法を使えば6ターン以内に解けそうだ、という主張をした記事。Mattさんが書いたので、Mattの手法と呼ぶ。
ただしこちらの評価関数は上のものとは違い”what word eliminated the highest amount of possible solutions.”(どの単語が、考えられる答えの最大の量を削除したか)を見ているらしい。これだけ読んでも意味が分からないが、記事の図を見てみるとなんとなくわかる。
クエリとする各単語に対して、答えがXだとしたら、候補をいくつに絞ることができるのか(答えXと同じ集合に分類される単語はいくつあるのか)、というのを、Xを全単語で入れ替えて計算し、各絞られた候補の数で平均(総和と同等)を取っている。その絞られた数が少ないほど(=削除した数が多いほど)最初のクエリとして優秀な単語となる、という推測だ。
これは平均を取っているので、最悪がどうなっているか、までは見ていない(これを見ようとしてるのが、後で言うmin-max法)。
ただし、実際にこの戦略を繰り返し使って、ランダム抽出してきた単語50回に対してゲームを行ったところ、平均4.42ターンで、50/50ゲームに勝った、とMattさんは述べているので、筋はいいみたいだ。実際にそこまで確かめてるの偉すぎる。
下図がこの方法でやってることのへらこ的直観的理解。
【ネタバレ(？)注意】WORDLE jaの最適解チャートを組んでみた｜ちゃそ｜note
日本語版Wordleに対する最適解チャート。min-max法なるものを使っている、と言っている。ちゃそさんが書いてるが、min-maxの手法と呼ぶ。
ある単語を打って、最も候補が絞れなかった場合の候補数を考え、それが一番小さくなるような単語を求める
ということらしい。「最悪この後どのくらい探索しなくてはいけない(クエリを投げなくてはいけない)か」は、「一番要素数の多い集合(一番絞れていない候補数)」に依存する、というのが恐らく根本の考え。
日本語版Wordleに対しての実験では、正解or入力できる単語数が2766という設定で、約85%の確率で5回以内、約97.5%の確率で6回以内に正答、最大で9回かかるらしい。きちんと調べてるの偉すぎる。
下図がこの方法でやってることのへらこ的直観的理解。
Wordle(ワードル)必勝法 – 秋元@サイボウズラボ・プログラマー・ブログ
Best Wordle guessing strategy | Hacker News
リンクのリンクのリンクになるが、掲示板(一番下のリンク)で初手の2手は" AEROS/UNLIT "が良い！と言っている。詳細は謎。
サイボウズラボの記事にはWordleで入力できる英単語のリストが載っている。
Automatic Wordle Solving. Taking out the fun of Wordle is fun by… | by Yotam Gafni | Jan, 2022 | Towards Data Science
これを読めばこの記事読む必要なし。
min-maxの手法(上で記述済み)と、平均値最小化という手法を使っている。平均値最小化という方法も、結局Mattさんと評価関数は同じ。
著者のYotamさんは、最悪のケースを考えたいからmin-maxの方がすきだ、平均値最小化はいまいちだ、と言っている。
実際にWordleの全ての単語に対して描けたところ、min-maxは最悪で5手、平均値最小化は最悪で6手で解けたらしい。つまりどちらでも条件は満たせて、絶対勝てるらしい。
Githubでコードも公開しているので、これを見れば万事解決。この記事いらんやん。
へらこ的結論
最後に挙げた記事の通り、min-maxでもMattさんの手法(平均値最小化)でも、どちらでも現在のWordleの単語リストではうまくいくらしい。
一般にWordleに挑むのにはどちらの方が良いのか、というのは解法だけ見ても分からず、データによるのでは、と思う。というのも、どちらも「なるべく多くの単語に対して、6ターン以内に当てる」ということを直接の目的としていないから。Yotamさんは最悪のケースを見たい、と言っていたが、それは全ての単語が6ターン以内に必ず当てられるような遷移が作れることを前提の記述だと思われる。あとはmin-maxが最良になる、という考えの根本が正しいかも微妙なところ(要素数だけじゃなくて結局中身も見ないとちゃんとは分からないよね)、というのも勿論ある。
下図がへらこ的直観的理解。Mattさんの手法が左、min-maxの方法が右。min-maxは最悪のケースを抑えてるが、「6ターン以内にどれだけ当てられるか」を見ていない。Mattの手法も同様。なので、データによりそう。
実際はMattさんの手法(平均最小化)もかなりバランス重視の評価関数になってると思うので、上みたいな差は生まれないと思うが、誇張すると差が出るよね、という感じ。
あと上記の解法の計算量は全てO(N^2)(N=12972)だと思われる(6回、クエリとする単語(N)×正解候補の単語(N)に対して、どこに色が付くかを見るので)。間違ってたらすまそ。
終わりに
余裕があれば自分でコード書いてみてテストしてみてもいいかな、と思ったが、そこまでのモチベーションと体力はなかったので、ここでおしまい。
自分でコード書くまでもなく、Yotamさんがコード上げてくれていました。そっち見てください。
もっといい解法考えたよ！/見つけたよ！というのがあったら、教えてください。
お前の理解はここが間違ってるよバカ、というのはこっそり優しく教えてください。
しかし誰向けの記事なんだこれ...(理論的な考察は明らかに足りてないし、軽い気持ちで見に来てくれる人向けでもない...)。
自己満のブログだしいいか。
滅茶苦茶読みにくかったと思いますが、ここまで読んでくださりありがとうございました。
