IMG_5950

【CEDEC2014】パックマン、ドルアーガの塔…往年のナムコタイトルから学ぶ乱数の進化と応用

  • このエントリーをはてなブックマークに追加

by [2014年9月08日]

先日パシフィコ横浜で開かれたゲーム開発者向けのイベント「CEDEC 2014」では様々な興味深い講演がありました。

今回はその中から、バンダイナムコスタジオの加来量一氏による、「ゲーム世界を動かすサイコロの正体 ~ 往年のナムコタイトルから学ぶ乱数の進化と応用」という講演をご紹介したいと思います。

加来 量一氏 株式会社バンダイナムコスタジオHE技術部プログラマー。1995年株式会社ナムコ (現・バンダイナムコゲームス)入社。「アルマジロレーシング」「ニンジャアサルト」等、業務用大型体感ゲームの制作に数多く携わった後、近年は主にコンシューマー向けゲーム、及びライブラリ開発に従事。「スターフォックスアサルト」「ソウルキャリバーレジェンズ」「ソウルキャリバーIV」「塊魂ノ・ビ~タ」「太鼓の達人WiiUば~じょん」他。 CEDEC2009公演「加速度センサの更なる活用」。2012年バンダイナムコスタジオ移籍。

2つの乱数

まず最初に、加来氏は乱数が2つに大別されることを示しました。

一方は、次に出る値が全く予測できない「真の乱数」。

もっともこれは次に出る値が予測できず同じパターンが再現できません。そのためネットワークで繋がっていてリプレイなどの必要のある最近のゲームでは、これはむしろ使用されては困る状態であるようです。

そのため、最近のゲームではもう一方の乱数、つまり一見でたらめに見えても未来が決定している、そしてパターン数が有限なためいつかは元の値に戻る性質を備えている(=周期性がある)疑似乱数が用いられている由です。

疑似乱数

続けて加来氏は、その疑似乱数の仕組みを説明しました。

まず、疑似乱数にはシードと呼ばれる乱数のパターンを決める種となる変数があります。

このシードに何らかの数字を正規化し、そして現在のシードの値を基に次の値(シード)を作るアルゴリズムを適用します。これが乱数アルゴリズムです。

もっとも実際には、何らかのコミット変換を行う、正規化する、といった形で出力変換アダプタを用いて、必要な範囲である一定周期内にほぼ一様な出現頻度で値が分布する(=一様乱数となる)ようにしているそうです。

ナムコゲームの乱数

ここで加来氏はナムコで初期からの業務用、家庭用、MSX用、ファミコン用ビデオゲームで乱数アルゴリズムがどういった形で用いられてきたのか、50本位調査したと語りました。

曰く、この調査はどのゲームも原始的なアセンブリ言語で書かれていたため非常に大変な作業で、キーワードを使って(ソースコードに書かれたコメントなどを検索し)乱数の部分を探した由です。

もっとも、それも一筋縄ではゆかず、「Random」と書くところを「ransu」などとローマ字表記で書かれたものもあったそうで、そうして見つかったものについて分類したが見つからなかったものも多かったとのことでした。

貧弱だった80年代のハード

そもそも1980年代の当時のマシンは性能が貧弱で乱数も計算規模の大きな物は使えませんでした。

具体的には8ビットCPUの場合だと一度に扱える数値は8ビットまで、メモリ空間もキロバイト単位で計算に使えるレジスタ(※注1)本数も少なく(※注2)乗除算機能は基本的になく、浮動小数点演算(float)や三角関数などの演算機能もありませんでした。

 ※注1:CPU内部で扱うデータを一時的に保持しておくための高速かつ小容量のメモリ。
 ※注2:例えば当時ホビーパソコンで多用されたザイログZ80では数値演算用レジスタは基本的にAレジスタ1本のみでした。

またこの時代のCPUは今からすると非常に低い動作クロック周波数しか利用できませんでした。

そのため、ここからはこうした貧弱なハードでいかにしてランダムな物を作って行くのか、初期のビデオゲームはどうやっていたのか、が説明されました。

混沌の時代

初期は手探り状態で、タイトル毎に全く違うコードが書かれていたりして、何をやっているのかを読み取るのが非常に困難であった、と加来氏は語りました。

代表的な手法として、画面出力用Vsync(垂直同期)カウンタを回してプレイヤーが何かしたときにそのカウンタの値を読み出すものや、テーブル(乱数表)を用いると行ったアナログな手法が存在しました。

もっとも、実際には(高価で希少な)メモリを消費する乱数表は用いられていなかったようです。

パックマンの乱数

ここで加来氏はこの時代のナムコの代表作の一つである「パックマン」を例に挙げました。

それによると、このゲームではメモリの&H0000~&H1FFFまでのアドレス(番地)に格納されている値を乱数のシードとする手法が用いられていたとのことです。

つまりプログラム本体を乱数のシードにするということで、その内容が一様である保証が無い(=値の出現頻度が均等になる保証が無い)上、プログラムを少しでも修正すると乱数の系列が変わってゲームの難易度や出現パターンなども変わってしまいます。

Rレジスタ法

この時代一般的だったZ80 CPUでは、Rレジスタと呼ばれる特別なレジスタが搭載されていました。

DRAMの場合、書き込まれたデータはそのままだと一定期間で消えてしまうため、定期的にその中身を読み出して再度書き戻す(=リフレッシュする)作業が必要です。Z80ではそのリフレッシュ作業に用いるレジスタがCPU自身に内蔵されていました。

そのため、このRレジスタの値はCPUの動作と無関係に常に変動していることから格好の乱数のシードとなり、実際にもそのように使われていたのです。

加来氏はそうしたRレジスタの利用例として、シューティングゲームの「ギャラガ」を挙げました。

「ギャラガ」では、一旦Rレジスタの値を使用して生成した乱数にさらにRレジスタの値を加算することで簡単に乱数を生成しているそうです。

もっとも、Z80固有のハードウェアを利用しているわけですからこれは他のCPUでは使えませんし、そもそもどんな値がいつ来るか判らないRレジスタを利用するため再現性が無く、しかも一様乱数としての性質が保証されないというゲームでは割と困った問題もあります。

線形合同法

続いて加来氏は、現在用いられている乱数生成手法についての説明に移りました。

一番手となったのは、長らくC言語のrand()関数で利用されていた線形合同法(Linear Congruential Generator:LCG) です。

このLCGでは定数AとB、それにnが入力された場合に、

rt =(rt-1×A+B)mod 2n

という漸化式で前回の乱数を利用する仕組みになっています。

もっとも、加来氏曰く実際のプログラムではrt-1×A+Bの計算結果を2のn乗で割った余りを求めるmod 2nの部分はレジスタが桁あふれするのに任せて省略する由で、乗算と加算一つずつで済ませています。

このAとBの条件としてAが4の倍数+1、Bが奇数の時、この乱数は例えば8ビットだと2の8乗=256通りの数を全部出してくれる、つまり一様乱数として機能するようになっています。

そのため、ナムコタイトルではLCGとして、

rt = rt-1×5+1

が多く使われていたそうです。Aが4+1=5でBが1ですから、256通りの値の出る最小の数値を用いていたわけです。

なお、この時代のプログラムでは多くのCPUに乗算命令が無かったため、このLCGは加算命令だけで実装されていた(※注6)とも説明されました。

 ※注6:上の式だとrt-1×5は例えばrt-1にrt-1を4回足せば乗算は不要です。

具体的には、LCGはナムコでは左に示すようなタイトルで使われていたとのことです。

なお、「パック&パル」でLCG(13+1)、つまりrt = rt-1×13+1となっているのは、このゲームの基板のCPUが乗算命令の備わるモトローラMC6809だった(=大きな数の乗算によるペナルティが小さかった)ためだそうです。


ここで加来氏は実際に(5+1)LCGの出力結果をプロットした図(左上)を示しました。

一見して全ての座標がほぼまんべんなく出ているように見えるのですが、よく見るとうっすら斜めにシマが出ています。

実はこれがLCGの弱点で、加算と乗算で構成される関係上、桁繰り上がりを起こして下位ビットに影響が出にくいのです。

そのため、最下位ビットでは0、1、0、1と周期が2で、2ビット目は周期が4.3ビット目は8となったりします。

このようにビット毎に周期が違う問題があるため、LCGの出力の下位ビットではちゃんとしたサイコロにならないので気を付けるように、との指摘がありました。

線形帰還シフトレジスタ

続いて示されたのが、線形帰還シフトレジスタ(Linear Feedback Shift Register:LFSR)です。

これはシフト演算器で入力値のビットを上にずらすシフト演算を行って、任意の特定ビット間で排他的論理和(XOR)演算を行い、その結果を繰り上がって空いた一番下のビットに戻すという仕組みです。

これはもともと電子回路で用いられた手法で、ハードウェアではシフト演算器とXOR演算器を適宜用意すれば比較的簡単に構成でき、しかも規則性の低いビット列が高速で生成されます。

このLFSRではシフト演算器を構成する各ビットの中から特定ビットを抽出してXOR演算を行う回路を、交流トランスやコイルなどで回路パイパスして特性を変化させる機構に見立ててタップと呼びます。

LSFRにおいては、シフト演算器に入力される最初の値(=シード)とこのタップの個数およびその配置、つまりどのビットを抜き出してXOR演算させるかで乱数の周期が決定されます。

この周期は8ビットで最大255で、2^8=256にはなりません。つまり、どうしても1個出てこない乱数があります。この「1つ足りない」周期が最大となる組み合わせをM系列と呼びます。

このためLSFRでは、初期化を誤ると周期1のM系列から外れた乱数になって出力される値が固定されてしまいます。

ハードウェアLFSR

ここで加来氏はナムコのゲームでLFSRがハードで実装された例を挙げました。

それによると「ギャラクシアン」や「ギャラガ」などのシューティングゲームで、背景を縦にゆっくり流れて「インベーダー」などとの違いを際立たせていた星は、実はプログラムはVRAMに描画しておらず、16ビット長のM系列発生機を用いて出力して、純然たるハードウェア回路だけで構成・出力していたのだそうです。

つまり、16ビットのM系列で2^16-1 = 65535周期の乱数として星を自動生成していたわけです。

この背景画面の解像度は256×256ピクセルで各ピクセルについて乱数を出力し星を表示するかどうかを決めていきます。

256×256 = 65536ですから、16ビットのM系列だと1ピクセル分足りないのですが、その分1個ずつ順番にずれるので、勝手に背景が縦スクロールする訳です。

60階の迷宮

次に加来氏はソフトウェアでのLFSRの例を紹介しました。

ここで取り上げられたのは「ゼビウス」を生んだ天才プログラマー、遠藤雅伸氏が作ったナムコRPG初期の名作「ドルアーガの塔」です。

プレイヤー操る「ギル」が60階あるドルアーガの塔を登りさらわれた恋人の「カイ」を救うこのゲーム、実は各階の迷路データはマップとしては入っていなくて、オープニングで音楽が流れている間に(必死で)自動生成されているのだそうです。

しかもこの迷路、フロアごとにシードの数値が決まっているので、毎回各階で同じ形になるとのことです。

この「ドルアーガの塔」ではLFSRの途中に反転機が入った反転LFSRというものになっていて、反転機の入力値が0だったら1にする、つまりNOT演算するロジックが入っています。

加来氏はこの形がナムコではポピュラーに使われていたようだ、としました。

続けて加来氏は、このドルアーガの塔の反転LFSRの出力を調べて見たところ、実はこれは周期最大のM系列ではなかったとしました。

それによるとこの乱数は周期が217しかなく、他にも周期が31や7の系列が出てくる構成になっていたそうです。

もっとも「217もあれば十分な気がします」とのことで、マップの偏りやフロア階数なども勘案してこのような構成になったように見えます。

ここで加来氏は「ドルアーガの塔」の乱数について、乱数で書いたにしてはクセがあると思うが迷路といってもそんなに迷わない、としました。

曰くこれが「ドルアーガの塔」の特徴で、フロア1ではプレイヤーのギルがとても足が遅いためそのままではドアまでたどり着けずに終わってしまう、と。

実はこの迷宮の壁を構成する乱数は、LFSRを一辺につき2ビット使って向きを決定しているのだそうです。

1ブロックの操作では1ビットずつしか出ないため、残りのビットはただシフトしているだけで、上部に履歴として残っているのですが、その結果次に出るサイコロの目が決まってしまうのです。それにより、左図で赤線で示された3つのパターンしか出ないようになっているのです。

これにより、ドルアーガの塔の迷路は結果的に特徴のある迷路になっている訳です。

加来氏曰く、これはゲームデザインで成功していると思っている、とのことでした。

ちなみにこの「ドルアーガの塔」、最上階(60階)の迷路が櫛桁状の特徴的な配置で有名です。

実はこれはシードに特別な値(0×ff)を使っていて、出力が左に伸びる壁1種類しか出ないように構成されているのだそうです。

ソフトウェアLFSRの弱点

ここで加来氏はソフトウェアでLFSRを利用する場合の難点を指摘しました。

曰く、ハードウェアとしては非常に簡単な作りにできるが、ソフトウェアとしては非効率だ、と。

まず、同じシフトレジスタを表現しているはずなのに、プログラマによって全く違う書き方になる可能性があり、ソースコードの見通し(可読性)が悪いことと、その結果としてバグを見つけにくいことが指摘されました。実際反転し忘れのコードもあって、(バグの原因が)分かりずらかったそうです。

また、出力が1ビットであるため、8ビットの乱数として扱うにはこのLFSRを8回実行せねばならず、当時のPCでは重かったことと、先述の通り出てこない数があるため初期化でミスをすると乱数にならないことも指摘されました。

LCGか、LFSRか


ここまで、LCGとLFSRの損得が説明されてきましたが、これらを組み合わせて利用する手法が説明されました。

16ビットプロセッサが普及し始めた1980年代中頃から、LCGとLFSRを組み合わせて乱数とする手法がポピュラーになりました。

この手法ではLCGの難点であった下位ビットの周期性が改善され、LFSRの上位ビットの履歴も隠ぺいできるという大きなメリットがあります。

しかも、この手法ではシードが2つになるので乱数が長周期化します。そのため、3の次はかならず11が出るとか、そういったものが無くなる、と加来氏は指摘しました。

このLCGとLFSRを組み合わせて使う手法はしばらく流行しましたが、1980年代末にはテーブル参照手法が復権してきました。

当時CPUは80年代中盤から変化なかったのですが、メモリ増量が実現し余裕ができたので乱数テーブルを置こう、という考え方に至ったのです。

この時期、回転面やポリゴンなどの技術が用いられるようになっていました。

ナムコで言えば、「ワルキューレの伝説」や「バーニングフォース」のようにシステムII基板を使用したゲームが該当するのですが、低速で三角関数などの演算機能も持たないMC68000のような16ビットCPUでこれまでにない複雑な処理をこなさねばならず、そのため大容量メモリを積んでテーブルの行列変換で座標計算を行うことで三角関数などの超越関数演算を回避する手法が流行していました。

その延長線上で、CPUパワー的には重い乱数もついでにテーブルで処理しよう、という考え方が出てきたのです。

そして1990年代、乱数は大変革の時を迎えました。コンシューマーレベルでのC言語の導入が始まったのです。

C言語には一般に標準Cライブラリが付属するため、開発でそれに含まれるrand()関数を利用するケースが次第に増えてきました。

しかし、当時のrand()関数は大半が乱数アルゴリズムとしてLCGを採用していたため、80年代中盤にLCGとLFSRの合体で解決していた問題が再燃しました。

そのため今日では、より近代的なアルゴリズムに移行してきています。

ナムコ製ゲームでの乱数実装状況

ここで加来氏は一連のナムコ製ゲームでの乱数実装状況を示しました。

左図は80年代前半のアーケードゲームの場合です。

この図では、最初LCGとLFSRが現れ、それらを組み合わせるようになっていった状況が示されています。
加来氏曰く、「あまり正確ではないのですが。雰囲気だけつかんでもらえれば」とのことですが、LCGが先行し、LFSRが後追いで出現し併用されるようになった状況がよくわかると思います。

続いて示されたのはアーケードゲームの80年代後半の図です。ここで加来氏は、皆LCGとLFSRの合体になったと思いきや、単独搭載のパターンが案外残っていることを指摘しました。さらに彼はこうしたLCG・LFSR単独利用をプログラマーのこだわりなのかは詳しくは分かりません、と言い、同時に後半にテーブル利用が増えていることも指摘しました。

最後に示されたのはコンシューマー初期の場合です。MSXとファミコンで、こちらはほとんどがLCGとLFSRの合体型となっていることを指摘し、この辺は技術者同士の交流があったのかな?と想像するとコメントしました。

乱数の発達史と今日の乱数

最後に加来氏は、これまで述べられてきた乱数の発達史が今日の乱数にどのように繋がっていくのかを語りました。

まず触れられたのが、GFSR(Generalized feedback sift register)と呼ばれる手法です。

これはLFSRが1回の操作で1ビットしか出ない。ソフトウェアで実装しにくい、という問題の解決を図ったもので、例えばシフト演算器を32セット並べ、32ビット=1ワード単位で乱数列を得ようというものです。

もっとも、これは各演算器のシードの初期化が難しく。また最悪の場合毎回それぞれのビット列が同じ数字となる恐れがあります。しかもこれはLFSRが並んでいるだけなので、周期が長くないという問題もあります。

こうしたGFSRの問題を解決したのが、Twisted GFSRという改良型です。

タップを用いてXOR演算する前に、マトリクスで一次変換して各ビットを少しずつずらし、別のビットを混ぜる。これがひねっている(twist)ように見えるため、Twistedと呼ばれているのです。

さらにこの考え方を突き詰めたのが、メルセンヌ・ツイスタ (Mersenne twister)と呼ばれる手法です。

これはTwisted GFSRをさらに改良し、名称の由来となったメルセンヌ素数(2199937-1)を利用して調整を施すことで超長周期化と乱数分布の均等化をはかったものです。

一方、GFSRのXOR演算部分を例えば加算に置き換えると、フィボナッチの数列に似ています。このようにGFSRの演算部分を置き換えたものをLagged Fibonacd(遅延フィボナッチ法)と呼びます。

さらにこれのバリエーションの一つとして、演算部分を減算に置き換え、なおかつキャリーフラグと呼ばれる前回引いた時に値が溢れたかどうかを示すフラグの値も引く手法もあります。

現在のC++ 11の乱数の実装ではLCGとキャリー付き減算、それにメルセンヌ・ツイスタの三種が採用されています。

これらは左図で上にいけばいくほど軽くなって、下に行けばいくほどリッチになっていくという特徴があります。

当然ながらメルセンヌ・ツイスタは処理が重いのですが、メモリ消費量もシードのサイズも大きくなった分、乱数としての性質が改善されています。

加来氏はここでもう少し理解したい人向けとして、メルセンヌ・ツイスタの考案者である広島大学の松本 眞 教授の論文を読むことを推奨しました。

加来氏は、今回の講演の要点として

・乱数はその性質を見極めて、正しく使いましょう
・癖のある乱数も使い方次第でゲームに味わいを加えることができる
・ゲームの技術史とその変遷を読み解く意義

の三点を挙げました。

特に三点目に関しては、30年前の技術が何の役に立つのか?という疑問について、最近のメルセンヌ・ツイスタの技術もLFSRがベースになって進化してできている、という変遷を読み解いてゆくことで、今後次の変遷があった時にどのようなアイディアがあるか、あるいは過去の失敗事例を踏まえてどのように対応するか、我々は知る必要があると思う、としました。

▼参考リンク
関連論文(広島大学の松本 眞 教授の論文公開ページ)
CEDEC2014
バンダイナムコスタジオ

コメントは受け付けていません。

PageTopへ