wordleのソルバを書こうかなあと思っていた時、Twitterでちょうど
「初手で情報量が一番大きい単語」
を調べている人のツイートが回ってきた。
情報量を考えるのか。なるほどな。
...しかし、Wordleでの単語の情報量ってどうやって計算するんだ?
と思って、同じようにWordleでの情報量を考えてた人がいるんじゃないかと思って、調べてみるといた。
https://xcloche.hateblo.jp/entry/2022/01/24/212558
xclocheさんという方が丁寧に解説してくれている。
この方は、wordleでの単語wの情報量-log(p(w))を、p(w)を
$$p(w) = \frac{(wを入力した時に得られるヒントを満たすような単語数)}{(総単語数)}$$
として計算していた。
なるほど、つまり価値が高い単語 = 入力して平均的に価値の高いヒントを得られる
、価値の高いヒント = より小さく単語を絞り込めるヒント
と考えてp(w)を定義すれば、
価値が高くなるほどp(w)が低くなり、情報量として扱えるようになるのか。
さらにありうる答え全てについて情報量を計算して、平均情報量を求めれば、その時点で最適な手の判断がつくと。
とても面白いので、初手だけではなくソルバを書いてみた。
ソルバとしてやったことは、上記の単語ごとの平均情報量の計算を毎回行う。
ただし、初手以外は、それまで得られたヒントを活用して、辞書を絞った状態で行う。
そのため、「全単語を考慮して効率よくヒントを集める」ということができない。
全単語を考慮すると計算量がかなーり多くなってしまう。
単語ごとの処理は独立だから処理を分散させることもできるが、もっと賢い方法で解決できる気もして...