SFC版風来のシレンの乱数生成アルゴリズムの話 解析編

#SFC版風来のシレンの乱数について
私はローグライクゲーム好きなのでローグライク系ゲームの動画をニコニコ動画等でたまに見たりします。中でも、SFC版の初代風来のシレンはもう20年以上も前のゲームですが、完成されたゲームシステムと絶妙なゲームバランスにより、今なお根強い人気があります。
さて、そのSFC版風来のシレンの動画を見ていると、たまにゲーム上で「連続して攻撃を外す」「同じアイテムばかり出る」といった偏った現象が発生した時に「シレンの乱数は偏りやすい」といったようなコメントがよく書き込まれています。
人間の感覚というのものは偏った現象に気づきやすいものであり、この手の意見は大抵誤っている（特に最近ではソシャゲのガチャが操作されている！などとすぐに言われますね）のですが、風来のシレンはSFC時代のゲームという事もあり実際に質の悪い乱数生成ルーチンになっている可能性もあります。
そこで気になって調べてみると、すでに乱数生成ルーチンを解析してネット上に公開されている方が居ました。

• 裏CHUNSOFT > ROMイメージ改造・解析 > 乱数生成

解析の結果、この頃のゲームでよく使われていたと思われる線形合同法による擬似乱数生成でも、乱数テーブルの参照をフレーム単位で次々と切り替えて乱数を必要とする瞬間に参照している値を乱数として使用する方法でもありませんでした。
（もっとも、風来のシレンにおいては冒険の中断セーブや死亡時の行動のリプレイなどを実現するために階の最初からのプレイを再現する必要があるので、乱数の状態変数の初期値とプレイヤーの操作順序のデータだけで状況を再現できない後者の乱数生成方法はそもそも使用できませんが。）

#SFC版風来のシレンの乱数生成ルーチン解析
風来のシレンの乱数生成ルーチンの詳細については、上述のサイトをじっくり読めば分かるのですが、多少説明不足で分かりづらいところもあるように思えたので、折角なので私が理解した内容をここで解説してみたいと思います。

##ROMデータを逆アセンブルしたコード
上述のサイトから風来のシレンのROMデータの乱数生成ルーチン部分を逆アセンブルしたコードのリストを下記に引用します。解説には不要と思われるのでアドレス部分と生のマシン語部分は削除し、アセンブリ部分と解析した方が追記したコメント部分のみ残しました。コメントの数値はすべて16進数であることに注意が必要です。

PHP             ; 
REP #$20        ; 
LDA $B7         ; "A" = 100 * $B8 + $B7
ASL * 5         ; "A" *= 20 (を10000で割った余り)
EOR $B8         ; "A" = "A" xor 100 * $B9 + $B8
ASL             ; "A" *= 2 (を10000で割った余り)
SEP #$20        ; 
LDA $B8         ; 
STA $B9         ; $B9 = $B8
LDA $B7         ; 
STA $B8         ; $B8 = $B7
LDA $B6         ; 
STA $B7         ; $B7 = $B6
XBA             ; 
STA $B6         ; $B6 = "A" / 100 (余りは切り捨て)
STA $00         ; $00 = "A" / 100 (余りは切り捨て) (これが新しい乱数になり、乱数生成ルーチンを呼び出した側で受け取られる)
STZ $01         ; 
PLP             ; 
RTL             ; 

コードをぱっと見た限りではかなり短くまとまっており、そんなに複雑なことはして無さそうです。

##乱数生成ルーチンの解説
乱数生成ルーチンの内容については、アセンブリのコードのコメントと上記サイト（65816アセンブラの解説も含む）をよく読めば分かるのですが、少々分かりづらい箇所があるように思えますので、コードを見ながら順に解説してみます。

###前提知識
まず乱数生成ルーチンのコードを読む前提条件として以下の点を抑えておく必要があります。

Aレジスタ

RAMの読み書きやデータ演算等に使用する汎用の16bitレジスタ。Pレジスタのフラグの状態で値を1バイト単位のデータを扱う場合と2バイト単位のデータを扱うモードが切り替わる。1バイト単位のデータを扱う場合は下位バイトの値のみを使用する。

Pレジスタ

プログラムの動作状態の各種フラグを保持するレジスタ。

\$XX

\$XXはRAMのアドレス(16進数)を示す。乱数生成ルーチンで使用しているのは\$00,\$01,\$B6-\$B9の6つのアドレスで、\$00-\$01には生成した乱数の値が戻り値として格納され、\$B6-\$B9には過去に生成した乱数が新しい順に4つ格納される。

#\$XX

#\$XXはXX(16進数)の値そのもの(即値)を示す。乱数生成ルーチンではフラグのビット位置の指定に使用している。

生成する乱数の範囲

風来のシレンは0-255の値を乱数として生成し、使用する。

###コードの解説
それでは順にコードを見ていきます。

PHP             ;

PHP命令はPレジスタの値をスタックに退避します。PusH Pの意でしょう。
Pレジスタは上述の通りプログラムの動作状態のフラグを保持しているので、サブルーチンの先頭で状態を退避しておきサブルーチンから戻る前に元に戻すのが常套手段なのでしょう。

REP #$20        ; 

REP #$20はPレジスタと0x20をビット反転したもののANDを取りPレジスタに格納します。要するにPレジスタの第5ビットを0にするという事です。REsetbit Pの略といったところでしょうか。
Pレジスタの第5ビットは、Aレジスタを1バイト単位で扱うか2バイト単位で扱うかのフラグになっており、第5ビットが0の時は2バイト、1の時は1バイト単位で扱います。
第5ビットを0にしたという事は、今後はAレジスタは2バイト単位でデータを扱うことになります。

LDA $B7         ; "A" = 100 * $B8 + $B7

LDA $XX命令は$XXの値をAレジスタに格納します。LoaD Aの意でしょう。
Aレジスタの下位バイトに$B7の値、上位バイトに$B8の値を格納します。前の命令でAレジスタを2バイト単位でデータを扱うようにしたので、上位バイトにもデータが格納されたわけです。コメントでは100(16進数) * $B8 + $B7となっていてぱっと見分かりづらいですが、要は$B7から$B8の連続した2バイトのデータをAレジスタに入れるということですね。

ASL * 5         ; "A" *= 20 (を10000で割った余り)

ASLはAレジスタを左に1ビットシフトする命令です。A Shift Leftの意味でしょうか。¹

EOR $B8         ; "A" = "A" xor 100 * $B9 + $B8`
ASL             ; "A" *= 2 (を10000で割った余り)

EOR $XXはAレジスタと$XXの値のXORを取りAレジスタに格納する命令です。ExclusiveORの略ですね。
ここではAレジスタの値と$B8から$B9の連続した2バイトの値のXORを取ってAレジスタに格納します。
それからASL命令でAレジスタを更に左に1ビットシフトします。
ここまでが乱数生成処理となり、この時のAレジスタの上位バイトが今回生成された乱数になります。

以上の乱数生成処理の流れを整理すると以下のようになります。[0]-[7]、<0>-<7>、(0)-(7)はそれぞれのメモリ内の第0ビット-第7ビットの値と思ってください。

+----------$B9-----------+----------$B8-----------+----------$B7-----------+ 
|[7][6][5][4][3][2][1][0]|<7><6><5><4><3><2><1><0>|(7)(6)(5)(4)(3)(2)(1)(0)|
+------------------------+------------------------+------------------------+
        ↓ Aレジスタに$B7-$B8を格納
+------------------Aレジスタ----------------------+
|<7><6><5><4><3><2><1><0>(7)(6)(5)(4)(3)(2)(1)(0)|
+------------------------------------------------+
        ↓ Aレジスタを左5ビットシフト
+------------------Aレジスタ----------------------+
|<2><1><0>(7)(6)(5)(4)(3)(2)(1)(0){ }{ }{ }{ }{ }|
+------------------------------------------------+
        ↓ Aレジスタと$B8-$B9のXORをAレジスタに格納
+------------------Aレジスタ----------------------+
|<2><1><0>(7)(6)(5)(4)(3)(2)(1)(0){ }{ }{ }{ }{ }|
|                       XOR                      |
|[7][6][5][4][3][2][1][0]<7><6><5><4><3><2><1><0>|
+------------------------------------------------+
        ↓ Aレジスタを左1ビットシフト
+------------------Aレジスタ----------------------+
|<1><0>(7)(6)(5)(4)(3)(2)(1)(0){ }{ }{ }{ }{ }{ }|
|                       XOR                      |
|[6][5][4][3][2][1][0]<7><6><5><4><3><2><1><0>{ }|
+------------------------------------------------+
        ↓ Aレジスタの上位バイト
+--生成された乱数---------+
|<1><0>(7)(6)(5)(4)(3)(2)|
|          XOR           |
|[6][5][4][3][2][1][0]<7>|
+------------------------+

結局の所、「$B7の第2ビット-$B8の第1ビットの8bit分のデータ」と、「$B8の第7ビットから$B9の第6ビットの8bit分のデータ」のXORを取ったものが生成された乱数になる、ということです。
乱数の生成ができたので、以降は生成後の処理になります。

SEP #$20        ;

SEP #$20命令はPレジスタと0x20のORを取り、Pレジスタに格納します。SEtbit Pの略といったところでしょう。
要するにPレジスタの第5ビットを1にします。前述したフラグの説明の通り、今後はAレジスタは1バイト単位でデータを扱うようになります。

LDA $B8         ; 
STA $B9         ; $B9 = $B8
LDA $B7         ; 
STA $B8         ; $B8 = $B7
LDA $B6         ; 
STA $B7         ; $B7 = $B6

STA $XXはAレジスタの値を$XXに格納する命令です。STore Aの意味でしょう。
$B8の値をAレジスタに格納し、Aレジスタの値を$B9に格納、$B7の値をAレジスタに…と繰り返しているのを見ればわかるように、$B8,$B7,$B6の値をそれぞれ$B9,$B8,$B7に移動（1バイトシフト）させています。
過去に生成した乱数の値の格納場所を1個ずつ後ろにずらしたわけですね。後で今回生成された乱数が空いた$B6に入ることになります。
前のSEP命令によりAレジスタのデータは1バイト単位で扱うようになっているので、Aレジスタにメモリの値を読み込んだ時に上位バイトも格納されたり、Aレジスタの値を$B8に格納した時に上位バイトが$B9に格納されたりというような事はありません。

XBA             ; 

XBA命令はAレジスタの上位バイトと下位バイトの値を入れ替えます。eXchange Byte Aの略ですかね。
この命令はAレジスタを1バイト単位で扱う時も2バイト単位で扱う時も関係なく入れ替えが行われます。
ここで思い出してほしいのですが、先程Aレジスタの上位バイトが今回の生成した乱数の値になると述べました。そしてその後はずっと1バイト単位でデータを扱うモードでAレジスタを使用しています。つまりAレジスタの下位バイトしか使用してないので、上位バイトには生成した乱数の値がそのまま残っていることになります。そこで上位バイトと下位バイトを入れ替えるのですから下位バイトが生成した乱数の値となり、結果としてAレジスタの値が生成した乱数の値になるというわけです。
可読性が下がる手法ですが、いかにもアセンブリ言語の時代のプログラミングといった感じですね。

STA $B6         ; $B6 = "A" / 100 (余りは切り捨て)
STA $00         ; $00 = "A" / 100 (余りは切り捨て) (これが新しい乱数になり、乱数生成ルーチンを呼び出した側で受け取られる)
STZ $01         ; 

さてAレジスタの値が晴れて生成した乱数の値になりました。まずSTA $B6でさきほど場所を空けた$B6に最新の乱数生成の結果として値を格納します。
次にSTA $00で$00にも同じ値を格納します。こちらはコメントの通り、乱数生成ルーチンを呼び出した側が使います。
STZ $XXは$XXの値を0にします。SToreZeroの略でしょう。
ここではSTZ $01で$01の値を0にしています。これはおそらく生成した乱数の値を2バイトのデータとして扱う時のために、$00を下位バイトとした時の上位バイトにあたる$01をゼロクリアしているのだと思われます。

PLP             ; 
RTL             ; 

PLPで最初にスタックに退避しておいたPレジスタの値を元に戻します。PuLl Pの略と思われます。通常プログラミングではPushに対する操作はPopというように思いますが、65816アセンブラのアセンブリ言語ではPushの対操作としてPullというようですね。
RTL命令はサブルーチンを終了し呼び出し元に戻ります。おそらくReTurn Longの略です²。

以上がSFC風来のシレンの乱数生成ルーチンになります。ルーチンの動作全体を模式図的にまとめてみると、次のようになります。

+----------$B9-----------+----------$B8-----------+----------$B7-----------+----------$B6-----------+
|[7][6][5][4][3][2][1][0]|<7><6><5><4><3><2><1><0>|(7)(6)(5)(4)(3)(2)(1)(0)|{7}{6}{5}{4}{3}{2}{1}{0}|過去の乱数列
+------------------------+------------------------+------------------------+------------------------+
              ↓抽出                                    ↓抽出
   +-------------------------+             +-------------------------+
   |[6][5][4][3][2][1][0] <7>|-----XOR-----|<1><0> (7)(6)(5)(4)(3)(2)|
   +-------------------------+      |      +-------------------------+
                                    ↓
                        +------------------------+
    サブルーチン戻り値←---|   今回生成された乱数    |-------------------------------------+
                        +------------------------+                                     |
                                                                                       |
                                      $B6-$B9を1バイトシフト                            ↓
+----------$B9-----------+----------$B8-----------+----------$B7-----------+----------$B6-----------+
|<7><6><5><4><3><2><1><0>|(7)(6)(5)(4)(3)(2)(1)(0)|{7}{6}{5}{4}{3}{2}{1}{0}|          空き          |過去の乱数列
+------------------------+------------------------+------------------------+------------------------+

図にしてみると割とシンプルなのがわかります。

##C言語によるSFC風来のシレン乱数生成互換ルーチンの実装
解析内容を元に、SFC風来のシレンの乱数生成の互換ルーチンをC言語で実装してみます。
解析結果を見ての通り、分かってしまえば非常にシンプルな処理なので、簡単に実装できます。
擬似乱数生成器の状態変数にあたる$B6-$B9は合計32ビットなので、状態変数は32ビット変数1つで事足ります。

#include <stdint.h>
                                                                                                       
#define SIREN_RNG_INIT_STATE 0xf7e8dd05
static uint32_t siren_rng_state = SIREN_RNG_INIT_STATE;

uint8_t siren_rng_next()
{
    uint32_t result =
        ((siren_rng_state & 0x7f800000) >> 23) ^
        ((siren_rng_state & 0x0003fc00) >> 10);

    siren_rng_state <<= 8;
    siren_rng_state |= result;

    return (uint8_t)result;
}

必要無いとは思いますが一応解説します。
32ビット変数のsiren_rng_stateを$B6-$B9に見立てています。状態変数の初期値SIREN_RNG_INIT_STATEは上述の解析サイトに記述されている初期値の例に合わせています。
まずresultの下位8バイトにsiren_rng_stateから該当場所の8bitずつのデータを抽出してXORを取り格納します(乱数生成部分)。
つぎにsiren_rng_state を8ビット左シフトして過去の生成乱数の値をずらします($B6-$B8を$B7-$B9に移す部分)。
最後にsiren_rng_stateの下位8bitに生成した乱数の値を格納($B6に生成した乱数を格納する部分)し、戻り値としてもその値を返して終了です。

##Xorshiftに似ているような？
この風来のシレンの乱数生成ルーチンを見て思ったのが、アルゴリズムがXorshiftに似ているということです。

• 直近4つの乱数の値を元に次の乱数を生成する
• 直近4つの乱数の値から適当に抽出したいくつかの値をシフトさせそれらをXORした値を次の乱数とする

抽出する値の個数やXORを適用する回数が違うとはいえ、この2点がXorshiftのアルゴリズムと全く同じ着想のように思えます。Xorshiftは2003年（当然ながらSFCシレンよりかなり後年）に提案されたアルゴリズムなのだそうですが、正式に高品質な擬似乱数生成器の論文として発表されたのが2003年でありアルゴリズムの原型自体は昔からあったものなのでしょうか。
いずれにせよSFC時代のゲームの乱数にしては、シンプルでありながらもなかなか凝った実装なのではないかという気がします。

線形帰還シフトレジスタの一種

(2017/12/04 追記)

Twitterで、この形式の乱数生成方法は「線形帰還シフトレジスタ」と呼ばれる物の一種であると教えていただきました。

• [線形帰還シフトレジスタ(Wikipedia)]
  (https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E5%B8%B0%E9%82%84%E3%82%B7%E3%83%95%E3%83%88%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF)

過去の状態からXORとシフトだけで次の状態を作るXorshift、そしてシレンの乱数生成アルゴリズムはこの線形帰還シフトレジスタの特徴を満たします。
乱数生成はテーブル参照や線形合同法が多かった時代に、チュンソフトは先進的なアルゴリズムを取り入れていたようです。ENIX（当時）のソフトの外注先であったことからもソフトハウスとしてレベルが高かったことが伺えます。

#それで結局風来のシレンの乱数の品質はどうなのか
解析結果の解説で思いの外長くなったので、記事を分けて改めます。

• 続編：SFC版風来のシレンの乱数生成アルゴリズムの話 考察編

1. コメントいただいたようにArithmetic Shift Leftの略のようです。引数にメモリアドレスを指定した場合そのアドレスの値をシフトするので、Aアドレスに限った命令ではないようです。
   ASL * 5 というのはASL命令が5個連続しているという事です。すなわちAレジスタの値が左に5bit分シフトされます。
   ここのコメントも分かりづらいですが、"A" *= 20というのはAレジスタを5ビットシフトするということで、10000で割った余りというのはシフトではみ出したビットは捨てるという事ですね。 ↩

2. RTSという近くのアドレスからのサブルーチン呼び出しに限定した終了命令もあり、このSはShortを意味していると思われます。追記：コメント頂いたように、SはシンプルにSubroutineの頭文字のようです。元々RTS命令があったところにアドレスをLong Jumpする命令が必要になったので、RTL(こちらのLはLongで正しいようです)が追加されたということみたいです。 ↩