2014年9月4日 にあった、ＣＥＤＥＣの講演についての記事です。


ゲーム世界を動かすサイコロの正体 ～
　　往年のナムコタイトルから学ぶ乱数の進化と応用

 

バンダイナムコのプログラマさんより乱数の講演です。

・ゲームで使われている主要な乱数のしくみについて
・乱数のアルゴリズムが改良されていく歴史
・乱数の選択の注意点

などについて、取り上げられました。

 
（乱数分布などは　せっかくなので　初め、自分で乱数プログラム組んで　用意しようかと思ったのですが
力尽きてしまい・・・

撮影した写真を使わせていただきました）

--------------------------------------------------------------------

●はじめに

・真の乱数

→　実際のサイコロ

予測不可能
再現不可能

・疑似乱数

→　ゲームプログラムで使われているのは こちら

でたらめに見えるが、法則性があり　実はすべて未来が決まっている
いつかは元の数字に戻る　（周期がある）

 

●乱数の要素

・種 （ｓｅｅｄ）

・種を更新する アルゴリズム

・出力変換アダプタ
　（更新された種を 使いやすい形に変換する）

 

●今回の講演にむけて

ナムコから発売された、初期の業務用、家庭用　約５０タイトルのプログラム（アセンブラ）を解析し

乱数アルゴリズムが どのように遷移していったのか　調査しました。


　業務用：　１９８０年代 （８ビット）
　家庭用：　１９８０年代前半 （ＭＳＸ，ファミコン）

 

ちなみに、８ビットＣＰＵ というと・・・

　扱える数字　　　０～２５５
　メモリ空間　　　１６ ～ ６４ＫＢｙｔｅ
　計算に使用できるレジスタ　１～２個
　掛け算、割り算　できない
　ｆｌｏａｔ　　　ない

 

--------------------------------------------------------------------

●混沌な時代

・手探りで乱数を模索

ＶＳｙｎｃカウンタ（画面同期カウンタ）の利用

　・・・　プレイヤーがボタンを押した瞬間の ＶＳｙｎｃカウンタを乱数として使用する方法

テーブル（乱数表）を参照する方法
　　→　しかし、「乱数表」を用意するメモリは勿体ない

 

・パックマンでは

プログラムのＲＯＭ内のメモリを乱数表と見立てて使用する方法

実装例：　A = *((char *)( seed & 0x1fff ))

問題点・・・

　一様な乱数では無い。
　プログラムを変えると、乱数も変わってしまう。

 

・ギャラガでは

Ｒレジスタを乱数として使用した

・・・　Z80特有の　メモリのリフレッシュを行うためのカウンタ
　　　　
　　　　→　メモリの情報保持のために、CPUの動作関係なしに常に動いているレジスタ
　　　　　　不規則な数字が格納されている

実装例：　A = *((char*)( 0x100 + Vcnt + R ))
　　　　　A = A + R

問題点・・・

　Z80以外のCPUでは使えない。
　再現性がない
　乱数の値が一様である保証が無い

 

--------------------------------------------------------------------

●線形合同法

最も有名な乱数

　乱数 = ( seed * A + B ) mod 2^n

A = (4の倍数+1) 、　B = 奇数　の時、最大周期 2^n

Ｃ言語の rand()関数に使われているため　最もポピュラー

 

・ナムコのゲームでは　伝統的に

　seed * 5 + 1

が使われていた。

利点・・・

　掛け算がないＣＰＵでも 容易に実装可能
　
　周期が最大 256　（8ビットなら）

 

具体例としては

　ポールポジション　　seed * 5 + 1  +  Ｖカウンタ
　ディグダグ　　　　　seed * 5 + 1
　パック＆パル　　　　seed * 13 + 1

 

・欠点

分布を見てみると、縞になりやすい

 


下位ビットほど周期性がない

　→　下位１ビット目　周期2
　　　下位２ビット目　周期4
　　　下位３ビット目　周期8
　　　下位４ビット目　周期16

 

--------------------------------------------------------------------

●線形帰還シフトレジスタ

電子回路でよく用いられる方法

シフト演算器の特定ビットをＸＯＲして戻すだけ

１回の操作（クロック）で １ビットの乱数を得られる

どのビットを抽出して、XORを取るか？ で周期が決まる。
（8ビットだと　最大周期255）

例）

　4ビット目 と 7ビット目を抽出して乱数を作ります。

　レジスタが 01011000　という状態のとき　4ビット目と7ビット目のXORは 1

1という乱数を得た後

レジスタを一つシフトし （01011000 → 10110000）
下位１ビットに 得られた乱数 1 を入れる　（10110001）


　→　レジスタは 10110001 になる　　（この時のXORは 0）
　→　レジスタは 01100010 になる　　（この時のXORは 0）
　→　レジスタは 11000100 になる　　（この時のXORは 1）
　→　レジスタは 10001001 になる　　（この時のXORは 1）
　→　・・・

こうして、得られたビットを　乱数として扱う。



利点・・・
　出力ビットのばらつきがとても良い

 

・実際の使用例

ギャラクシアン、ギャラガで　背景の星の配置に 使用していた。

他には、
ボスコニアン　　　6ビット目と14ビット目のXOR の反転　＋ Rレジスタ
マッピー　　　　　0ビット目と7ビット目のXOR の反転
ドラゴンバスター　8ビット目と15ビット目のXOR の反転

 

・ドルアーガの塔 での使用例

ステージのフロアを 乱数で生成している。
（種はフロア毎に固定なので　毎回同じ形のステージになる）

4ビット目と7ビット目のXOR の反転　したものを使用

より踏み込んだ内容は、こちらにまとめました。
http://sekigames.gg-blog.com/Entry/291/



・欠点

　実装したコードを見ても、パッと見　何をしている処理か良く分からない。

　１回の操作では、１ビットしか取得できない
　（８ビットの乱数を得るためには ８回操作をしないといけない）

　変化しない形が存在する

　→　00000000　は何度操作しても 00000000 になる。
　　　（初期化に注意）

 

--------------------------------------------------------------------

●８０年代 中頃

・線形合同法　＋　線形帰還シフトレジスタ

両方の結果を足して、それを乱数とする手法

 

線形合同法 と 線形帰還シフトレジスタ　のいいとこどり

→　線形合同法の 下位ビットの周期性が改善
　　線形帰還シフトレジスタの上位ビットの履歴も隠蔽

→　乱数の周期が拡大
　　　（周期 55552）

 

●８０年代末

・テーブル参照主義 の復権

この頃　メモリが増大し（MByteの時代）　CPUはまだまだ遅かった

Sin、Cos、Atan、Sqrt　なんでもテーブルに入れてしまえ
な時代だった

 

●９０年代

・Ｃ言語の襲来

→　乱数アルゴリズムを自作せず
　rand() をそのまま利用するコードが主流に

→　線形合同法の問題が再び・・・

 

--------------------------------------------------------------------

●現在の乱数

・ＧＦＳＲ　（Generalized Feedback Sift Register)

線形帰還シフトレジスタ を３２個並べれば　１回の操作で 32ビット乱数が取れる

　　シフトレジスタ　→　ワード列の配列

 

欠点

　周期は １ビット分の線形帰還シフトレジスタ と同じ

　適切な種で初期化しないと、適切な乱数が生まれてくれない

 

これが進化して

Twisted GFSR

→　メルセンヌ・ツイスター法　　（超長大周期　2の19937乗 - 1）

 

--------------------------------------------------------------------

●まとめ

乱数は その性質を見極めて、正しく使いましょう

癖のある乱数も 使い方次第でゲームに味わいを生むことができる

→　ドルアーガの塔が とても良い例

過去の乱数アルゴリズム の反省点や改良から
今の メルセンヌ・ツイスター法 が生まれたという事もあり　過去の技術史を読む解くのも大変意義があります。

 

[7回]