アルゴリズム
ゲームプログラミング
乱数

サイコロを振るのは簡単である、しかし、ゲームでサイコロを実装するにはサイコロを知らなければならない

More than 1 year has passed since last update.

あなたはサイコロを正しく実装することができますか?

業務系ではあまり使わないですがゲームでよく使うものといえば「乱数」です。
でも、この乱数、意外と扱いが難しいものであることは知られていません。
何故でしょうか?

本来、コンピュータには「ランダムな数」というものは存在しません。
なぜかといえば、アルゴリズムは決定的なものなので、
同じパラメータを与えれば出力されるものも同じになります。
これは絶対不変のもので、ソフトウェアでは解決できないものです。
要するにソフトウェアにおける「乱数」とは必ず「疑似乱数」なのです。
(ハードウェアで本物の乱数を実装しているものはあります)
そうなんです。
ソフトウェアにおける「乱数」とははランダムということではなく、ランダムに見える数列を生成するだけなんですね。
多くの人たちはrand()(=乱数を生成する関数)のお世話になる筈ですが、単に初期化して呼び出すだけでなく、このことを正しく知っておく必要があります。

悪名高き線形合同法(Linear congruential generators)

1950年頃、Derrick Henry Lehmerという人がこのアルゴリズムを作りました。
ただ、これはゲーム業界において非常に悪名高いアルゴリズムでもあります。
皆さんは「カルドセプトサーガ」というゲームをご存じでしょうか。
これはサイコロを振って進むモノポリー型のカードゲームですが、サイコロの規則性があったことで一躍有名になりました。
特定の条件を満たした場合、サイコロは奇数と偶数を交互に出してしまったり、
次の出目が予測可能な状況になったりする現象があったためです。
これは線形合同法で実装された乱数の最下位ビットが0と1の繰り返しになることに起因したり、
同じ順序の数列が必ず生成されるということに起因しています。
それは、乱数がこのような性質を持っている事を実装担当者が知らなかったということを示しています。

ゲームにおける乱数を利用した良い例

ゲームにおける乱数といえば、敵がアイテムを落としたり、状態異常の魔法が効いたり効かなかったり、
クリティカルが出たり出なかったりと様々なところに使われています。
しかし、この乱数の再現性をあえて使ったことで意味を持つものもあります。
「ファイアーエムブレムシリーズ」ではセーブしてリセットしても同じ手順をとる限り結果が変わりません。
これは乱数から必ず同じ数値が得られるからであり「ゲームの仕様」です。
逆に「スーパーロボット大戦シリーズ」ではリセットをするたびに結果がかわります。
命中率10%の「ブレストファイヤー」を当てようとして頑張ったりした人も多いことでしょう。
これらは乱数の規則性を使う事でできるゲームの面白さの表現でもあります。
同じ乱数を再現させるためには同じシードを与え、何度目に出た乱数なのかを記憶しておくことです。
ゲームを再開するときに同じシードで初期化し、進めた分の乱数は捨てるだけなので簡単ですね。

シードを都度変えればいいのではないですか?

偏りがない乱数を生成する場合に、シードを毎回変えるという手法をたまにみかけます。
こちらは間違っています。
システム時間などをシードとして与える事がよくありますが、アルゴリズムによっては与えられたシードの数値をすべて使うとは限りません。
これにより選択される数列が狭まったり上位ビットや下位ビットに規則性が生じる可能性があります。
また、秒などを使っている場合は「同じ秒」に実行された乱数は必ず同じ順序で同じ結果を返してしまいます。
サーバーで乱数を必要とするアプリなどでは秒でシードを初期化するといったような間違いをしていないか確認する必要があります。
そうでないと、同じ数列が生成され、しかもその最初の方しか使わないため酷く偏るということが発生します。

恐らく最も優れた選択肢メルセンヌツイスタ(Mersenne Twister)

実装内容など詳しくはメルセンヌツイスタをご覧下さい。
こちらは非常に優れた疑似乱数生成アルゴリズムです。
よくわからなければ迷わずこれを使って下さい、と言い切って良いほど欠点のないアルゴリズムです。
従来の生成法の欠点を元に設計されているため、優れた周期性を持ち、均等に分布されるようになります。
また、非常に高速でメモリ効率が良いことでも知られています。

恐らく最も短いXorShift

XorShiftも一時期有名になりました。

unsigned long xor128(){ 
    static unsigned long x=123456789,y=362436069,z=521288629,w=88675123; 
    unsigned long t; 
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); 
} 

これだけの処理で、非常に短い処理で高い精度の疑似乱数を生成することができます。
メモリの少ないコンソールゲームでは見かけることもありました。
こちらも検討に値します。

基礎ライブラリの乱数を使うときは必ず何のアルゴリズムで実装されているか調べましょう

Cは「線形合同法」、
RubyやPythonは「メルセンヌツイスタ」です。
Javaは「線形合同法」、C#は「引き算法」です。
Golangでは「algorithm by DP Mitchell and JA Reeds」と書かれていますが、Plan9のCライブラリと同じ「線形合同法」のようです。
乱数の処理を呼ぶとき、気にかけてみて下さい。

最後に

乱数を使わないゲームというのはほぼ無いと言っても良いです。
完全情報ゲームである「将棋」などのAIであっても選択肢の決定に乱数を用いる事もあるでしょう。
(あえて悪手を選択させるなどですね)
ですが、乱数がどういった性質を持つものなのかは意外と正しく理解されていません。
皆さんが現実の世界でサイコロを振るときそれは真の乱数です。
しかし、ゲームの中でサイコロを振るとき、それは真の乱数ではないことを正しく理解しておく必要があります。