# ポケモンWordleを攻略しよう(中編)

## はじめに
このドキュメントは **ポケモンWordleを攻略しよう(中編)** です. [前編](https://hackmd.io/@niart/HJNpxydk9)は主に専門的な用語の解説となっているため, 基本的には先にそちらを読むことを推奨します.

以前公開した[**Project\_Verbum**](https://github.com/niart120/Project_Verbum)について, 関連ドキュメントを書いていなかったので書くことにしました.

そもそもProject\_Verbumってなんだよという人向けに説明すると, ポケモンWordleを~~破壊~~攻略するために作ったプログラムです.


例えば, こんな感じでランダムなお題とその解法を自動生成してくれます.

このプログラムに用いているアルゴリズムの詳細について説明をしていこうと思います.

前編にて自己エントロピー/平均エントロピーの解説をしたので, こちらでは本題の1つであるポケモン名の評価方法の説明をしたいと思います.

引き続き, なるべく平易な表現になるように心がけますが, 数学的な表現は多少難解になるかもしれません. ご容赦ください.

あるいは有識者の方々に関しましては, 数学的な議論に誤りなどがあれば遠慮なく指摘していただけると幸いです.

## ポケモンWordleとは
そもそも[**ポケモンWordle**](https://wordle.mega-yadoran.jp/)がどのようなゲームなのかを説明していませんでしたね.

このドキュメントを閲覧している方々には不要かとは思いますが, 改めて説明しておきましょう.

ポケモンWordleとは, [**やど**](https://twitter.com/giga_yadoran)氏が元ゲームである[Wordle](https://www.nytimes.com/games/wordle/index.html)にインスパイアされて開発した, ポケモンの名前を当てるクイズゲームです.

ゲームの流れとしては,

1. ポケモンの名前(五文字まで)を質問する
1. 質問したポケモンがどれくらい近いかのヒント(後述)が返答される
1. 上記を10回繰り返すまでにお題のポケモンの名前を答えられれば勝利, 答えられなければ敗北

という流れで進行します.

2.の質問に対するヒントというのは, 質問された名前の各文字について, その文字が答えのポケモンに含まれていれば黄色に, 含まれてかつ位置が一致しているなら緑色に点灯することで知らされます.

その他補足ルール及び特殊な例を以下に引用します.

> **補足ルール**
> * 今日のお題モードにはダイパまでのポケモンしか出ません
> * その他のモードではお題の出題範囲を選べます
> * お題のポケモンは必ず５文字です
> * 「ドククラゲ」のように同じ文字がお題に含まれる場合があります
> * 回答には４文字以下のポケモンも入力することができます
> * 回答には剣盾までのポケモンが使えます
>
> **特殊な例**
> 「キノココ」のように同じ文字が含まれるポケモンを入力した場合、色の塗り方が少し特殊です
> 例えば、お題が「ココロモリ」入力が「キノココ」の場合、お題にも入力にも「コ」が２つあるので,
>
> (画像略)
>
> このように両方の「コ」が黄色になります
>
> お題が「チコリータ」入力が「キノココ」の場合、お題には１つしか「コ」がないため
>
> (画像略)
>
> このように１つ目の「コ」だけ黄色になります
>
> つまり「同じ文字はお題に含まれる数までしか黄色(緑)にならない」ということです

(ポケモンWordle How To Play より引用)

加えて, 次の独自ルールを導入します.
* 出題範囲はその他のモード(エンドレス/チャレンジ)準拠とする.
* 質問に用いることができるポケモンは5文字のポケモンのみとする.

つまり, お題/質問に使われるポケモン名は全て初代から剣盾までの名前が5文字からなるポケモンを用いることにします.

この独自ルールを制定した理由としては次の2つがあげられます.

1点目はお題のプールがダイパまで/剣盾までのいずれにしても, 難易度がさほど変わらないこと.
2点目は出題/質問のプールを同一のものとして扱うことで以降の議論における話を簡単にするためです.

これらのルールを加えて考察を進めて行きたいと思います.

## 問題の定式化
前回の最後で触れた通り, 質問に使うポケモン名に対して事象系を定義してアレコレするのですが, その為にはいくつか準備をしてやる必要があります.

細かい用語の定義が曖昧なまま議論をしても仕方がないので, まずはポケモンwordleのルールを考えるところからはじめましょう.

### ルールの立式
ポケットモンスター赤緑からソードシールド(DLC含む)までに実在する, 名前が5文字からなる, 515種類のポケモン$s = c_{1}c_{2}c_{3}c_{4}c_{5}$(e.g. $s=$"バンギラス"なら, $c_{1}=$'バ', $c_{2}=$'ン', $c_{3}=$'ギ', $c_{3}=$'ラ', $c_{5}=$'ス')の集合$S=\{$"フシギダネ", "フシギソウ", "フシギバナ", "カメックス", $\dots$, "ブリザポス", "レイスポス"$\}$を考えます.

$S$の部分集合として, お題の候補となるポケモンの集合を$A\subseteq S$, 質問に使うことが出来るポケモンの集合を$Q\subseteq S$を定めます. 今回は, 先ほどの独自ルールを踏まえて$Q=A=S$としておきます.

(今回は$Q=A=S$なのに何故部分集合とか出てきて別途定義しているんだ, と混乱する方もいるかもしれません. 今回は扱いませんが, 今後$A$の範囲を赤緑まで/金銀まで/etc...などに絞って議論することを考慮して, このように定義しています)

ポケモン名を比較したとき, 各文字について得られる結果は"文字と位置が一致", "文字が含まれる", "それ以外"の3通りです.

従って, それぞれに0, 1, 2を割り当てた集合$T=\{0, 1, 2\}$を考えることで, 最終的な比較結果は五つ組$r\in R=\{(t_1, t_2, t_3, t_4, t_5)|t_1, t_2, t_3, t_4, t_5\in T\}$として表すことができます.

$Q, A, R$を用いて, ポケモン名を比較する関数$f$を$f:Q\times A \rightarrow R$として与えることにしましょう.

例えば, 質問が$q=$"ハンテール"$\in Q$, お題が$a=$"サイホーン"$\in A$だったとき, "ハンテール"の4文字目の"ー"は文字と位置が一致しており, 2文字目の"ン"はサイホー'ン'に含まれますから, 比較結果は次のようになります.
\begin{align}
f(q,a) = r = (2, 1, 2, 0, 2)
\end{align}

### 事象系の構成
ここまでの話を踏まえて, 具体的に事象系をどのように構成するかを考えていきたいと思います.

お題となるポケモン$a$が$A$から一様に選ばれることを仮定します. (中学数学の言葉でいえば, どのポケモンが選ばれるかは"同様に確からしい", ですね.)

このとき, 最初に質問に用いるポケモン$q\in Q$と比較結果$r\in R$について, $f(a,q)=r$を満たす$a\in A$の場合の数が計算可能なことから, $q$を用いたときに$r$が返ってくる確率も計算出来そうです.

とはいうものの, なんだか記号ばかりで分かりにくいですね. 先ほどのハンテールの例($q=$"ハンテール")で考えましょう.

お題が$a=$"サイホーン"$\in A$だったときの比較関数の結果は$f(q,a)=(2,1,2,0,2)$でしたが, この結果が返ってくるポケモンは他にも"デスカーン", "バクフーン"などが居ます.

$A$に含まれるすべての要素を調べてやると, 該当するポケモンは例示していたサイホーンを含め計7種類居ることが分かります.

このような, "ポケモン$q$を用いると比較結果$r$が返ってくるようなポケモンの集まり"を, 集合$F_{q,r}$として数式で表すと次のようになります.
\begin{align}
F_{q,r} = \{a|f(a,q)=r, \forall a\in A\}
\end{align}

今回でいえば, $F_{q,r}=\{$"サイホーン", "デスカーン", $\dots$, "ズガドーン"$\}$となりますね.

この集合の濃度(集合に含まれる要素の個数)が, ハンテールを質問に用いたときに$(2,1,2,0,2)$が返ってくる場合の数とみなすことができます. 一方で, 分母となる全ての場合の数は$A$の濃度がそのまま使えます.

従って, $|\cdot|$を集合の濃度を表す記号とすれば, 初手に$q=$"ハンテール"を入力した場合に$r=(2,1,2,0,2)$が返ってくる確率は,
\begin{align}
P_q(r) = p_{q,r} = \frac{|F_{q,r}|}{|A|} = \frac{7}{515}
\end{align}
と表すことが出来ます.

これは$r=(2, 1, 2, 0, 2)$という比較結果に限定されず, 全ての比較結果について同様に確率を計算することが出来ますし, どのようなポケモンを質問に用いても同様の議論が成立します.

この事実を用いて, 任意のポケモン名$q\in Q$について, その比較結果を事象とみなした事象系$X_q=(R,\boldsymbol{p_q})$を構成しましょう.

## 平均エントロピーの計算
さて, 事象系が定義出来たところで, いよいよ各ポケモンから得られる事象系$X_q$の平均エントロピーを計算してみましょう.

前回の話を踏まえると, ポケモン名$q\in Q$によって構成される事象系$X_q=(R,\boldsymbol{p_q})$の平均エントロピー$H(X_q)$は次のようになりますね.
\begin{align}
H(X_q) &= -\sum_{r\in R} P(r)\lg P(r)\\
&= -\sum_{p_{q,r}\in \boldsymbol{p_q}} p_{q,r}\lg p_{q,r}
\end{align}

ここまで書いておいてなんですが, 生じうる事象$r\in R$は単純計算でも$3^5=243$通りあります.

矛盾が生じるなどで存在しない事象を取り除いたとしても, 人間が手計算でやるのは無理がありますね.

ということでプログラミングの出番です.

冒頭で述べたProject_Verbumの実装では, 平均エントロピーの計算過程が前計算ステップと実計算ステップに分かれています.

それぞれの方針を簡単に述べておきます.

前計算ステップについては, $A, Q$から任意の要素を選んで作るペア$(a,q)\in A\times Q$について, $f(a,q)$を前計算しておき, その計算結果$r$をキーとしてもつ辞書を用いて$F_{q,r}$を生成/管理します. ここら辺の前計算に関する具体的な実装については`Solver`の`__init__`関数を参照いただければと思います. ([solver.py](https://github.com/niart120/Project_Verbum/blob/main/src/solver.py))

実計算ステップについては, 前計算ステップで生成した辞書が持っている全ての$F_{q,r}$を用いて, $P_q(r)$計算したうえで 平均エントロピーの定義に従って計算するだけです. 具体的な実装については, こちらも上記の`Solver`内に含まれる`get_entropy`関数をご参照いただければと思います.

## 実験
平均エントロピーをどのように計算するかという話は以上で終わりなのですが, 流石にこれだけだと片手落ちといいますか, あまり面白くは無いですね.

ということで, 具体的にどのようなポケモンが平均エントロピーが高い, 即ち質問に用いたときにより多くの情報が得られるかというのを調べてみました. その結果は以下の通りです.


Twitter上などでも多くの方が指摘されていた通り, やはりジーランスが強いようですね. その後ろもレントラー, ネンドール, グラードン, ランクルスと見覚えのある名前が続きます.

solver.pyを実行することで, 同様の結果が得られますから, もし気になる人が居ればご自分でプログラムを実行したり, 弄ったりして色々遊んでみてください.

例えば, solver.pyを少し書き換えてやれば逆に平均エントロピーが最も低いポケモンが誰かを調べてみることも出来ますね.

## 考察
どうやら, 初手に用いるべきポケモンはジーランスが良さそうに思えます.

が, 本当にそれで結論付けて良いのでしょうか?

例えば, 今回の定義は今日のお題モードとは前提条件が異なるため, この結果だけで議論するのは不正確なように思えます.

実際, 条件を揃えた場合(集合$A$の範囲をダイヤモンドパールまでに出てくるポケモンに制限した場合)はレントラーから得られる平均エントロピーが最も高いことが分かっています.

(プールを狭めた場合の計算結果です)

また, 初手をジーランス(あるいはレントラー)として固定したとしても, その後の手筋についてはどのように決めれば良いのでしょうか?

或いはそもそも平均エントロピーが最も高いポケモンを初手に選ぶことは本当に正解といえるのか? などといったことを考えると, まだまだ議論の余地は残されていそうです.

## まとめ
ここまで, 前編にて説明した前提知識に基づいて, ポケモン名の評価方法についてお話してきました.

具体的になにをやったかと言えば, ポケモンWordleのルール説明から始まって, 考えなければならない問題についての定式化を行ったうえで, 事象系の定義/エントロピーの計算方法を説明しました.

また, 実際に全てのポケモンから生成される事象系の平均エントロピーを計算し, どのポケモンを入力するのが価値が高いかを比較しました.

しかしながら, 二手目以降の手筋の決定法や, お題となるポケモンのプールが異なる場合に関しての評価については更なる検討が必要です. 後編では, そのあたりの詳細を詰めていこうと思います.