乱数調整

レイド乱数探索アルゴリズムの改良

Pokémon RNG Advent Calendar 2020の19日目の記事です。
他の記事も面白いので読んでみましょう。そして参加しましょう。


SWSHのレイド乱数探索アルゴリズムの発見は、個体決定方法において逆算時の課題となっていた再計算処理の考慮を別で考えることにより、現実的な時間でのシード計算を可能とした。
今回は、それ以来ほぼ全てのツールにそのまま実装されているであろう、このアルゴリズムの改良を行った。
元のアルゴリズムの解説はこちら→https://oupo.hatenadiary.com/entry/2019/12/22/194820


●元のアルゴリズムの問題点
ゲーム内から分かる情報(以下観測値、m bit)と虱潰しする値(n bit)から線形写像に用いる値を計算するのだが、
この計算処理は加算処理を行うため線形ではない
そのため、m+n>64となる場合でも64bitを超過する情報をそのままでは扱えないため、探索範囲は最低でも32bitが必要となる。

●改良した点
64bitを超過する分を含む一部情報を線形写像で扱えるようにし、32bit未満の探索範囲で検索できるようにした。
一部情報は、観測値のうち、以下のいずれかに該当するもの。
ただし、加算対象に定数が含まれるECは除く。

1. 下位bitから1が連続している範囲
 加算後の値が下位bitから1が連続していれば、その範囲での加算処理は線形となる。
 観測結果によって該当するかが変わる。

2. 最上位bit
 観測結果に関わらず、観測値の各最上位bitは線形写像に組み込むことができる。
 詳しくは後述。

最大でこれらのbit数まで、超過bit分の探索範囲を減らすことができる。

●改良アルゴリズム詳細
観測値bit列$v$、探索値bit列$s$とそれに対応する加算値bit列$t$とする。
$$v=s+t$$それぞれを一部情報に対応するbit列$v_1$、$s_1$、$t_1$と残りのbit列$v_0$、$s_0$、$t_0$に分割すると、
$s_0$、$t_0$に依存する値$c$(下位1連続bitは0、最上位bitは加算時繰り上がり値)を用いて
$$\begin{cases}v_1=s_1+t_1+c \cdots(*)\\v_0=s_0+t_0\end{cases}$$と書ける。
$s_0$を固定すると$c$を固定値として扱えるので、$(*)$と解の存在条件から$s_1$の絞り込みが可能で、
かつ線形であるため逆算が容易である
結果、探索範囲は$s_0$と絞り込み後の$s_1$の組み合わせ範囲だけで済む。


細かい計算は面倒なので省略。
64bit超過は2V6連等、元々条件が厳しくないと達成はできませんが、
条件さえ十分にあればCPU計算でも一瞬で計算が終わる程度まで高速化が可能です。

何故これの解説を今頃になって書くのか。
あ、私の遥か昔の配布ツールにはこのアルゴリズムは未実装です。
他にもいろいろ対応してないから使わなくていいよ。多分もう更新もしないよ。

某ツールには実装されてると思います。多分。

第5世代で乱数消費しないと出ない個体値とか

Pokémon RNG Advent Calendar 2018の16日目の記事です。
他の記事も面白いので読んでみましょう。そして参加しましょう。


以前この記事で書いたように、第5世代の個体値乱数列は消費数を固定するとかなり偏りが生じる。
という訳で調べたいなと思いつつ数年間放置していたものを計算してみた。

●BW標準(消費0)

初期シード数該当する個体値数個体値割合
0196664321.8315792084%
1786614267.3259161785%
215733367214.6528400481%
320977559519.5368747227%
420978141319.5374165662%
516781366115.6288650818%
611187128710.4188255034%
7639317115.9541045688%
8319663572.9770989902%
9142059821.3230351731%
1056816450.5291444249%
1120683500.1926301047%
126909190.0643468462%
132112460.0196738169%
14606720.0056505203%
15163300.0015208498%
1639570.0003685243%
179140.0000851229%
181950.0000181608%
19550.0000051223%
2030.0000002794%
2120.0000001863%

一番出やすい個体値
個体値初期シード
13-21-19-0-29-80D47C6EB
21692601
27F6C9AE
2F8C5F2D
4864728B
56D969FA
705D4B0F
746297CC
826BFFC8
82F4F645
AB5C4B64
B77EE5AA
C4D1CCD0
C7213D8F
CE2A9A0A
D8D4740E
DE7392FB
E1AEC42C
EF100FEF
EF16D855
FF19B490
22-15-11-14-22-221043FB8F
113D7CCD
15E1DDA7
16614F93
2BDD61E2
37EFDC23
3ED85316
42F6F3A4
452841A5
46B5A48C
6AC7DE4A
920F8E96
93EAD559
96D433C7
B8B0F47F
BAD96E29
D05AE435
DECE4121
E091361A
E5D4CDF6
FCDE8457


●BW2(消費2)

初期シード数該当する個体値数個体値割合
0196662851.8315655179%
1786764287.3273133487%
215732019014.6515844390%
320977542219.5368586108%
420975645619.5350922644%
516782335315.6297677197%
611188631610.4202251881%
7639328345.9542091563%
8319715172.9775795527%
9142015731.3226245530%
1056840880.5293719471%
1120651320.1923304051%
126889760.0641658902%
132113760.0196859241%
14603840.0056236982%
15161740.0015063211%
1641020.0003820285%
179540.0000888482%
182010.0000187196%
19450.0000041910%
20140.0000013039%
2130.0000002794%
2210.0000000931%

一番出やすい個体値
個体値初期シード
25-4-31-10-9-90DEB3601
23366D91
3AC6AB42
3D303D68
44E519EF
4CAB1A0A
5B0BA705
606BAAE3
61819D13
77B0920F
8996B8E0
8BAE11CC
8D9A6FB2
90ECD601
9EFFA228
A4CA7152
A9930A85
BD61DA65
C1580C0B
D2048E96
F0A21798
F393592A


という訳で、1.83%くらい消費しないと出現しない個体値があります。
$(1-\frac{1}{32^{6}})^{2^{32}}$がだいたいそれくらいなので、多分計算合ってます。合ってるといいな。
6V等はちゃんと出るので、そこは一安心ですね。
誰か出ない個体値を検索してた人とかいるのかな…。

偏り怖い…。

ピカチュウのお城攻略(動画)

Pokémon RNG Advent Calendar 2017の22日目の記事です。
他の記事も面白いので読んでみましょう。そして参加しましょう。


HGSSのバトルキャッスル乱数動画です。



仕組みはバトルファクトリー独自の要素を除いてほぼ同じ。
バトルファクトリーまとめ - oupoの日記

違う箇所は以下。
・1戦ごとの乱数消費は12で固定
・コクランの手持ちは1戦目、2戦目ともに個体値All31

という訳で、以下動画で使用したデータとか。
続きを読む

乱数調整で遊ぼう解答

Pokémon RNG Advent Calendar 2017の9日目の記事です。
他の記事も面白いので読んでみましょう。そして参加しましょう。


先週@Blastoise_Xさんによりある問いが出されました。
乱数調整で遊ぼう - ろいしんぶろぐ

というわけで3時間で解いてみたのでその解答・解説です。
以下、ネタバレ注意。
続きを読む

XY・ORAS固定乱数仕組み

6世代でも固定シンボル乱数に成功しました。


というわけで仕組みとか。
検証中の部分が多いので、常に最新の情報に注意してください。


●仕組み

・乱数列
個体決定に使用する乱数列は5世代まででも使用していたMT。
起動する度に初期シード32bitを決定し乱数列を生成する。
フィールド上ではおおよそ60消費/秒で進み、ステータス画面等でも同様に進む。
スリープにすればさすがに止まりそう。(精度よく止められる気はしないので未確認)
乱数値は剰余ではなく5世代同様、商を用いる形式となっている。
(サンムーンでは剰余を使用)
5世代参考→http://blog.livedoor.jp/x_x_saki_x_x/archives/53962575.html

・初期シード
本体とセーブデータに依存する値にミリ秒を足した値のよう。
セーブし直さずに同じ本体で2回起動すれば、初期シードの差はおおよそ起動時間ミリ秒の差になる。
そのため同じセーブデータを使用すれば、サンムーンと異なり初期シードの範囲を絞り込むことが可能。(ソフトリセットでもOK)
初期シードはタイトル画面でのAボタンを契機として決定されると思われる。
(XYで待機時間を変更して確認、ORASは正確には未検証)
ちなみに本体の時間を変えても関係なく初期シードが変わったので、変えるだけ無駄です。
(本体初期化での挙動は未確認)

・個体決定方法
基本的にサンムーンと同じと考えられる。
3V確定の固定シンボルの場合、
 EC→PID→V箇所→残り個体値→性格
という順であった。
(複数特性ある場合等諸々未確認)


●乱数調整方法検討

現時点で乱数列の確認方法は出現個体の確認しか見つかっていない。
また、出現個体の消費数も毎度1/60秒を合わせられる訳ではないので、多少の幅が出てくる。
そして、野性ポケモンを出現させてわざわざ個体値を完全に特定したとしても、情報量的に32bit全探索の場合は初期シードを完全に特定できるとは限らず、基本的に2匹以上の個体値特定を行うこととなる。
そのため、毎度32bitの初期シードから全探索を行うのは相応の労力が必要となる。
そこで、本体とセーブデータを固定した場合の性質を利用する。

一度起動時刻をメモし、野生ポケモンの個体から初期シードを特定する。
すると、同じ本体とセーブデータを使用する限り起動時刻からおおよその初期シードの値を推定することができる。
その後、捕獲の必要のある初期シードの確認有無で2通りの方法が考えられるので、それぞれのメリットデメリットを挙げてみる。

1.初期シード確認を行わない場合
・メリット
事前に待機時間を計算することになるので、待機時間の管理が楽。
毎度ポケモンを捕獲する必要がない。
・デメリット
試行回数を減らすには起動時刻のミリ秒単位の時間の管理と相応の精度が必要。
(1/60秒の精度が出せたとしても初期シード候補は16-17程度になる)

2.初期シード確認を行う場合
・メリット
待機時間の管理さえできれば調整が比較的容易。
・デメリット
毎度ポケモンを捕獲して初期シードを特定する必要がある。
乱数消費を止めないと目標個体検索中も乱数消費が進むので、待機時間の管理が難しい。

どちらも試してみたが、1.は初期シードを安定しなかったので2.の方で調整することとした。


●やってみた

というわけで、以下実際に固定シンボル乱数を行った手順。
完了までセーブを行わず、同じ本体で実施。

0.準備
以下の作業を行いやすい場所でセーブする。
起動時刻をメモして起動し直し、野性ポケモン2匹を捕獲する。
捕獲したポケモンの個体値から初期シードを32bit全探索し、初期シードを特定する。

以下ループ。

1.初期シード特定
起動時刻をメモして起動し、野性ポケモンを捕獲する。
捕獲したポケモンの個体値から初期シードを検索し、初期シードを特定する。
(高Lvのポケモンであれば1匹でもそのままのステータスだけで特定が可能)

2.個体検索
特定した初期シードから目的の個体を検索する。
検索結果と経過時間から残りの待機時間を計算する。

3.乱数調整
計算した待機時間待機し、ポケモンを出現させる。


●その他

操作統一前は消費数が安定しなかったので、何かしらの操作をすると一時的に消費数が変わるのかもしれない。(未検証)

ループ時の初期シード特定だが、野生ポケモンのLvが低い場合個体値測定にPSSの対戦をするという方法もある。
その場合、通信を切断して終了すると消費数が安定しなかったので、面倒でも降参して終わらせることを推奨する。
また、Lvが低すぎなければ2匹捕まえるという手段もある。
その場合、予め2回ともタイミングを決めておくと初期シード候補の絞り込みがやりやすいかと。
ちなみにタイミングを合わせる場合、水上であまいかおりを使うとよい。
(草むらで使うと群れが出てくるクソ仕様乱数調整しかしないので努力値振りは知りません!


スリープ中に乱数消費が止まるのであれば、起動から一定時間後にスリープして検索諸々を行えば待機時間管理自体はやりやすそう。
(どの程度精度が安定するかは知らない)
サンムーンのQR針的な存在があればいいんだけどね。
 
プロフィール
さき

ポケモンの乱数調整とかツールとか。サンムーン乱数調整できました。
Twitter→@water_blow

広告
最新コメント
記事検索