はじめに
Wordleは、Web上で遊べる単語当てゲームで、毎日お題として選ばれた英単語を推測とそれに対するヒントともとに予想するゲームです。ゲーム性としては、いわゆる数当てゲームのHit and Blow(マスターマインド、numeron等)といったゲームと似ています。お題の英単語は毎日更新されて、全てのプレーヤーで共通となっていることと、プレー結果のSNSでの共有のされ方がとてもユニークであったことから、2022年頃に流行しました。
そのゲーム性がシンプルであることから、英単語以外のいろいろな単語(?)のリストで同じゲームが作成されています。ポケモンWordleは、名前の通りポケモンの名前を予想していくゲームになります。
この記事では、かつてポケモントレーナー(HGSSくらいまでプレイ)をしていた自分がポケモンWordleを、できるだけ効率的に攻略したいと思ったので、コンピューターの力を使ってこのゲームにおける最強のポケモンを探していこうと思います。
ポケモンWordleについて
ポケモンWordleもいくつか種類があるそうですが、今回はやど氏が作成したこちらのポケモンWordleを使っていこうと思います。
ルール
- ポケモンWordleは、正答として決められた5文字のポケモンを当てるゲームです 。
- プレーヤーは10回ポケモンを予想することができます。
- 予想する毎に、各文字について緑、黄、灰色のマークという形でヒントが与えられます。
- 緑色になった文字は、「お題に含まれていて、位置も合っている文字」
- 黄色になった文字は、「お題に含まれているが、位置は合っていない文字」
- 灰色になった文字は、「お題に含まれていない文字」
- 5文字とも緑になるポケモンを当てることができたらクリアです。
さらに細かいルールとして、
- 4文字以下のポケモンを予想として使うことも可能です。(お題は必ず5文字のポケモン)
- 6文字の名前のポケモン(「マスカーニャ」など)は予想として使うことができません。
- お題には、同一の文字が含まれているポケモンになる可能性もある。(キリンリキ、ルンパッパ等)
- 同様に、同一の文字が含まれているポケモンを予想することも可能。このとき、予想に重複している文字がお題にも含まれている場合は、お題に含まれている数だけ黄色(緑)になります。例えば、お題が「チコリータ」で予想が「キノココ」であるとすると、キノココの3文字目だけが黄色になります。
- 予想には全ての世代のポケモンを使うことができます。
プレー画面
お題が「パラセクト」でプレーした画面です。
最後は、「〇ラク〇ト」か「〇ラ〇クト」のどちらかの形に絞られるので、最後は自分の中にあるポケモン図鑑を一生懸命検索する必要があります。
もう一つ「クレセリア」でプレーした画面です。
かなり沼ってしまいました。意外と伝説や御三家と言われるポケモンが盲点になります。
本家Wordleをプレーした人は、違いに気がついたかもしてませんが、ポケモンWordleではほとんどのヒントが灰色で、緑や黄色の情報はあまりありません(僕が下手くそなだけかも知れませんが)。日本語の文字はアルファベットより文字数が多いので当然ですね。そのため、本家では、うまくやれば最終手までに、3文字くらいは色がついているので、断片的な情報から「英単語っぽい組合せ」を探す方法で予想することが多いですが、ポケモンでは灰色が多く「残った文字から作れるポケモン」をうまく考える必要があります。
このため、本家ほど勘でクリアできる可能性が低く、ある程度脳内ポケモン図鑑が完成していないとクリアするのが難しいゲームだと思います。
最強のポケモンの基準
ポケモンWordleをクリアする上で最も強いポケモンの条件を決める必要があります。ゲームの難易度感として、ある程度慣れた人なら10手以内でクリアすることは普通にできます。クリアできない場合も、そのポケモンが記憶から抜け落ちただけで、9手目までのヒントで絞り込むことができないということはほとんどありません。つまり、クリアするだけを目指すなら割と簡単です。
そこで、今回はより短い手数でクリアする方法を考えて、その初手で選ばれるポケモン、つまり最初に宣言するべきポケモンを最強のポケモンとすることにします。
作戦について
一旦、人間が思いついて実行できそうな作戦を考えてみましょう。
本家Wordleやその派生ゲームをプレーしたことがある人なら、「良い予想」と「悪い予想」があることは直感で理解できると思います。
ポケモンWordleでは、灰色が多いという性質があるので、他の多くのポケモンで使われている文字が灰色であることが確定すると、その分多くの候補絞ることができます。そういった文字が多く含まれているポケモンが強うそうであると考えることができるでしょう。個人的な感覚としては、「ン」、「ー」、ラ行なんかが多いの文字が多く組み合わさっているポケモンがよさそうです。
このあたりを実際に調べた記事もあるので、そちらを参考にしてみてください。
ポケモンWordleの最適な初手を考えてみた
本記事ではより定量的な基準をもとに決めていきたいと思います。
そこで、本家Wordleの攻略やHit and Blowの攻略でも使われている「平均情報量」の理論をベースに、最強のポケモンを調べていこうと思います。
平均情報量について
ここでは、平均情報量の気持ちを説明しようと思います。
ある質問に対して$N$種類の回答があり、その確率が$p_i$で表されるとき、平均情報量$H$は
H = \sum^N_{i=1} -p_i \log_{2} p_i
と計算することができます。
この平均情報量は、その質問で得られる情報量を表していて、性質として確率が均等に散らばる状況ほどより大きな値をとります。
「良い予想」や「悪い予想」と、平均情報量のつながりを具体例を使って考えてみます。アキネーターのような二択の質問を繰り返して、人物を当てるゲームを考えてみましょう。今回は100人の候補がいるとしましょう。質問はできる限り次の質問につながるように、1回の質問でできるだけ候補を減らしたいです。
そこで、最初の質問として、「はい」と「いいえ」の回答で該当する候補数が表のようになる質問を考えてみましょう
| はい | いいえ | |
|---|---|---|
| 質問1 | 50 | 50 |
| 質問2 | 1 | 99 |
質問1は「その人は男性ですか?」などで、質問2は「その人はマサラタウンのサトシですか?」などの質問があります。
どちらも候補を二分する質問ですが、質問1ではどちらの答えでも必ず50人まで候補数が減ります。質問2では「はい」となれば1回の質問で人物を当てることができます。しかし、そうなる確率は1/100で、99/100は「いいえ」と答えられるでしょう。「いいえ」は候補をしぼることができないのに、そう答えられる確率は大きくなっています。そのため、質問2の場合はほとんどのパターンで候補数が減らないという結果になるでしょう。
つまり、確率が偏っているほど候補数が減りづらいということです。この考え方は、回答の種類が増えても同じように考えることができます。
平均情報量は、この確率の散らばり具合が定量化されていて、例えば$N=2$のときは$p_1 = p_2 = 1/2$のときに最大値を取ります。
ポケモンWordleでは、人物ではなくポケモン当てゲームと言い換えることができ、ポケモンを入力することが質問に相当し、3色のヒントを回答とみなすことができます。
そこで、最初の予想として相応しい最強のポケモンを「平均情報量が最も大きいポケモン」とすることができるでしょう。平均情報量は、予想に対して返ってくる答えの確率分布が分かれば算出できるので、これをすべてのポケモンで計算するプログラムを作ればよいです。
実装
実装に際して、もう少しだけ必要な仮定を付け加えます。
- 答えとして選ばれるポケモンは、5文字のポケモンの中から均等に選ばれることにします。
- 「今日のお題」でプレーすることを想定して、答えに選ばれるポケモンは4世代までのポケモンとします。(シンオウ図鑑に登場するポケモン)
- 筆者は、5世代(ブラック･ホワイト)以降のポケモンに詳しくないので、予想として使えるポケモンも4世代までとします。1
4世代までのポケモンは全部で493匹、その中でお題になりうるポケモンは285匹です。
ポケモンの名前のリストはこちらを使用させていただきました。
実装としては、
- 予想とお題から、灰黄緑のパターンを返す関数
- 回答パターンの確率(場合の数)を管理するリスト
- 確率の分布から平均情報量を計算する関数
の3つを作れば良さそうです。回答パターンは灰=0,黄=1,緑=2と割り当ててそれを5つ並べたものとして管理しています。下のプログラムでは、それぞれの回答パターンの場合の数は、辞書形式で管理していますが、5桁の数字を3進数の値とみなすことでリストで管理することもできます。
コード
import math
f = open("poke.csv", "r", encoding="shift-jis")
poke_all = [] #全ポケモンの名前
for x in f.readlines():
n = x.split(",")
poke_all.append(n[0])
poke_num = 493
poke_pred = poke_all[:poke_num] #予想に使えるポケモン(4世代まで)
poke_ans = [x for x in poke_pred if len(x) == 5] #答えになりうるポケモン
#ans: お題のポケモン
#call: 予想のポケモン
#ヒントを5桁の数字で返す関数
def color_check(ans, call):
# 0:灰色
# 1:黄色
# 2:緑色
color = [0] * len(call)
#文字と場所が一致していたら緑(2)
for i in range(len(call)):
if call[i] == ans[i]:
color[i] = 2
for i in range(5):
for j in range(len(call)):
if color[j] != 0:
continue
if call[j] == ans[i]:#同じ文字が含まれていたら黄(1)
color[j] = 1
break
return tuple(color)
#平均情報量を計算
def get_entropy(call):
count = dict() #それぞれ色のヒントで場合の数をカウント
for x in poke_ans:
hint = color_check(x, call) #xが答えだったときの色
if hint in count:
count[hint] += 1
else:
count[hint] = 1
H = 0 #平均情報量
for v in count.values():
p = v / len(poke_ans) # 答えのポケモン数で割って確率に
H += -p * math.log2(p)
return H
#全てのポケモンの予想に対して平均情報量を計算
entropy = []
for poke in poke_pred:
H = get_entropy(poke)
entropy.append((poke, H))
print(sorted(entropy, key=lambda x:x[1])[-1])
結果
平均情報量を基準として、ポケモンwordleの中で最も強いポケモンは、
ポケモン図鑑No.405 レントラーでした!!
多くのトレーナーがシンオウを旅する時にはつれていたのではないでしょうか。自分もかっこよくて好きだったので、プラチナで育てていた記憶があります。
平均情報量は4.154でした。平均的にみて、$2^4=16$択の選択肢を1つに絞れるくらいのパワーを持っていることになります。
平均情報量を使うことで、付随して分かることがいくつかあるので、それについても見てみましょう
平均情報量ランキング
平均情報量の大きさランキングです。
順位 図鑑No. 名前 平均情報量
1 No.405 レントラー 4.15443
2 No.369 ジーランス 4.08785
3 No.383 グラードン 4.06737
4 No.437 ドータクン 4.01163
5 No.344 ネンドール 4.00544
6 No.099 キングラー 3.94865
7 No.337 ルナトーン 3.93535
8 No.485 ヒードラン 3.93524
9 No.430 ドンカラス 3.85808
10 No.364 トドグラー 3.84279
11 No.416 ビークイン 3.77560
12 No.171 ランターン 3.75281
13 No.367 ハンテール 3.71191
14 No.335 ザングース 3.69910
15 No.135 サンダース 3.67307
「ー」や「ン」が含まれているポケモンが多くランクインしていることが分かります。さらに上位勢はラ行や「ド」が含まれているポケモンがランクインしています。
あと、なぜか3,4世代のポケモン(No.252以降)が多いような気もします。後の世代ほど似たような名前のポケモンが多いということでしょうか。
レントラーチャートについて
ここまでは1手目について考えましたが、2手目以降でも同じ方法でポケモンを予想することが可能です。1手目では全てのポケモンが答えになりうるのに対して、2手目では、ヒントによって解となるポケモンの集合が小さくなっているというのが違いです。そのため、解としてあり得るポケモンの集合をプログラムで管理すれば、2手目以降も同じプログラムが使えます。
1手目レントラーに対する回答は41パターンあり、それぞれについて同じ計算をすると、次に予想するべきポケモンを1匹決めることができます。下の折りたたみは、レントラーチャートの全パターンについて、2手目のポケモンをまとめてあります。
2手目以降を全て灰色になったときは、「レントラー」→「ゴルダック」→「オニスズメ」→「イシツブテ」の順で答えることになり、イシツブテでも全て灰色のときは、「ピカチュウ」、「ジグザグマ」、「エネコロロ」の3択になります。最後の3択は、ピジョットと答えておくと、次の1手で確実に正解できます。
レントラーに対する答えと2手目
1手目、残り候補数、2手目のポケモン
灰灰灰灰灰 67 ゴルダック
灰灰灰灰黄 35 マルノーム
灰灰灰灰緑 23 オコリザル
灰灰灰黄灰 12 サクラビス
灰灰灰黄黄 4 ライチュウ
灰灰灰黄緑 2 カメックス
灰灰灰緑灰 8 マクノシタ
灰灰灰緑黄 2 フシギダネ
灰灰灰緑緑 5 エアームド
灰灰黄灰灰 16 クロバット
灰灰黄灰黄 2 フシギバナ
灰灰黄灰緑 1 ベトベター
灰灰黄黄灰 3 カメックス
灰灰黄緑緑 1 トドグラー
灰灰緑灰灰 4 カメックス
灰黄灰灰灰 26 ニドクイン
灰黄灰灰黄 12 デリバード
灰黄灰灰緑 2 カメックス
灰黄灰黄灰 6 オニドリル
灰黄灰黄黄 2 リザードン
灰黄灰緑黄 1 ヒードラン
灰黄黄灰灰 4 ベトベトン
灰黄黄黄灰 2 フシギダネ
灰黄緑灰灰 1 トリトドン
灰黄緑灰黄 1 ルナトーン
灰緑灰灰灰 7 マタドガス
灰緑灰灰黄 5 リザードン
灰緑灰灰緑 1 ワンリキー
灰緑灰黄灰 2 リザードン
灰緑灰黄黄 1 ランターン
灰緑灰緑灰 2 フシギダネ
灰緑灰緑緑 2 キャタピー
灰緑黄灰灰 1 エンペルト
黄灰灰灰灰 10 エレキッド
黄灰灰灰黄 1 チャーレム
黄灰灰黄灰 1 ラフレシア
黄灰黄灰灰 1 フォレトス
黄黄灰灰灰 1 カクレオン
緑灰灰灰灰 6 レジアイス
緑黄灰灰灰 1 レディアン
緑緑緑緑緑 1 レントラー (1手目で正解)
同じ方法で全てのポケモンについて、正解までに必要な手数を計算することもできます。正解するまでに必要な手数のポケモンの分布は、以下のようになりました。
| 1手 | 2手 | 3手 | 4手 | 5手 | 6手 |
|---|---|---|---|---|---|
| 1 | 13 | 126 | 107 | 33 | 5 |
全てのポケモン(285匹)を当てるのに必要な手数は1030手で、平均3.614手となります。
ちなみに、6手かかるポケモンは「フシギソウ」「フシギバナ」「ピカチュウ」「ジグザグマ」「エネコロロ」の5匹です。
考察
このゲームは、難しいポケモンでも6手、平均をとっても3.7手以内でクリアできることがわかります。1ゲームについて10手も予想ができるので、コンピューターを用いると、途端にヌルゲーになることが分かりました。
2手目の部分に注目すると、他にもおもしろいことがわかります。例えば、「灰灰灰緑黄」のとき、候補は2匹で「ヨーギラス」と「ダークライ」です。しかし、2手目のポケモンは、そのどちらでもない「フシギダネ」となっています。
「フシギダネ」を言えば、4文字目「ダ」の色を見ることで、次の予想で確実に正解することができます。しかし、2択の場合は1/2に賭けてどちらのポケモンを言う方が手数的にもよいです。
実は、「フシギダネ」も「ヨーギラス」も2択を必ず絞ることができるため、平均情報量は同じ1.0で、プログラム的には優劣をつけることができず、ポケモン図鑑番号が小さい「フシギダネ」が出力されているという形になります。
平均情報量は、確率の散らばり具合を示す量で、次の1手で当たりやすくするための指標になります。これは、最初に考えた平均的により短い手数でクリアするという条件とは微妙に違うということがわかります。
そこで、次はより手数を直接計算できるような方法で最強のポケモンを考えていこうと思います。
全探索アルゴリズム
ここでは、全探索による解法を考えていきます。何を探索するかというと、ポケモンWordleの全てのゲームの流れを探索します。例えば、「初手にフシギダネで灰灰灰灰灰のとき」、「初手にフシギダネで灰灰灰灰緑のとき」、「初手にフシギソウで灰灰灰灰灰のとき」...といった全ての流れを考えて、そのときの最短手数を全て調べるということです。
「初手にフシギダネで〇〇のとき」の〇〇を全てのパターンに変えて、それらの最短手数を全て足せば、初手にフシギダネと答えたときに必要な手数が分かります。
では、例えば「初手にレントラーで灰灰灰灰灰のとき」の(残り候補67匹全てで正解するための)最短手数をどうやって計算すればよいか。これは、「レントラーで灰灰灰灰灰、2手目にフシギダネで灰灰灰灰灰のとき」、「レントラーで灰灰灰灰灰、2手目にフシギソウで灰灰灰灰灰のとき」というような具合で、やはり全ての流れを計算します。
3手目以降も同様の計算をします。なんか途方もないような計算が必要になりそうですが、ここでのポイントは今の1手で最適を考える場合、次の1手のことについて全て調べればよいということです。
かなり面倒くさそうな計算が必要そうですが、実はこれを1つの式で書くことができ、それが計算のアルゴリズムにつながってきます。
以降はThe best strategies for Wordleを参考に、同じ表記を用いて式を記述します。
お題になりうるポケモンの集合を$H_0$、予想として入力できるポケモンを$T$とします。ポケモン集合に対して、最短手数を返す関数を$f()$とすると、知りたい値は$f(H_0)$となります。この関数は直接計算できませんが、再帰的に定義することができます。
f(x) = \left\{
\begin{array}{ll}
0 & (\left| H \right| = 0) \\
1 & (\left| H \right| = 1) \\
\left| H \right| + \min_{t \in T} \sum_{s \ne GGGGG} f(P(H,t,s)) & (それ以外)
\end{array}
\right.
$T$は予想として入力できるポケモンの集合、$s$は色のヒントを表していて、「$GGGGG$」は「緑緑緑緑緑」を表しています。$P$は集合$H$に含まれるポケモンのうちで、ポケモン$t$と予想したときに$s$という色の結果になるポケモンの集合です。つまり、答えとしてあり得るポケモンの集合となります。レントラーチャートから例を取ると、$t$はレントラーで、$s$は「灰灰灰灰緑」の場合は、5文字目に「ー」がついて他の文字を含まない23匹のポケモンの集合になります。(レントラーチャートの3行目を参照)。
この集合$P(H, t, s)$は、必ず元の集合$H$より小さくなるので、繰り返し計算していくと、より小さな集合$H$で$f(H)を$計算していくことになります。$H$の要素が1つになるまで小さくすると、$f(H)$が具体的な値になります。その後は、小さい集合から順にさかのぼって$f(H)$を計算することができるので、最終的に$f(H_0)$が分かります。小さいものから順番に計算するという点は、一般項が分からない数列の第100項を、初項と漸化式から順番に計算しているような感じだと思います。
$\min_{t \in T}$の部分は、全ての予想に対して最小手数と計算して、その中でもっとも手数の小さいポケモンを予想として採用することを表しています。
この方法は、局所的な最適解を採用する平均情報量とは異なり、確実に「平均的に手数が少ない」ポケモンを調べることができます。「じゃあ最初からこの方法を使えばいいじゃないか」と思うかも知れませんが、前で触れたようにかなり大がかりな計算になります。
この式では$f(H)$を1段階計算するのには、3つ目の場合分けの全ての$t$と$s$についてループを回す必要があります。$t$は予想として言うことができるポケモンなので$493$通り、$s$は5文字の色のパターンなので$3^5=243$通りです。平均的に5段階計算する必要があるとすると、計算量はざっくり$(493 \times 243)^5 \sim 10^{25} $となります。大きめな見積もりかも知れませんが、それでも何年で計算できるとかのレベルではないことは確かです。
アルゴリズムの工夫
このままでは、計算が終わるまでにポケモンの新作がいくつ出るか分からないので、せめて寝て起きたら答えが分かるくらいには短縮したいですね。そこで、全探索アルゴリズムを工夫することで計算量を減らそうと思います。「枝刈り」という名前で呼ばれる方法で、考え方としては、探索しなくてよさそうな無駄な所は探索しないということをします。
ここでは、平均的に最短になる場合さえ分かればよいので、それを利用します。
大雑把に分けて、2つの場合を「探索しなくてよさそうな場合」と考えて枝刈りをします。
- 正解までに手数がかかりすぎる場合
- そのポケモンを予想することで得られる情報が少ない場合
1つ目の場合は、例えば最初の3手で「フシギダネ→フシギソウ→フジギバナ」というように、ほとんど候補が絞れなさそうな場合、正解するのが10手以上になるポケモンもいる可能性があります。平均情報量を使った結果では、どんなに長くても6手までで正解できるはずなので、10手かかる場合を考えるのは無駄になっている可能性が高いです。こういう場合はそこで探索を打ち止めにして、無駄な計算を削減します。この工夫は計算量の式の指数の値が小さくなるようにする工夫になります。今回は7手以上になる場合があるポケモンは計算から除外します。
2つ目の場合は、探索するポケモンの数を減らすことを目的としています。前の結果からレントラーと言っておけば、かなり良い結果になることが分かっています。そのため、全探索した結果「ピィ」とか「ピッピ」が最も良くなるという結果になるのは考えにくいです。そこで、良い結果にならなそうなポケモンはあらかじめ探索から除外します。
今回は、平均情報量を基準にして、良い結果になりそうなポケモンを絞っておきます。平均情報量は、先ほどの結果から「完璧ではないが、まあまあ良さそう」な基準なので、平均情報量の上位$N$匹だけを探索するという形にしたいと思います。これは計算量の式の493の部分が小さくなるようにする工夫になります。
しかしながら、最も最適なポケモンが上位$N$匹に入っていない可能性もありえます。そのため、一般的には$N$が大きいほど結果の精度が高くなりますが、反対に計算時間が増えることになります。今回は上位10匹を探索するようにしました。また、候補が少なったときは、上位10匹に加えて候補に残っているポケモンを探索するようにしました。これは、例えば1/2でポケモンを当てに行った方が最適に場合を確実に探索してもらうためです。
実装
理論の部分が長くなりましたが、やることとしては$f()$にあたる関数を作って、アルゴリズムの工夫を入れ込むことになります。再帰関数は一見難しそうに見えますが、コンピューターの得意な範囲なので、実装は難しくないです。
再帰関数の練習問題として、フィボナッチ数列を再帰を使って求めるものがよくあるので、それら参考にすると再帰関数を理解しやすくなると思います。
コード
import math
f = open("poke.csv", "r", encoding="shift-jis")
poke_all = [] #全ポケモンの名前
for x in f.readlines():
n = x.split(",")
poke_all.append(n[0])
poke_num = 493
poke_pred = poke_all[:poke_num] #予想に使えるポケモン(4世代まで)
poke_ans = [x for x in poke_pred if len(x) == 5] #答えになりうるポケモン
#ans: お題のポケモン
#call: 予想のポケモン
#ヒントを5桁の数字で返す関数
def color_check(ans, call):
# 0:灰色
# 1:黄色
# 2:緑色
color = [0] * len(call)
#文字と場所が一致していたら緑(2)
for i in range(len(call)):
if call[i] == ans[i]:
color[i] = 2
for i in range(5):
for j in range(len(call)):
if color[j] != 0:
continue
if call[j] == ans[i]:#同じ文字が含まれていたら黄(1)
color[j] = 1
break
return tuple(color)
#平均情報量を計算
#poke_H:その時点でのお題候補のポケモン
def get_entropy(poke_H, call):
count = dict() #それぞれ色のヒントで場合の数をカウント
for x in poke_H:
hint = color_check(x, call) #xが答えだったときの色
if hint in count:
count[hint] += 1
else:
count[hint] = 1
H = 0 #平均情報量
for v in count.values():
p = v / len(poke_H) # 答えのポケモン数で割って確率に
H += -p * math.log2(p)
return H
#枝刈りの時に使用します
#十分に大きな値ならなんでもいいです
INF = 10** 5
#以降は再帰関数を用いた定義と同じ表記を使っています。-------------------------------------------
H = set(poke_ans)
T = list(poke_pred)
# 最小手数を計算する関数。
# H:お題候補のポケモンの集合
# depth:再帰の深度。正解に必要な手数
def f(H, depth):
#7手目に達した場合は正解にINF手かかることにする
# if len(H) == 1:
# return 1
if depth == 7:
return INF
min_sum = INF
entropy = []
selected_T = set()
#平均情報量から次の手のポケモンを絞る
for t in T:
entropy.append((get_entropy(H, t), t))
entropy = sorted(entropy, reverse=True) #ポケモンを平均情報量の高い順に並べる
for i in range(10):
selected_T.add(entropy[i][1])
#答え候補のポケモンが10匹以下で、平均情報量の基準から漏れた場合は追加する
if len(H) <= 10:
selected_T |= H
#T:宣言するポケモンの集合
#H:答えになり得るポケモンの集合
for t in selected_T:
# print(t)
d = dict()
flag = 0
for h in H:
if h == t: #宣言するポケモンが答えと一致したとき
flag = 1
continue
s = color_check(h, t)
if s not in d:
d[s] = set([h])
else:
d[s].add(h)
#どのポケモンであってもヒントが同じになるときは無視
if len(d) == 1 and flag == 0:
continue
sum_f = 0
#シグマの中身を計算
for k, p in d.items():
#|H|=1の場合分け
if len(p) == 1:
sum_f += 1
#|H|=2のときは必ずf(H)=3
#再帰関数を呼び出す回数を減らす工夫
elif len(p) == 2:
sum_f += 3
else:
sum_f += f(p, depth+1)
#和がINFを超えた場合そこで中断
if sum_f >= INF:
break
#シグマの値が最も小さくなる場合を記録
if min_sum > sum_f:
min_sum = sum_f
return len(H) + min_sum
print(f(H, 1))
結果
今回は、初手で平均情報量が大きい10ポケモンのみで計算をしました。それぞれのポケモンの総手数(全てのポケモンを当てるのに必要な手数)で並べると以下のようになりました。
順位 図鑑No. 名前 総手数 平均手数
1(2) No.369 ジーランス 964 3.3825
2(1) No.405 レントラー 968 3.3965
3(3) No.383 グラードン 969 3.4000
4(9) No.430 ドンカラス 970 3.4035
5(7) No.337 ルナトーン 978 3.4316
6(6) No.099 キングラー 979 3.4351
6(5) No.344 ネンドール 979 3.4351
8(8) No.485 ヒードラン 980 3.4386
9(4) No.437 ドータクン 987 3.4632
10(10) No.364 トドグラー 990 3.4737
括弧内の数字は、平均情報量を基準とした時の順位です。
ポケモンwordleの中で最も強いポケモンは、「ジーランス」になりました。
HGSSでタケシの手持ちに入っていたポケモンですね。
初手で「ジーランス」を選択することで、理論上は平均3.3825手以内でゲームをクリアできることが分かりました。また、平均情報量と比較しても総手数が60手以上減らせるということが分かりました。
今回は、全探索と言っておきながら、計算量の都合ですべての場合を計算していません。そのため、964手で全てのポケモンを正解できるルートが存在することは保証されますが、それより少ない手数のルートが存在する可能性はあります。従って、より正確な計算を行っていくと順位が変動する可能性があります。
ここに関しては、探索するポケモン数(今回は10ポケモン)を徐々に増やすことで、必ず最適解に収束するはずなので、変化しなくなる部分を見つけることで、ある程度最適な答えまでたどり着けると思います。
また、今回は6手で計算を打ち止めしましたが、どのように質問していっても7手以上かかるポケモンがいる場合は、必ずINF手以上の値が返ってくるため、これら10匹のポケモンを初手に使えば、全てのポケモンでを6手以内で正解できる手順があることがわかります。ただし、こちらも同様にあえて7手かかるポケモンを作る手順の方が、全体の手数を小さくできる場合があるので、可能手数を増やして精度を上げると結果が変わる可能性があります。
おまけ
ポケモンWordleのゲームバランスは、既存のポケモンしか予想に使えないという制約があるために保たれていて、それゆえに面白いゲームとなっています。おまけでは、ポケモンWordle界での「ミュウツー」を作ってみたいと考え2、ゲームの要であるこのルールを破った場合について考えていきます。
まだ登場していないポケモンの名前、つまり任意の5文字の文字列を入力できた場合、どのポケモンが最適なのかというのを調べてみました3。平均情報量を基準として、似た名前のポケモンは平均情報量も近い値になるということから、山登り法を使って探索しました。
結果は図鑑No. ???「ラルイーン」が最強のポケモンということになりました。平均情報量は4.634で、レントラーの4.154と比べても圧倒的であるという事が分かります。「ー」や「ン」、ラ行が有力そうであるという事前の予想と、だいたい合ってそうな結果ですね。
「ラルイーン」が、初手の予想だけに使える特別なポケモンだとすると、初手に「ラルイーン」と言った場合の総手数は925手になります。やはりこちらの場合でも圧倒的な数字ですね。新作のポケモンで「ラルイーン」が追加されたら、ポケモンWordleの環境ポケモンになるのは間違いなさそうです。