# ポケモンWordleを攻略しよう (前編) ## はじめに 以前公開したProject\_Verbumについて, 関連ドキュメントを書いていなかったので書くことにしました. そもそも[**Project\_Verbum**](https://github.com/niart120/Project_Verbum)ってなんだよという人向けに説明すると, ポケモンwordleを~~破壊~~攻略するために作ったプログラムです. ![](https://i.imgur.com/2MO4w9q.png) 例えば, こんな感じでランダムなお題とその解法を自動生成してくれます. このプログラムに用いているアルゴリズムの詳細について説明をしていこうと思います. ただ, アルゴリズムの説明にあたって, エントロピーという一般的には聞きなれない概念が出てくるので, まずは前編にてエントロピーの説明をして, しかる後にアルゴリズムの詳細を説明したいと思います. なるべく平易な表現になるように心がけますが, 数学的な表現は多少難解になるかもしれません. ご容赦ください. あるいは有識者の方々に関しましては, 数学的な議論に誤りなどがあれば遠慮なく指摘していただけると幸いです. ## 準備:事象と事象系 いきなりですが, ジョーカーを除く52枚からなるトランプから, シャッフルしたうえでカードを1枚引くことを考えてみます. トランプのカード1枚を引いたときに, どのようなカードを引くかという観点から, 生起する事柄を分類する方法はいくつもあります. 例えば, カードのスートに着目するのであれば, {スペード, クラブ, ダイヤ, ♡}の4種類の事柄に分割されますし, 数字に着目するのであれば, {$1, 2, \dots ,13$}の13種類の事柄に分割することが出来ます. あるいはもっと極端な例でいえば, {♡の7, それ以外}といったように分割することも可能です. 上記のように, ある観点に基づいた行為によって生じる事柄, 即ち **事象(event)** を全て列挙し, それらに加えてそれぞれの生じる確率を並べたものを **(完全)事象系(event system)** と呼びます. 具体的な例を一つあげてみます. 引いたカードのスートを事象として, $x_1=$"♠", $x_2=$"♣", $x_3=$"♢", $x_4=$"♡"とすれば, それぞれの事象が生じる確率$p_1, p_2, p_3, p_4$は全て$\frac{1}{4}$となりますから, カードを1枚引いた時のスートに関しての事象系$X$は次のように書き表すことが出来ます. \begin{align} X &= \begin{pmatrix} x_1& x_2& x_3& x_4\\ p_1& p_2& p_3& p_4 \end{pmatrix} \\ &= \begin{pmatrix} \text{"♠"}& \text{"♣"}& \text{"♢"}& \text{"♡"}\\ \frac{1}{4}& \frac{1}{4}& \frac{1}{4}& \frac{1}{4} \end{pmatrix} \end{align} さて, 何故このような話をしたかというと, エントロピーという概念を定義するのに事象と事象系という言葉が使われているためです. エントロピーというと聞き馴染みがない言葉のように思えるかもしれませんが, 情報量という言葉に言い換えると皆さんにも馴染みがあるのではないでしょうか? 次節以降で詳しく述べていきます. ## 情報量とは? "情報量"という単語自体は普遍的なものであり, 皆さんも使うことは少なからずあると思います. しかしながら, その言葉の具体的な意味を具体的に考えたことがある人はあまり居ないかもしれません. そもそも何をもって情報の"量"を比較しているのでしょうか? 情報の"量"というのは, 物事の珍しさの尺度と捉えることが出来ます. 先ほどのトランプの例を交えて説明しましょう. カードを1枚引いた時に, そのカードについて, 次A, B, C, Dのうちいずれか1つが分かったとしましょう. * A : (数字が)7 * B : (数字が)4の倍数 * C : (スートが)♡ * D : (色が)黒 それぞれを一種の"情報"として捉えたとき, 直観的にはAが最も引いたカードに関する情報を得られていると感じるのではないでしょうか. 何故そのように判断できるのかは, その事象の起こりやすさに起因しています. 実際に数えてみましょう. * A : (数字が)7 -> $4$通り -> $\frac{4}{52}$ * B : (数字が)4の倍数 -> $12$通り -> $\frac{12}{52}$ * C : (スートが)♡ -> $13$通り -> $\frac{13}{52}$ * D : (色が)赤 -> $26$通り -> $\frac{26}{52}$ このようにしてそれぞれの事象における確率を比較してみると, 1番目の事象が最も起こりにくい, 即ち珍しい事象であることが分かりますね. しょっちゅう起こる事象よりも, 珍しい事象の方がより多くの(価値のある)情報を持っている, と考えるのは不自然ではないと言えます. もう少し踏み込んでみましょう. 例えば, Aの情報とCの情報の両方が分かったとします. このとき得られる情報は, * E:♡の7 となりますね. Aの情報とCの情報はそれぞれ独立しています. 独立というのはつまり, 数字が7であるという事象と, のスートが♡であるという事象は互いに影響し合わないという意味です. このとき, Aから得られる情報の量と, Cから得られる情報の量を足したものが, Eから得られる情報の量と等しくなるべき, というのはAとCが分かればEが導かれるという状況からしても, 妥当な考えといえるのではないでしょうか. ここまでの話を踏まえると, 情報量という概念はつぎの要件を満たしていると良さそうに思えます. * 頻繁に生じる(確率の高い)事象よりも, 珍しい(確率の低い)事象から得られる情報量の方が大きい(単調減少性) * 独立な事象から得られる情報量の和は, その事象が同時に起きたときに得られる情報量と等しい(加法性) * 事象の生じる確率に応じて情報量が連続的に変化する(連続性) なぜか最後の連続性だけ唐突に出てきてますね. この性質は, 数学的な議論(最大/最小, 微分可能性など)を行うのに便利という理由で含まれています. ~~ふわっとしてますね.~~ ともあれ, これらを踏まえると, 次のような定義がおぼろげながら浮かんできます(~~小泉進次郎構文~~). Def.1 自己情報量(infomation content) : ある事象$a$が確率$P(a)=p$($0\le p \le 1$)で起こるとき, **自己情報量**$I(a)$を \begin{align} I(a) &= -\lg(P(a))\\ &= -\lg p \text{ [bit]} \end{align} : と定義する. 但し, $P(a)=0$のとき$I(a)=0$とする. ここで, $\lg P(a)$という見慣れない表記が出てきたように思うかもしれませんが, これは$\log_2 P(a)$の略記となっています. あまり高校数学を覚えていないという方に説明すると, $\log$というのは対数関数と呼ばれる関数のことです. 先ほどの$\log_2 p$は, "$2$を$x$乗すると$p$になる数$x$"を表します. 練習も兼ねて, 少し具体的な計算をしてみましょう. ここからは高校数学の知識を使った計算がいくつか出てくるので, もし良く分からなければ読み飛ばしていただいてかまいません. 取り合えず$\lg$とかいうのを使うと上手くいくんだな, ぐらいの認識で大丈夫です. 先ほどの"♡の7"という事象の自己情報量を計算すると, \begin{align} I(\text{"♡の7"}) &= -\lg(1/52) = \lg(52)\\ &= \lg(2\times 2\times 13)\\ &= 2\lg(2) + \lg(13)\\ &\approx 5.700 \end{align} となります. つまり, "♡の7"という情報は, およそ$5.7$bitの情報量であると言えますね. ほかの事象についても計算してみましょう. "(引いたカードの数字が)7"という事象と, "(引いたカードのスートが)♡"という事象の自己情報量は, \begin{align} I(\text{"7"}) &= -\lg(1/13) = \lg(13)\\ &\approx 3.700 \end{align} \begin{align} I(\text{"♡"}) &= -\lg(1/4) = \lg(4) = 2\lg(2)\\ &= 2 \end{align} となりますね. それぞれおよそ$3.7$ bit, $2$ bitの情報量であると言えます. つまり, 実際にカードを引いたときに得られた情報が, "(引いたカードの数字が)7"または"(引いたカードのスートが)♡"であった場合, 前者の方がより多くの情報を得ているということができます. 実際に, 計算結果が先ほど述べた "頻繁に生じる(確率の高い)事象よりも, 珍しい(確率の低い)事象から得られる情報量の方が大きい", "独立な事象から得られる情報量の和は, その事象が同時に起きたときに得られる情報量と等しい" といった性質を満たしていることを確認してみてください. なぜこのように上手くいくのか, 詳しい話はこの場では割愛しますが, 興味がある方は以下のサイトを参考にされると良いかと思います. [情報量の意味と対数関数を使う理由 -高校数学の美しい物語](https://manabitimes.jp/math/1002) さて, 上記で述べた自己情報量というのは, ある特定の事象について得られる情報量がどの程度であるかを表しています. それに対して, ある事象系で生じる事象から得られる平均の情報量というものも定義することができます. Def.2 平均情報量(shannon entropy) : 事象$x_i$が確率$p_i$で生じるような, $n$個の事象$\boldsymbol{x}=(x_1, \dots, x_n), \boldsymbol{p}=(p_1, \dots, p_n)$からなる事象系$X=(\boldsymbol{x},\boldsymbol{p})$の**平均情報量**$H(X)$を \begin{align} H(X) &= -\sum_{x_i\in\boldsymbol{x}}P(x_i)\lg P(x_i)\\ &= -\sum_{p_i\in\boldsymbol{p}}p_i\lg p_i \text{ [bit]} \end{align} と定義する. 但し, $P(x_i)=0$のとき, $P(x_i)\lg_2 P(x_i)=0$とする. (余談ですが, 平均情報量を表記している文字はエイチではなくエータと読むこともあります. ~~ややこしいですね.~~) つまりこれは, それぞれの事象から得られる自己情報量を, その事象が生じる確率で重みづけした和となっており, 自己情報量についての期待値となっているわけですね. といっても良く分からないと思うので, 具体的に計算してみましょう. 又してもトランプの例を用います. "カードを1枚引いて数字を見る"という行為の下で, 次のように事象系$X=(\boldsymbol{x},\boldsymbol{p})$を構成してみます. \begin{align} X &= \begin{pmatrix} x_1& x_2& x_3\\ p_1& p_2& p_3 \end{pmatrix}\\ &= \begin{pmatrix} \text{"3の倍数"}& \text{"5の倍数"}& \text{"その他の数"}\\ \frac{4}{13}& \frac{2}{13}& \frac{7}{13} \end{pmatrix} \end{align} つまり, 引いたカードの数について, "'3の倍数', '5の倍数', 'それ以外'のどれかが分かるような状況"という事象系を構成しています. この事象系$X$の平均情報量は, 次のように計算することができます. (計算過程については, $\log$の諸公式をご存じであれば一度自分で手を動かしてみるといいかもしれません.) \begin{align} H(X) &= -\sum_{x_i\in\boldsymbol{x}}P(x_i)\lg P(x_i)\\ &= -\left(\frac{4}{13}\lg\frac{4}{13} + \frac{2}{13}\lg\frac{2}{13} + \frac{7}{13}\lg\frac{7}{13}\right)\\ &= -\left(\frac{4}{13}\lg4 + \frac{2}{13}\lg2 +\frac{7}{13}\lg7 -\lg 13\right)\\ &= -\frac{10}{13}\lg2 - \frac{7}{13}\lg7 + \lg13\\ &\approx 1.420 \end{align} また, 平均エントロピーの値は, 構成される事象系によって変化します. 前述した通り, この値が大きければ大きいほど, その事象系において得られる情報量が大きくなることが期待できます. さて, 自己情報量と平均情報量とで2つの情報量が出てきましたが, これらはそれぞれ自己エントロピー, 平均エントロピーとも呼ばれています. 以降はそれぞれの情報量を自己エントロピー/平均エントロピーと呼称することにします. 文献によっては, 文脈上どちらであるかが明らかなときは単にエントロピーと呼ばれることも多いため, 場合によっては混乱するかもしれません. このドキュメントでは, なるべく省略せずに表記するようにします. ## まとめ ある事象について, その事象がもつ情報量を計算する自己エントロピーという概念と, 事象系から得られる平均の情報量を計算する平均エントロピーという2つのエントロピーを紹介しました. ポケモンWordleの話をしているはずなのにポケモンのポの字も出てこなくて退屈だったかもしれませんね. しかしながら, これでようやく本題に入ることができます. 結局"エントロピー"とやらのうま味はなんだという話になりますが, それは正に情報の価値の比較が可能になったことにあります. つまり, ポケモンWordleにおいて, ポケモン名を入力して得られる結果に対して上手く事象系を定義したうえでエントロピーを計算してやることで, どのポケモン名を入力するのが正解にたどり着くうえで効率的なのかを比較できるようになったわけです. 次回からは, ポケモンWordleにポケモン名を入力することで生起される事象系を実際に構成し, 各ポケモンにおける事象系の平均エントロピーを計算/比較してみましょう. ## 参考文献 大矢 雅則. 情報数理入門. サイエンス社, 1999年 ## 補足 有識者向けに少しだけ補足しておきます. #### Q. 自己エントロピー/平均エントロピー以外にもあるよね? A. はい, 確かに条件付エントロピーや相互エントロピーなども存在します. しかし今回の目的である, アルゴリズムの説明に関して言えばそれらは必要ないと判断したため省略しています.