神奈川のパシフィコ横浜で行われた，ゲーム開発者向けイベントCEDEC 2014の最終日である2014年9月4日，
「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」という講演が行われた。
登壇したバンダイナムコスタジオ HE技術部 加来量一氏
 |
 |
この講演のユニークな点は，旧ナムコの作品を「乱数」という視点から振り返るということだ。バンダイナムコスタジオ HE技術部のプログラマーである加来量一氏は，旧ナムコの初期作品50本を解析し，それぞれの時代でどのような乱数が使われていたかを特定した。そこから見えてくる乱数技術改良の歴史を見ていくというのが，講義の主旨なのである。
1980年代のナムコアーケード作品で使用されている乱数技術の一覧表。加来氏がそれぞれのプログラムを解析した結果だ。それぞれのプログラマーが独自に乱数生成アルゴリズムを作っていた「混沌」，乱数生成アルゴリズムを用いた「線形合同法（LCG）」「線形帰還シフトレジスタ（LFSR）」「LCGとLFSRを組み合わせて使用」，そして「乱数表（テーブル）の参照」……と大別できる。それぞれの乱数技術は時代の流れと共に明確に切り替わる訳ではなく，いくつかの方式が並行して使われていた。これはプログラマー個人のこだわりによるものではないか，と加来氏は推測する
 |
 |
MSXやファミコンで発売されていたナムコ作品における，乱数技術の一覧表。さまざまな方式が混在していたアーケードとは違い，「LCGとLFSRを組み合わせて使用」に統一されているが，加来氏はプログラマー同士の技術交流が盛んだったためではないかと考えているそうだ
 |
氏が乱数にこだわった理由は，乱数が生み出す偶然性が遊びの本質と考えているからだ。乱数とは，ランダムに数を生成すること。例えばサイコロなどは乱数を作り出す装置だ。次に出る目が何になるかは分からないからこそ，偶然性による遊びが生まれる。すごろくでは自分の駒を進める数がサイコロによって決められるため，毎回異なった展開が生まれるが，これなどは乱数の偶然性が遊びを面白くする好例だろう。
ゲームにおいても，乱数は重要な役割を担っている。敵の動きやAIの振る舞いなどが毎回変化し，展開が単調にならないのは乱数のおかげだ。乱数は，次に何の数が出るか分からない「真の乱数」と，ある程度の法則性がある「疑似乱数」に分類できるが，現代のゲームでは疑似乱数が使われている。これは，真の乱数を使うと，自分のプレイを後から再生できるリプレイ機能などがうまく働かないためであるという。
「真の乱数」と「疑似乱数」。現在のゲームでは後者が用いられる
 |
 疑似乱数の仕組み。上部のseed（乱数のもととなる数）に，アルゴリズムで加工を加えることで乱数を生み出していく。偏りのない乱数を生み出すため，これまでもさまざまな改良が繰り返されてきた |
 今回の研究のテーマとなる8ビット時代では，かなり限られた条件下で乱数を作らなければならなかった |
時代と共に変化していく乱数
・混沌の時代
加来氏は，ナムコ最初期を乱数技術における「混沌の時代」であると分類する。CPUの処理能力やメモリの制限が大きい中，プログラマーが乱数を発生させる方法を模索し，それぞれのタイトルで色々な手法が使われていたためだ。
画面同期を行った回数を乱数の替わりに用いたほか，「パックマン」ではseedを使ってメモリのどこかのアドレスにアクセスし，そこに存在する数値を乱数として用いたり，「ギャラガ」のようにメモリをリフレッシュするための「Rレジスタ」をseedにするといった工夫が用いられていたという。
 混沌の時代では，プログラマーごとに異なった方法で乱数を生成していた |
 パックマンではseedを使ってメモリにアクセスし，そこにある数値を乱数として使用していたという。スライド中に書かれたコードは，それぞれの乱数発生方式を加来氏がC言語で解釈し直したもの |
Z80に特有の「Rレジスタ」をseedとした乱数
 |
 |
・線形合同法（LCG）の時代
その後，乱数生成に「線形合同法」（LCG）というアルゴリズムが用いられるようになる。LCGはC言語標準ライブラリの乱数で使われていることでも有名で，ひと言で表わすと「足し算とかけ算の組み合わせ」だ。当時CPUとして使われていたZ80はかけ算ができなかったため，足し算を連続させることで擬似的なかけ算とし，LCGを実現していたというから，いかに制限が大きかったかがうかがえる。
画面のキャラクターは乱数生成アルゴリズム「線形合同法」の擬人化。名前を募集中とのこと
 |
 |
加来氏解析による，LCGを使用した代表的なナムコタイトル。それぞれの作品で微妙に方法が異なっているのが分かる
 |
 |
LCGの欠点。繰り上がることの多いかけ算と足し算で構成されているため，下位のビットがあまり変化しない
 |
・線形帰還シフトレジスタ（LFSR）の時代
簡単に実装でき，ばらつきのある乱数を出力できることから，LCGに次いで次いで「線形帰還シフトレジスタ」（LFSR）が使われるようになった。「ギャラクシアン」や「ギャラガ」の背景できらめく星々も，実はLFSRによる乱数から作られている。画面を1ドット描くごとに乱数が作られ，星の有無や色などが決められているそうだ。
「線形帰還シフトレジスタ」（LFSR）の概念。元々は電子回路で使われていた方式であり，そのためハードウェア的な実装が容易だという。左写真のキャラクターは，加来氏による「線形帰還シフトレジスタ」の擬人化で，名前は「シフトレジ子」
 |
 |
 「ギャラクシアン」や「ギャラガ」においてLFSRはハードウェア的に実装され，星々を描くのに使われている |
 加来氏解析による，LFSRを使用した代表的なナムコタイトル |
そして「乱数の話をする際には欠かせないだろう」ということで紹介されたのが「ドルアーガの塔」だ。本作は，主人公のギルが迷路状のフロアを突破していくという60面構成のゲーム。現在のゲームであれば，プログラムの中に60階分のマップデータが内蔵されているところだが，本作にはそうしたものは存在しない。ステージ開始時の音楽が鳴っている最中，乱数を使って迷路の壁が生成されているという。
乱数のseedとなるのは，ステージごとに決められた数値。seedが決められているため，毎回同じ形の迷路が生成されることになる。ランダムな結果を導き出すはずの乱数が，毎回同じでなければならないマップを作るのに使われている逆転現象が面白い。
同作の迷路で特徴的なのが，通路が右下へ伸びるジグザグの階段状になっていることで，これはLFSRが1回の計算で1ビットの乱数を生成するところを，2ビット組み合わせて使っていることから，規則的な階段状の構造が生まれるのだという。加来氏によれば，ドルアーガの塔については「このテーマだけで講演時間を全て使っても説明しきれない」ほどにディープな話題なのだそうだ。
ドルアーガの塔のLFSRで作られた迷路（左写真）と，本当にランダムに作成された迷路（右写真）。ドルアーガの塔の迷路では「上下の回廊」と「右下へ伸びるジグザグの階段状通路」が特徴となるが，これは1ビットの乱数を生成するLFSRを2回分組み合わせて使ったことによるものだそう。結果として，複雑すぎず，足が遅い初期状態のギルでも制限時間内に突破できる迷路が生まれている
 |
 |
LFSRを2ビット分使ったドルアーガの塔の迷路生成
 |
LFSRの欠点。右側に並ぶコードは，LFSRをソフト的に実装する際の例。ソフト的にLFSRを作ろうとすると，プログラマーによって全く異なるコードになるため，エラーが見つけづらくなるという。加来氏によれば，過去のナムコ作品の中にもミスしたであろうと思われるLFSRが残っていたとのことだ
 |
・LCG＋LFSRの時代
ある程度まんべんなく乱数が出力できるものの，偏りも生まれやすく，下位のビットが周期化しやすいLCG。ハードウェア的には簡単に実装できるものの，1回の操作で1ビットしか乱数が出力できないため，ビット数の多い乱数を生成するためには計算回数が増えてしまうLFSR。それぞれにメリットとデメリットを持つ2つの形式だが，80年代中盤には両者を組み合わせた使用法がメインになった。これにより，両者の良い所取りが可能になっていったという。
・テーブルの時代
使えるメモリが少なかった時代は，テーブル（乱数表）を内部に持つようなことが難しかったが，80年代末にメモリが増えたことから，テーブルを使った乱数が主流になっていく。
・C言語の時代
90年代のゲーム開発ではC言語が盛んに使われるようになる。前述したようにC言語は標準ライブラリで乱数を生成できるため，これまでのような自作アルゴリズム乱数は姿を消していったそうだ。ただ，標準ライブラリの乱数はLCGによるものなので，LCGの問題が再燃したことから，現在では近代的なアルゴリズムが使われているという。
現代の乱数技術の数々。LFSRを32個並べるという，現在のCPUならではの力技を使い，一回で32ビットの乱数を生成できる「GFSR」。これを改良した「Twisted GFSR」。その発展型である「メルセンヌ・ツイスタ」。GFSRを様々な演算法で加工する「遅延フィボナッチ数列」など，過去のものをベースに現在の乱数技術が成り立っていることが分かる。C++11では，様々な乱数生成エンジンが使用可能
 |
 |
 |
 |
最後に加来氏は「癖のある乱数も，使い方次第でドルアーガの塔のようにゲームに味を加えることができます。乱数の性質を見極めて正しく使って下さい」と語って講演を締めくくった。
つぶやく
2014/09/05 14:03
