Pokémon RNG Advent Calendar 2017の9日目の記事です。
他の記事も面白いので読んでみましょう。そして参加しましょう。
先週@Blastoise_Xさんによりある問いが出されました。
乱数調整で遊ぼう - ろいしんぶろぐ
というわけで3時間で解いてみたのでその解答・解説です。
以下、ネタバレ注意。
では解いていきましょう。
というか何ができるか分からないと調べようがないよね。
3種類くらい行動があるらしい。
自動販売機だ。
当たりが出そう。
ペラップ～♪
音程は4通り観測できた。
何か捕まえた。
必要な情報は以下の2つ。
・乱数列
・乱数使用方法
どちらも事前情報がなく、片方だけを先に特定するのも無理そうなので、
両方を仮定して観測された事象を説明できたらOK、という考え方でいきましょう。
対象とする事象は、まずは考えやすいものにします。
0.で観測された事象のうち、情報が得られたのは以下の2つ。
・ペラップの音程
処理がそのままであれば、8192通りの音程を4つに分けているものと思われる。
「8192通り」の数字を変えられると場合によっては特定が面倒になる。
・出現ポケモン
他の情報は後回しとし、個体値だけを考えると非常に単純で情報量も多い。
変な個体値決定方法は考えない。とりあえず考えるとしても第4世代方式とする。
今回は後者の「出現ポケモン」の個体値情報から考えることにしました。
「乱数列」「乱数決定方法」の仮定を、複数の観測データを説明できるまで行います。
説明できればきっとその仮定は正解です。
どうしても上手くいかない場合は1に戻ってみるのもいいでしょう。
まずは「乱数列」の仮定から。
おそらくはポケモンで使用されている乱数列だと当たりをつけました。でないと難しすぎる。
某世代みたいに説明書に書いてあると推測しやすくなるのでとてもいいです。
ポケモンでよく使われる乱数列は以下の通り。
・LCG（32bit）
普通に全検索できる
「s[n+1] = s[n] + 0x41c64e6d + 0x6073」の形がよく使われている。
使用例）
第3世代
第4世代
・LCG（64bit）
全検索したい？スパコン使ってね！
「s[n+1]=s[n] * 0x5d588b656c078965 + 0x269ec3」の形が使われている。
使用例）
第5世代（性格値乱数列）
・MT
初期シード32bitならなんとかなる、けど計算が少し大変
使用例）
第4世代（孵化乱数列）
第5世代（個体値乱数列）
第6世代
・TinyMT
初期シード32bitならなんとかなる、けど計算が少し大変
使用例）
第7世代（孵化乱数列）
・SFMT
初期シード32bitならなんとかなる、けど計算が少し大変
使用例）
第7世代
難易度的にはLCG（32bit）が無難なので、とりあえずそれの良く使われている形を仮定しましょう。
乱数値も上位16bitを使っているので、そのように仮定します。
次は「乱数決定方法」の仮定。
今回は、主にこっちの仮定が中心です。
こちらもポケモンで使われている方法から考えます。
・仮定1：第4世代方式
6つの個体値を2つの乱数を使って決定。
1つ目の乱数でHABを下から5bitずつ、2つ目の乱数でSCDを下から5bitずつを使って決定する。
2連続で遭遇したポケモンの個体値を入力して検索するも、
2つが近い位置に見つからなかったためハズレ。
・仮定2：割合取得方式
0～n-1を生成するのに「r * n / (rmax + 1)」みたいなことをする方式。
使用例）
DPtの性格（r / 0xa3eで0～24取得）
第5世代（参考：BW出現スロット等の閾値検証）
第6世代
第5世代以降のHABCDSの順に決定する方式で計算してみた。
試した事象全てで連続2個体の間の消費数が30前後になったので、おそらくこれが正解。
・仮定3：剰余取得方式
0～n+1を生成するのに「r % n」みたいなことをする方式。
使用例）
HGSSの性格（r % 25）
第7世代
仮定2がダメだった場合に試す予定だった方式。
今回は出番なし。
とりあえず乱数消費に使えそうなペラップの音程について調べてみましょう。
割合取得方式の場合、8192通りを4区間に等分した場合、単純に4通り取得する場合と同じになります。
個体値決定後に謎の消費が30程度ありましたが、ペラップ1回で乱数消費1つと仮定して矛盾は観測されませんでした。
個体値決定後の謎の消費の数はどうやら固定ではないようです。
ポケモンの個体、あるいはペラップの音程でも必要数の情報があれば乱数位置の推定ができます。
あとはペラップで位置調整が1つ単位でできるので、適宜調整しましょう。
とりあえず当たりが出そうな自動販売機の当たりを狙ってみます。
本当は3.で確認してからやるべきだけれど、3.でも実調整はすることになるし、うん。
第5世代なんかでは1/32の確率で当たるらしいので、
まずは乱数値を0～31化したうちの0が出るようペラップで調整してみます。
という訳で勝利条件を1つ達成しました。
流れとしてはこんな感じになります。
それを知るには少し情報が足りてなさそうなので、また少し適当に遊んでみます。
何か出ました。
どうやら持ち物があると所持金が増えそうです。
再度3.と4.を行います。
持ち物は（おそらく）ポケモン依存となるので、出現ポケモンと持ち物判定の両方を調べる必要がありそうです。
これを行うことで調べるべき範囲が制限され、考えやすくなります。
という訳で、まずは出現ポケモンから。
きっとどこかのエンカウントテーブルを流用しているだろうとの希望的観測から、
既存のエンカウントテーブルを調べたところHGSSにそれっぽいのがありました。
とりあえずこれを仮定しましょう。
これと乱数値から作った表と、実際の観測データを照らし合わせてみます。
あとは持ち物ですね。
調べてみると、どうやらベトベターはきんのたまを5%の確率で持っているらしいですね。
という訳で、さっきの表を見てみましょう。
おそらく0～4の時に持っていそうですね。
位置8も可能性としてはありそうですが、実はそこは性格に割り当てられています。
今更ですが、基本的に複数データと照らし合わせるのが望ましいです。
（説明上観測データは1つしか出していませんが。）
ちなみに、実際のポケモンでは持ち物判定はこんな感じになっています。
第4世代：http://2style.jp/bowline/ds/research/wild_item.txt
第5世代：BW野生ポケモンの持ち物について
では、所持金を増やしてみましょう。
勝利条件の2つ目、達成です！
いかがでしたでしょうか。
今回は勝利条件を満たすために必要な内容のみを少し大雑把に見ましたが、
更にきっちりと解析する場合、閾値検証等も行うことになります。
また、消費内訳にも不明点（特に不定消費）が残っていますが、
これらの解析も同じような流れで行うことになるかと思います。
ちなみに、この方法で導いた結論は必ずしも正しいとは限りません。
（観測されていない事象に反例がある可能性があります。）
あ、プログラム自体の解析は私の管轄外ですので悪しからず。
（解析する別解はこちら→http://d.hatena.ne.jp/oupo/20171209/1512767116）
では、ここまで読んでくれた方が次回作の解析をしてくれると信じて。
私は隠居します。
10日目はカレンダー作成者の@mizdraさんの担当です！
他の記事も面白いので読んでみましょう。そして参加しましょう。
先週@Blastoise_Xさんによりある問いが出されました。
乱数調整で遊ぼう - ろいしんぶろぐ
というわけで
以下、ネタバレ注意。
では解いていきましょう。
0.遊ぶ
まずは仕組みの推測…の前に何ができるかをざっと見てみましょう。
3種類くらい行動があるらしい。
自動販売機だ。
当たりが出そう。
ペラップ～♪
音程は4通り観測できた。
何か捕まえた。
1.方針決定
何ができるか一通り見たところで、まずは方針を決めます。必要な情報は以下の2つ。
・乱数列
・乱数使用方法
どちらも事前情報がなく、片方だけを先に特定するのも無理そうなので、
両方を仮定して観測された事象を説明できたらOK、という考え方でいきましょう。
対象とする事象は、まずは考えやすいものにします。
0.で観測された事象のうち、情報が得られたのは以下の2つ。
・ペラップの音程
処理がそのままであれば、8192通りの音程を4つに分けているものと思われる。
「8192通り」の数字を変えられると場合によっては特定が面倒になる。
・出現ポケモン
他の情報は後回しとし、個体値だけを考えると非常に単純で情報量も多い。
今回は後者の「出現ポケモン」の個体値情報から考えることにしました。
2.仮定
虱潰しのお時間です。「乱数列」「乱数決定方法」の仮定を、複数の観測データを説明できるまで行います。
説明できればきっとその仮定は正解です。
どうしても上手くいかない場合は1に戻ってみるのもいいでしょう。
まずは「乱数列」の仮定から。
おそらくはポケモンで使用されている乱数列だと当たりをつけました。
某世代みたいに説明書に書いてあると推測しやすくなるのでとてもいいです。
ポケモンでよく使われる乱数列は以下の通り。
・LCG（32bit）
普通に全検索できる
「s[n+1] = s[n] + 0x41c64e6d + 0x6073」の形がよく使われている。
使用例）
第3世代
第4世代
・LCG（64bit）
全検索したい？スパコン使ってね！
「s[n+1]=s[n] * 0x5d588b656c078965 + 0x269ec3」の形が使われている。
使用例）
第5世代（性格値乱数列）
・MT
初期シード32bitならなんとかなる、けど計算が少し大変
使用例）
第4世代（孵化乱数列）
第5世代（個体値乱数列）
第6世代
・TinyMT
初期シード32bitならなんとかなる、けど計算が少し大変
使用例）
第7世代（孵化乱数列）
・SFMT
初期シード32bitならなんとかなる、けど計算が少し大変
使用例）
第7世代
難易度的にはLCG（32bit）が無難なので、とりあえずそれの良く使われている形を仮定しましょう。
乱数値も上位16bitを使っているので、そのように仮定します。
次は「乱数決定方法」の仮定。
今回は、主にこっちの仮定が中心です。
こちらもポケモンで使われている方法から考えます。
・仮定1：第4世代方式
6つの個体値を2つの乱数を使って決定。
1つ目の乱数でHABを下から5bitずつ、2つ目の乱数でSCDを下から5bitずつを使って決定する。
2連続で遭遇したポケモンの個体値を入力して検索するも、
2つが近い位置に見つからなかったためハズレ。
・仮定2：割合取得方式
0～n-1を生成するのに「r * n / (rmax + 1)」みたいなことをする方式。
使用例）
DPtの性格（r / 0xa3eで0～24取得）
第5世代（参考：BW出現スロット等の閾値検証）
第6世代
第5世代以降のHABCDSの順に決定する方式で計算してみた。
試した事象全てで連続2個体の間の消費数が30前後になったので、おそらくこれが正解。
| 位置 | 乱数 | 個体値 | 備考 |
|---|---|---|---|
| 0 | 8EF97E97 | 17 | オニドリル Lv.27 性格：がんばりや 個体値：17-4-5-30-25-0 |
| 1 | 249748BE | 4 | |
| 2 | 2D883D59 | 5 | |
| 3 | F1899D58 | 30 | |
| 4 | CF992EEB | 25 | |
| 5 | 0546F482 | 0 | |
| … | … | … | |
| 34 | 0C998BF9 | 1 | ベトベター Lv.28 性格：せっかち 個体値：1-20-23-26-31-11 |
| 35 | A19CD778 | 20 | |
| 36 | B83EAE8B | 23 | |
| 37 | D6610BA2 | 26 | |
| 38 | FA29B06D | 31 | |
| 39 | 58CFB4DC | 11 |
・仮定3：剰余取得方式
0～n+1を生成するのに「r % n」みたいなことをする方式。
使用例）
HGSSの性格（r % 25）
第7世代
仮定2がダメだった場合に試す予定だった方式。
今回は出番なし。
3.その他スキーム解析
ここまでで基本的な仕組みが推測できたので、その情報を基に他の情報の決定方法を考えます。とりあえず乱数消費に使えそうなペラップの音程について調べてみましょう。
割合取得方式の場合、8192通りを4区間に等分した場合、単純に4通り取得する場合と同じになります。
個体値決定後に謎の消費が30程度ありましたが、ペラップ1回で乱数消費1つと仮定して矛盾は観測されませんでした。
個体値決定後の謎の消費の数はどうやら固定ではないようです。
| 位置 | 乱数 | 個体値 | 備考 |
|---|---|---|---|
| 0 | 8EF97E97 | 17 | オニドリル Lv.27 性格：がんばりや 個体値：17-4-5-30-25-0 |
| 1 | 249748BE | 4 | |
| 2 | 2D883D59 | 5 | |
| 3 | F1899D58 | 30 | |
| 4 | CF992EEB | 25 | |
| 5 | 0546F482 | 0 | |
| … | … | … | |
| 34 | 0C998BF9 | 1 | ベトベター Lv.28 性格：せっかち 個体値：1-20-23-26-31-11 |
| 35 | A19CD778 | 20 | |
| 36 | B83EAE8B | 23 | |
| 37 | D6610BA2 | 26 | |
| 38 | FA29B06D | 31 | |
| 39 | 58CFB4DC | 11 | |
| … | … | … | |
| 70 | 508A190D | ペラップ（ちょっと低い） | |
| 71 | 0B7D00FC | ペラップ（低い） | |
| 72 | B96E93BF | ペラップ（ちょっと高い） | |
| 73 | 69D37AC6 | ペラップ（ちょっと低い） | |
| 74 | B997FAC1 | ペラップ（ちょっと高い） | |
| 75 | 4662F2A0 | ペラップ（ちょっと低い） | |
| 76 | 65CE6E93 | ペラップ（ちょっと低い） | |
| 77 | 17483F0A | ペラップ（低い） | |
| 78 | 38B443B5 | ペラップ（低い） | |
| 79 | 64605A84 | ペラップ（ちょっと低い） |
4.実調整
実際にやってみましょう。ポケモンの個体、あるいはペラップの音程でも必要数の情報があれば乱数位置の推定ができます。
あとはペラップで位置調整が1つ単位でできるので、適宜調整しましょう。
とりあえず当たりが出そうな自動販売機の当たりを狙ってみます。
第5世代なんかでは1/32の確率で当たるらしいので、
まずは乱数値を0～31化したうちの0が出るようペラップで調整してみます。
| 位置 | 乱数 | 0～31 | 備考 |
|---|---|---|---|
| 97 | B48D281E | 22 | ペラップ（ちょっと高い） |
| 98 | 87879939 | 16 | ペラップ（ちょっと高い） |
| 99 | 0081FBB8 | 0 | 当たりそう |
という訳で勝利条件を1つ達成しました。
流れとしてはこんな感じになります。
0.再度遊ぶ
さて、もう1つの勝利条件は何でしょうか。それを知るには少し情報が足りてなさそうなので、また少し適当に遊んでみます。
何か出ました。
どうやら持ち物があると所持金が増えそうです。
再度3.と4.を行います。
持ち物は（おそらく）ポケモン依存となるので、出現ポケモンと持ち物判定の両方を調べる必要がありそうです。
3.再度解析・実調整
これらを調べる前に、乱数位置を特定できるペラップの音程を使って出現ポケモン生成に関する乱数使用範囲を調べます。これを行うことで調べるべき範囲が制限され、考えやすくなります。
| 位置 | 乱数 | 個体値 | 備考 |
|---|---|---|---|
| -4 | CFD5EA6F | ペラップ（高い） | |
| -3 | 2C5D03B6 | ペラップ（低い） | |
| -2 | 4F8068F1 | ペラップ（ちょっと低い） | |
| -1 | 550C7D10 | ペラップ（ちょっと低い） | |
| 0 | CECC8043 | ||
| 1 | 92F966FA | 18 | オニドリル Lv.29 性格：ゆうかん 個体値：18-22-26-21-16-31 |
| 2 | B0ED64E5 | 22 | |
| 3 | D7F01BF4 | 26 | |
| 4 | AC789F57 | 21 | |
| 5 | 8432BA7E | 16 | |
| 6 | F9E02C19 | 31 | |
| … | … | … | |
| 36 | 5106C4F7 | ペラップ（ちょっと低い） | |
| 37 | 9DEF7F9E | ペラップ（ちょっと高い） | |
| 38 | 0A0FDAB9 | ペラップ（低い） | |
| 39 | 417ADF38 | ペラップ（ちょっと低い） | |
| 40 | 2EA47B4B | ペラップ（低い） | |
| 41 | 609BB962 | ペラップ（ちょっと低い） |
という訳で、まずは出現ポケモンから。
きっとどこかのエンカウントテーブルを流用しているだろうとの希望的観測から、
既存のエンカウントテーブルを調べたところHGSSにそれっぽいのがありました。
| 確率 | 出現ポケモン |
|---|---|
| 20% | ベトベターLv.26 |
| 20% | オニドリルLv.27 |
| 10% | ベトベターLv.26 |
| 10% | オニドリルLv.27 |
| 10% | ベトベターLv.28 |
| 10% | ベトベターLv.28 |
| 5% | オニドリルLv.29 |
| 5% | オニドリルLv.29 |
| 4% | マグマッグLv.27 |
| 4% | ベトベトンLv.30 |
| 1% | マグマッグLv.27 |
| 1% | ベトベトンLv.30 |
とりあえずこれを仮定しましょう。
これと乱数値から作った表と、実際の観測データを照らし合わせてみます。
| 位置 | 乱数 | 個体値 | 百分率 | 備考 |
|---|---|---|---|---|
| 0 | CECC8043 | 77 | ベトベター Lv.28 | |
| 1 | FE4B3E51 | 31 | 性格：きまぐれ 個体値：31-30-9-9-5-27 きんのたま持ち | |
| 2 | F6AC96F0 | 30 | ||
| 3 | 4B19C4A3 | 9 | ||
| 4 | 4CF4C3DA | 9 | ||
| 5 | 2C803045 | 5 | ||
| 6 | DBA7F3D4 | 27 | ||
| … | … | … | … | |
| 31 | CFD5EA6F | ペラップ（高い） | ||
| 32 | 2C5D03B6 | ペラップ（低い） | ||
| 33 | 4F8068F1 | ペラップ（ちょっと低い） | ||
| 34 | 550C7D10 | ペラップ（ちょっと低い） | ||
| 35 | CECC8043 | 80 | オニドリル Lv.29 | |
| 36 | 92F966FA | 18 | 性格：ゆうかん 個体値：18-22-26-21-16-31 | |
| 37 | B0ED64E5 | 22 | ||
| 38 | D7F01BF4 | 26 | ||
| 39 | AC789F57 | 21 | ||
| 40 | 8432BA7E | 16 | ||
| 41 | F9E02C19 | 31 |
あとは持ち物ですね。
調べてみると、どうやらベトベターはきんのたまを5%の確率で持っているらしいですね。
という訳で、さっきの表を見てみましょう。
| 位置 | 乱数 | 個体値 | 百分率 | 備考 |
|---|---|---|---|---|
| 0 | CECC8043 | 77 | ベトベター Lv.28 | |
| 1 | FE4B3E51 | 31 | 性格：きまぐれ 個体値：31-30-9-9-5-27 | |
| 2 | F6AC96F0 | 30 | ||
| 3 | 4B19C4A3 | 9 | ||
| 4 | 4CF4C3DA | 9 | ||
| 5 | 2C803045 | 5 | ||
| 6 | DBA7F3D4 | 27 | ||
| 7 | 1CC5C9B7 | 11 | ？ | |
| 8 | FE37055E | 99 | ？ | |
| 9 | 05C44D79 | 2 | 持ち物（5%） |
おそらく0～4の時に持っていそうですね。
今更ですが、基本的に複数データと照らし合わせるのが望ましいです。
（説明上観測データは1つしか出していませんが。）
ちなみに、実際のポケモンでは持ち物判定はこんな感じになっています。
第4世代：http://2style.jp/bowline/ds/research/wild_item.txt
第5世代：BW野生ポケモンの持ち物について
では、所持金を増やしてみましょう。
| 位置 | 乱数 | 個体値 | 百分率 | 備考 |
|---|---|---|---|---|
| 164 | EFFC937A | ペラップ（高い） | ||
| 165 | 2DD65765 | ペラップ（低い） | ||
| 166 | 10025C74 | 6 | ベトベター Lv.26 | |
| 167 | 7EE515D7 | 15 | 性格：いじっぱり 個体値：15-9-16-14-21-10 | |
| 168 | 4F7C2EFE | 9 | ||
| 169 | 84A5C699 | 16 | ||
| 170 | 706E8D98 | 14 | ||
| 171 | A9C6FA2B | 21 | ||
| 172 | 5233FEC2 | 10 | ||
| 173 | 23CEF50D | |||
| 174 | 22D6ACFC | |||
| 175 | 0504CFBF | 1 | 持ってそう |
勝利条件の2つ目、達成です！
いかがでしたでしょうか。
今回は勝利条件を満たすために必要な内容のみを少し大雑把に見ましたが、
更にきっちりと解析する場合、閾値検証等も行うことになります。
また、消費内訳にも不明点（特に不定消費）が残っていますが、
これらの解析も同じような流れで行うことになるかと思います。
ちなみに、この方法で導いた結論は必ずしも正しいとは限りません。
（観測されていない事象に反例がある可能性があります。）
あ、プログラム自体の解析は私の管轄外ですので悪しからず。
（解析する別解はこちら→http://d.hatena.ne.jp/oupo/20171209/1512767116）
では、ここまで読んでくれた方が次回作の解析をしてくれると信じて。
私は隠居します。
10日目はカレンダー作成者の@mizdraさんの担当です！
