# 真・女神転生 疑似乱数アルゴリズム

ここでは真・女神転生(SFC版)の疑似乱数生成アルゴリズムについての解説と, 先駆者によって示唆されていた, 既存の手法とは異なるアプローチでの乱数調整手法について紹介します.

文末に参考文献を記載してあるのでそちらもご参照ください.

(以前 GitHub.io上で公開していた記事のアーカイブです)

## 疑似乱数アルゴリズム
ゲーム上でのランダムな事象(命中判定, 回復量, 敵の行動, レアな敵の出現判定etc)を生成するためには, 疑似乱数を生成する必要があります.
この疑似乱数を生成するアルゴリズムは, ゲームによって様々ではありますが, 一部のゲームでは生成される乱数の質が良くないアルゴリズムを採用していたり, その実装がずさんなため, 所謂"乱数調整"が可能となってしまっています.

真・女神転生(SFC版)では, 線形帰還フィードバックレジスタ(LRFR)と繰り上がり加算を組み合わせることで, 0から255までの範囲の疑似乱数を生成しています.

高級言語ではなじみのない言葉も多々出てくるので合わせて解説します.

> 乱数計算に関係するメモリは現在乱数１バイト、計算に使われる内部変数が３バイト。
以下三つの内部変数を仮に[A][B][C]とする。hは数値が16進数である事を表す。
アキュームレータは計算結果を一時保存する領域の事。
>
> [A]をキャリー付き左シフト。
> [B]の1ビット目と2ビット目をXORして反転した値を[A]に加算。
> [B]をキャリー付き左ローテート。
> アキュームレータに[B]をロードして22hをキャリー付き加算。
> アキュームレータに[A]をキャリー付き加算。
> アキュームレータに5AhをXOR。
> [C]にアキュームレータの値をキャリー付き加算。
> 現在乱数に[C]をXOR
[Megami Tensei Labo 真・女神転生乱数調査室#基本的な仕組み](https://smtlab.web.fc2.com/rng.html#mechanism)

:::info
**メモ**
キャリーフラグ(キャリー)carryとは, キャリー付き加算(所謂繰り上がり加算), キャリー付き左シフトなどでの桁あふれ時に立つ, 1bitからなるフラグです.

フラグには,
- キャリー付き加算を実行したときの最上位ビットでの繰り上がりビット
- シフト演算時に溢れるビット

が代入されます.
このフラグが立っているとき,

- 加算を実行すると加算演算後に+1を行います.
- 左(右)ローテート命令を実行すると, 最下位(最上位)ビットに1を埋め込みます.
:::

## アルゴリズムの概説
内部変数`A` , `B` , `carry` をひとまとめ(`carry|B|A`)に17bitとして扱っていると考えると, この部分は線形帰還フィードバックレジスタになっています. これらの変数は長さ17bitのランダムビット列を生成します.

内部変数`C`は乱数生成を行うための内部状態を保持しています. `A`, `B`, 及び`carry`の値をアキュムレータで加工して, `C`に加算していくことで内部状態を更新します.

初期乱数`Rnd`は, VC版(SwitchOnline版)の場合は`0`で固定です. `C`と`Rnd`の排他的論理和(xor)を取ることで乱数列の更新を行います.

## アルゴリズムの性質
このアルゴリズムで生成される乱数列の長さは 113999個となります. 現代のコンピュータの処理性能をもってすれば容易く全探索が可能です.

一般に, 周期$L$の乱数生成器から乱数列状の現在位置を特定するには$log_2 L$ [bit] の情報量が必要です. $\log_2 113999≈16.8$より, ゲーム上で得られる$17$ bitの情報から乱数列上の現在位置が特定できそうですね.

そこで, 乱数生成器が連続して出力する乱数から現在位置を特定することを考えます.

## 実際の特定手法
[Shin Megami Tensei Labo 真・女神転生乱数調査室](https://smtlab.web.fc2.com/rng.html) では, 私たちが観測できる乱数列の例として, 回復魔法による回復量, 蘇生魔法の失敗判定, おみくじの結果といったものが挙げられていました.

この中で, おみくじの結果は容易に観測でき, かつ最上位ビットの情報を含んだ判定を行っているため, 乱数位置の特定に利用することが出来ます.

おみくじの判定は次のように行われています. おみくじを使った際, その時の乱数値の上位4bitを16進数で表したものをrとすると, 以下の条件で結果が変動します.

- `r==0x0` : 全回復
- `0x1<=r && r<=0x4` : HPがレベル分だけ回復
- `0x5<=r && r<=0xA` : 何も起きない
- `0xB<=r && r<=0xE` : HP1/4
- `x==0xF` : HP,MP1/8

(参考):[Shin Megami Tensei Labo 真・女神転生乱数調査室 #各種乱数判定の内容](https://smtlab.web.fc2.com/rng.html#various)

これらすべての条件を観測するのは容易ではありません. 例えば, HPが満タンのときにおみくじを使った際は, 全回復とレベル分の回復を区別することが出来ません. ("しかしこうかがなかった"というメッセージは出る)

そこで, 上記の判定を次のように纏めてしまいましょう.

- `0x0<=x && x<=0x4` :HP回復(しかしこうかがなかった)
- `0x5<=x && x<=0xA` :何も起きない
- `0xB<=x && x<=0xF` :HP減少

おみくじの結果を上記の3つのみに区別したとしても, 問題なく乱数列を特定することが出来ます. 観測できる情報量は, $log_2 3 \approx 1.585$ bitですから, 概ね11～12個のおみくじから, 乱数列上の位置を特定するのに十分な情報が得られることになります.

具体的な手順としては, 上記のアルゴリズムで生成される乱数列を上記で述べたおみくじの結果に変換したものから, 観測できたおみくじの結果の並びを全探索すれば良いでしょう. 考えられる場合の数は高々20万通りにも満たないわけですから, スマートフォンでも容易に検索可能です.

## 乱数調整への応用

### 乱数調整クイズ
ここでクイズのお時間です. 魔人との遭遇確率は一般に1/256と言われていますが, ビッグフットとの遭遇確率は何分の1でしょうか?

この問いに答えるには, そもそも魔人やビッグフットといったレアエネミーにエンカウントするための条件を知る必要があります.

これらの条件は乱数値を調べることで見つけることが出来ます. 実は固定敵部屋に進入した際には, 魔人との遭遇判定に1つ, 種別判定に1つで, 合わせて乱数が2つ消費されています.

1つ目の乱数では, 乱数値が0x00のときに魔人と遭遇することが確定します. 2つ目の乱数では, 1つ目で魔人遭遇が確定しているなら, 遭遇する魔人の種類を決定します. そうでない場合は, 上位4ビットが0x0の時, レアエンカウントが確定します. 従って先ほどのビックフットの質問の答えは1/16となります.

こうした調査をもとに先述の乱数の仕組みを悪用することで, 所謂乱数調整を行うことが出来ます.

### 既知の手法
既存の手法では, ゲーム開始直後の操作の固定化によって乱数消費を制御することで, 魔人との遭遇などの確率の低い事象を引き起こしていました.

確かに誰でも出来る方法ではありますが, 月齢を合わせる手間があったり, 複雑かつ失敗したら即リセットのややシビアな移動操作制御が求められます.

### 提案手法
ビッグフット討伐RTAにて用いた手法では, 先述の方法で乱数位置を特定し, ツールによってレアエンカウント(上位ビットが0x0の乱数値)までに必要な消費数を計算して, その数だけおみくじや回復魔法によって乱数消費を行っています. もし魔人との遭遇を目標にするのであれば, 魔人遭遇判定時に乱数値が0x00となるまで消費を行えばよいです.

この方法ならば, 操作精度や月齢の条件を気にすることなく目的の敵と遭遇することが出来ます. 但し, 戦闘中の乱数については別途乱数調整が必要になるため, この方法のみを用いてストラディバリを入手するのは難度が高いです.

また, 乱数を消費するために大量のおみくじが要求されます. 魔人と遭遇することを目的とする場合は該当する乱数の出現頻度が低いがために, 歩行などによる乱数消費で仕切りなおしをするなどの工夫が必要になります. このように, 既存の方法より大きく劣る部分も多いです.

既存の真・女神転生での手法とは異なるアプローチでの乱数調整ではありますが, 操作精度や月齢の条件に依ることなく魔人やビッグフットの討伐が可能です. ぜひ一度お試しいただければ幸いです.

## リファレンス
以下にこの文書を書く上で参考にしたページ, 動画を載せておきます.

### ウェブページ
[真・女神転生 攻略情報局](https://smtlab.web.fc2.com/index.html)
乱数調整にかかわる情報が多く載っているため, 記事を書く上で大変参考になりました.

とりわけ乱数生成アルゴリズムの説明が無ければ, そもそも乱数調整ツールを開発することもなかったと思います.