ポケモンWordleの最適戦略

概要

ポケモンWordleの最適戦略を計算しました.

https://github.com/habara-k/pokemon-wordle-solver

計算済みの戦略をシミュレートできるWebサイトも作ってみたので, ぜひ使ってみてください.

https://habara-k.github.io/pokemon-wordle-solver/

最適戦略とは

戦略とは

次のような図で表されるものを戦略と定義します.

ランクルス
├─ 🟨⬜⬜⬜⬜ => エビワラー
│               ├─ ⬜⬜⬜🟨⬜ => ギラティナ
│               │               └─ 🟩🟩🟩🟩🟩
│               ├─ ⬜⬜🟨🟨⬜ => フワライド
│               │               └─ 🟩🟩🟩🟩🟩
|               ├─ ⬜⬜⬜🟩⬜ => マグマラシ
│               │               ├─ ⬜⬜⬜🟩🟩 => ヒノアラシ
│               │               |               └─ 🟩🟩🟩🟩🟩
│               │               ├─ 🟨⬜⬜🟩🟩 => タマザラシ
│               │               |               └─ 🟩🟩🟩🟩🟩
│               │               └─ 🟩🟩🟩🟩🟩
...             ...

図の戦略は, 次のように解釈します.

初手ランクルスを入力します. その返答が

1. 🟨⬜⬜⬜⬜ のとき, 次にエビワラーを入力します. その返答が
   1. ⬜⬜⬜🟨⬜ のとき, 次にギラティナを入力して正答となります.
   2. ⬜⬜🟨🟨⬜ のとき, 次にフワライドを入力して正答となります.
   3. ⬜⬜⬜🟩⬜ のとき, 次にマグマラシを入力します. その返答が
      1. ⬜⬜⬜🟩🟩 のとき, 次にヒノアラシを入力して正答となります.
      2. 🟨⬜⬜🟩🟩 のとき, 次にタマザラシを入力して正答となります.
      3. 🟩🟩🟩🟩🟩 のとき, 正答となります.
   4. ...
2. ...

最適とは

最適の定義としては

1. 平均入力回数が最小
2. 最悪ケースの入力回数が最小

等が考えられると思いますが, ここでは 1. の 「平均入力回数が最小となる戦略」を最適戦略と定義します.

理由

「最悪ケースの入力回数の最小値」で戦略を評価する場合, 例えば次の戦略A,Bの優劣をつけることができません.

• 戦略A: $100$ケース全てに対して $5$回の入力で正答する.
• 戦略B: $99$ケースに対して $4$回の入力で正答し, $1$ケースでのみ$5$回の入力で正答する.

また, 戦略Aは戦略Cよりも優れていることになってしまいます.

• 戦略C: $99$ケースに対して $4$回の入力で正答し, $1$ケースでのみ$6$回の入力で正答する.

さらに実際に平均最小戦略を求めたところ, 最悪ケースは$6$~$7$回でした.
ポケモンWordleでは$10$回までの入力が許されていることを踏まえて, 平均入力回数で戦略を評価するのが妥当であると判断します.

最適戦略の計算

入力可能なポケモンは全部で846匹も存在します.
したがって戦略として考えられるものは無数に存在します.

以下では, 最適な戦略を効率よく見つける方法を考えていきます.

動的計画法(メモ化)

「まだ入力していないポケモンで, 答えになり得るポケモンの候補が $S$ まで絞れている状況で, その後の平均入力回数の最小値」を $f(S)$ とします.
このとき, $f(S)$ には次の漸化式が成立します.

$$\begin{aligned} f(\emptyset) &= 0 \\ f(S) &= 1 + \frac{1}{|S|} \min_{g \in \text{入力可能なポケモン}} \sum_{T \in \mathrm{Part}(S,g)} f(T) \cdot |T| \end{aligned}$$

ただし $\mathrm{Part}(S,g)$ は, 候補 $S$ に対してポケモン $g$ を入力した際, 次の候補となりうるようなポケモンの集合の全体を表します.

例: $S=\{$フシギダネ, フシギソウ, フシギバナ, リザードン$\}$, $g=$フシギダネ のとき,
$\mathrm{Part}(S,g) = \{ \emptyset, \{$フシギソウ, フシギバナ$\}, \{$リザードン$\} \}$

この漸化式に従って $f($答えとなり得る全てのポケモン$)$ を計算すれば, それが平均入力回数の最小値となります.

さらに $f$ の計算式を辿って「どの $g$ で $\sum_{T \in \mathrm{Part}(S,g)} f(T) \cdot |T|$ の最小値を取っていたか？」を再帰的に調べていけば, 平均入力回数を最小化する戦略を求めることができます.

しかしこの計算方法には無駄が多く, このままだと時間がかかり過ぎてしまいます.

分枝限定法

前節で出てきた$f(S)$の漸化式における

$$\min_{g\in\text{入力可能なポケモン}}$$

の部分は非効率です. なぜなら, 明らかに悪そうな入力も全て考慮する必要があるからです.
分枝限定法は, この無駄な探索をできるだけ省くアルゴリズムです.

今 $f(S)$ を計算したい状況で,

• $S$ を平均 $\mathrm{ub}(S)$ 回の入力で正答できるような戦略を見つけることができた
• $g$ を次の入力にした場合, 平均入力回数が $\mathrm{lb}(S,g)$ を下回ることはないことが断定できた

とします.　このとき $\mathrm{ub}(S) \le \mathrm{lb}(S,g)$ であれば, $g$ を入力する場合の探索を省くことができます.

たくさん探索を省くためには, 小さな暫定値 $\mathrm{ub}(S)$ と大きな下界 $\mathrm{lb}(S,g)$ を (ただし高速に) 計算することが重要です.

暫定値$\mathrm{ub}(S)$の計算

候補 $S$ に対してできるだけ平均入力回数が小さくなるような入力として, ここでは平均情報量を最大化する入力

$$\tilde{g}(S) := \argmin_{g \in \text{入力可能なポケモン}} \sum_{T \in \mathrm{Part}(S,g) \setminus \{\emptyset\}} |T| \log_2|T|$$

を用います. これに従って $\mathrm{ub}(S)$ は以下の漸化式で高速に計算できます.

$$\begin{aligned} \mathrm{ub}(\emptyset) &:= 0 \\ \mathrm{ub}(S) &:= 1 + \frac{1}{|S|} \sum_{T \in \mathrm{Part}(S,\tilde{g}(S))} \mathrm{ub}(T) \cdot |T| \end{aligned}$$

下界$\mathrm{lb}(S,g)$の計算

候補 $S$ に対して $g$ を入力した際に, あり得る次の候補を $T \in \mathrm{Part}(S,g)$ とします.

ここで候補 $T \neq \emptyset$ を正答するまでの平均入力回数は, どんなに良くても $2 - 1/|T|$ 回です.

理由

$1$回で当たるのは高々 $1$ 通りです.
他の $|T|-1$ 通りが全て $2$ 回で当たったとしても, 平均入力回数は $(1 + 2(|T|-1)) / |T| = 2 - 1/|T|$ にしかなりません.

これを用いて, $\mathrm{lb}(S,g)$ を次式で高速に計算することができます.

$$\mathrm{lb}(S,g) := 1 + \frac{1}{|S|} \sum_{T \in \mathrm{Part}(S,g) \setminus \{\emptyset\}} (2 - 1/|T|) \cdot |T|$$

高速化

ここまでで, かなり高速に最適戦略を求めることができるようになりました.
あとは細かいチューニングをしていきます.

良さそうな入力から探索する

$$f(S) \gets 1 + \frac{1}{|S|} \min_{g \in \text{入力可能なポケモン}} \sum_{T \in \mathrm{Part}(S,g)} f(T) \cdot |T|$$

を計算する際に, $g$ として平均情報量が大きいものから探索するようにしました. なぜなら暫定値を

$$\mathrm{ub}(S) \gets \min\left(\mathrm{ub}(S), 1 + \frac{1}{|S|} \sum_{T \in \mathrm{Part}(S,g)} f(T) \cdot |T|\right)$$

と小さく更新していけるため, 最適な入力$g$を早めに引き当てることができれば探索を省略しやすくなるからです.

和が暫定値を超えた時点で終了

$$f(S) \gets 1 + \frac{1}{|S|} \min_{g \in \text{入力可能なポケモン}} \sum_{T \in \mathrm{Part}(S,g)} f(T) \cdot |T|$$

を計算する際に $\sum_{T \in \mathrm{Part}(S,g)} f(T) \cdot |T|$ を計算しますが, この和が途中で $(\mathrm{ub}(S) - 1) \cdot |S|$ を超えてしまうと, それ以上 $g$ を探索する必要がありません.

候補の大きさ$|S|$が小さいときには例外処理

$|S| = 1, 2$ のときは, 候補内の要素を順番に入力していくのが最適です.

また $|S| = 3$ のときは, 入力として候補内の要素のみを考慮すれば十分です.

理由

候補内から入力した場合, 平均入力回数は悪くても $(1+2+3)/3 = 2$回です.
候補外から入力した場合, 今回は絶対当たらないので平均入力回数は良くても $2$回です.
よって候補内から入力する場合だけ考慮すれば十分です.

下界$\mathrm{lb}(S,g)$ をもう少し正確に計算する

$$\mathrm{lb}(S,g) := 1 + \frac{1}{|S|} \sum_{T \in \mathrm{Part}(S,g) \setminus \{\emptyset\}} \left( 1 + \frac{1}{|T|} \min_{g^\prime} \sum_{U \in \mathrm{Part}(T,g^\prime) \setminus \{\emptyset\}} (2 - 1/|U|) \cdot |U| \right) \cdot |T|$$

とすることで $\mathrm{lb}(S,g)$ そのものの計算コストは増えますが, より大きな下界$\mathrm{lb}(S,g)$ を得ることで探索を大幅に省くことができ, 結果として速くなりました.

平均の計算を整数で行う

$f(S), \mathrm{ub}(S), \mathrm{lb}(S,g)$ は全て $|S|$ 倍することで整数となります.

整数で計算すると除算もなく高速で, さらに誤差のない計算が可能です.

暫定的な入力 $\tilde{g}(S)$ の改善

$$\tilde{g}(S) := \argmin_{g \in \text{入力可能なポケモン}} \sum_{T \in \mathrm{Part}(S,g) \setminus \{\emptyset\}} |T| \cdot (\textcolor{red}{0.1|T|} + \log_2|T|)$$

とした方が僅かに暫定解の精度が上がり, 探索をさらに削減できました.

Rustで実装

高速な言語を使うことも重要です. (初期実装はPythonでした)

並列化

4並列で3倍程度の高速化に成功しました.

数値実験

計算環境は M1 Macbook Pro 2020 を用いました.

答えの候補	最小平均入力回数	最悪ケース[回]	計算時間[秒]
DP以前	3.3404 (= 942/282)	6	95
BW以前	3.4947 (= 1328/380)	6	1051
XY以前	3.5576 (= 1512/425)	6	3497
SM以前	3.6139 (= 1713/474)	7	11488
剣盾以前	3.6379 (= 1859/511)	6	24891

計算済みの最適解とソースコードはGitHubに公開している他, Webサイトで使ってみることもできます.

さいごに

ポケモンWordleや本家Wordleの平均入力回数の最小化問題を解いている人は (調べた限り) 見つからなかったので, (ポケモンWordle限定ですが) 現実的な時間で解くことができて良かったです.

それでは皆さん, 最適なポケモンWordleライフを!