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計算でも一瞬で計算が終わる程度まで高速化が可能です。
何故これの解説を今頃になって書くのか。
あ、私の遥か昔の配布ツールにはこのアルゴリズムは未実装です。
他にもいろいろ対応してないから使わなくていいよ。多分もう更新もしないよ。
某ツールには実装されてると思います。多分。
他の記事も面白いので読んでみましょう。そして参加しましょう。
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計算でも一瞬で計算が終わる程度まで高速化が可能です。
pattirudonアルゴリズムの上位互換アルゴリズムを見つけた
— さき@隠居 (@water_blow) February 14, 2020
(画像はi7-8700で2V6連再計算0-1を計算した結果) pic.twitter.com/5xcWf7Ukl1
あ、私の
某ツールには実装されてると思います。