プチコン講座

番外編 プチコンで疑似乱数を作ろう

【プチコン/mkII 両対応】

 プチコンには標準でRND関数が備わっておりこれによってA=RND (10)で0〜9の乱数を発生させることが可能になっています。普通に使う場合には全く問題ないのですがゲームなどで使用する場合には同じ乱数列の乱数を発生させることができないという問題になることがあります。それは、ゲーム内で同じものを再現ができないということです。
 例えば敵キャラの動きを乱数によって決定する場合にはプレイするたびに敵の動きが変わるため必勝パターンというものを作りにくいというのが挙げられます。コンシューマゲームやアーケードゲームでもスタート時の敵の動きが同じステージでは毎回同じ動きになっているというゲームもあります。また、ステージデータを自動的に乱数によって生成する場合はクリア不能な面が生成してしまう場合があります。これが、乱数を自分で制御できればクリアが可能かはプレイヤーの手によって検証が可能になります。

 乱数だから「でたらめな数」なのが当たり前ですがコンピュータの計算によって生成される疑似乱数においては完全な「でたらめな数」というのは無理な話で計算のための初期設定が必要になります。その初期設定の値をユーザーの手によって行うことが可能な場合があります。多くのBASICではRNDOMIZEの引数によって同じ乱数列の乱数を発生可能だし、ポケコンではシャープの機種においてはRND(負の数)で同じ乱数列の乱数を発生させることが可能になっています。
 これは一般的にはseed(シード)と言われていますがプチコンのRND関数では、シードを与えることができないため同じ乱数列の乱数を再び発生させるということができないのです。しかし、プチコンのRND関数も所詮が疑似乱数であり、シードを与えることができないのならば自分で疑似乱数の計算を行えば良いだけの話です。

 一般的なコンピュータによって生成される疑似乱数の中で最もポピュラーなのが線形合同法によるものです。したがって、まずはそれについて見ていくことにしましょう。

 《線形合同法の公式》
 X(N+1)=(A*X(N)+B) mod M


 このA、B、Mの組み合わせによって乱数の発生の仕方(最大値や周期など)が変わってきます。Mが乱数列の最大周期になり、M-1がこの乱数列の最大値になります。
 例えばX=(X*3+2)%64という式で考えてみます。

 まず使うためにはこの乱数の初期値(上記の「シード」)を決める必要があります(今回はその初期値は0に設定しました)。この初期値によって乱数の発生の仕方が変わってきますが逆にいえばこの初期値が同じならば発生する乱数列は同じものになるためゲームなどにおいて再現性を持たせることが可能になるというわけです。

《 リスト1 》
 ACLS
 X=0
 FOR I=1 TO 64
  GOSUB @RND
  ? X;
 NEXT
 END
@RND
 X=(X*3+2)%64
 RETURN
ACLSはmkIIでのみ使用可能なので初代プチコンはCLS:GCLSと置き換えて考えてください。
場合によってはGPAGE 0VISIBLE ,,,,,1が必要になる場合があります。

 上記のようにこの乱数列の周期は公式Mの値が64であることから、周期が64と推測されるため64個の乱数を発生させてそれを画面に表示させてみましたが、よく見ると同じものが4回タブっているということに気が付くでしょう。
 つまり、この式は周期16の疑似乱数ということです。これはあくまでMの値が最大周期と言うだけであってAやBの値によってはその最大の周期を得ることができないというわけです。

 次にこの乱数を使って画面上にドットを表示してみましょう。

《 リスト2 》
 ACLS
 X=0
 FOR I=1 TO 64
  GOSUB @RND:A=X
  GOSUB @RND:B=X
  GPSET A,B,15
 NEXT
 END
@RND
 X=(X*3+2)%64
 RETURN

 周期が16の乱数であるため16個のドットが表示されることを期待してみましたが画面上には8個しかドットが表示されていません。

実は線形合同法には以下の2つの問題点があるのです。

《 線形合同法の問題点 》

(1) 上位の桁はランダム性が高く下位の桁はランダム性が低い
(2) いくつか組にして使えばランダムではなくなる


それを順に解説していきます。

(1)リスト1において発生した乱数をよく見ると全部偶数になっています。
線形合同法における乱数は下位の桁は全部奇数、全部偶数、奇数と偶数を交互のいずれかになってしまいます。(最大周期が得られる場合は必ず奇数と偶数が交互になる)
 生成された乱数が偶数と奇数を交互に繰り返すというのは、言い換えると2進数で表した時には最下位は0と1を交互に繰り返すということです。これは最下位だけに止まらず下位Kビットの最大周期は2^K-1になります。どれだけ周期の長い乱数であっても、2進数で表して下位3ビットのみを取り出してやれば最大でも周期は7しかないということです。
 したがって、基本的に線形合同法によって生成される乱数は下位は極力使用せず上位から使うのが望ましいといえます。

(2)これはリスト2の実行結果を見ればよく分かるでしょう。
 周期16の乱数でも2つ組み合わせれば実際の周期は半減してしまうわけです。そのため組み合わせて使用するのが前提であれば必要な周期の数倍の周期の乱数が求められてきます。X座標、Y座標において別々に乱数を発生させるのではなく1つの乱数でX座標、Y座標を求めることでこの問題は解決できそうですが、そのためには縦横64の場合は0〜4095の乱数が必要になります。縦横256の場合は0〜65535になります。極力下位ビットをしないようにしなければならないのにこれではそれが難しくなってしまいます。
 そのため周期を増やすことでこの問題を解決することにします。とはいうもののどの程度必要かというと具体的にはジャンルによって変わるので難しいでしょう。
 ゲームではなく科学技術シミュレーションならば億単位、兆単位の周期でないと使い物にはなりませんが、プチコンではそのような用途には用いることはほぼありません。

 仮にゲームで使用する場合について考えるとメインルーチンがVSYNC1(60fps)で実行するゲームだと30分のプレイで最低でも108000回の乱数発生が行われます。敵キャラ8体に乱数を使えばその8倍になります。そうすると少なくとも周期は10万単位で欲しいところでしょう。
 また、プチコンにおいては標準のRND関数によってランダムに表示したドットで画面を埋め尽くすことが可能になっているため同じような使用方法を可能にするためにはそれができるくらいの周期があるのが望ましいです。

《 リスト3 》
 ACLS
 FOR I=1 TO 524287
  GPSET RND(256),RND(192),15
 NEXT

 プチコン(というかDS)の液晶画面解像度は256x192であり、合計49152のドットで構成されています。このことからすべてのドットを埋め尽くす期待値を計算すると559345回のループが必要になってきます。X座標、Y座標、別々に乱数を発生させる場合には期待値を考えると2倍の数になるため最低でも100万回程度の周期が必要といえるでしょう。
 つまり、「プチコン標準のRND関数の代わりに使えるレベル」となると周期は100万回以上が合格ラインといえるけど現実問題からすれば線形合同法を使用する限りはそれは不可能といえます。
 それはプチコンで扱える上限の数が524287だからです。そうなるとプチコンだと下記のものが最大になりそうです。

 X=(X*5+3)%65536

 この式だと周期は65536になり、上記の十分とされる100万には及ばないけど最初に書いたX=(X*3+2)%64と比べるとかなり実用性は高くなりそうです。これを用いて上位8ビットのみを使って画面上にドットを表示してみることにします。
 8ビットで表すことのできる数字は0〜255であり、プチコンのグラフィック画面においてX座標は問題ないのですがY座標は収まりきらないため下画面も使って表示をすることにします。上下画面を使って2画面分を1画面のように使用する方法は第4回の講座で書いているのでそれを参考にすると良いでしょう。
 524287回のループですべてドットを埋め尽くせない可能性もあるため2重ループにして最大1億回実行できるようにしてみました。(もっともこの疑似乱数は周期が65536だから無意味だけど)

《 リスト4 》
 ACLS
 PNLTYPE "OFF"
 X=0:Y=0
  FOR I=0 TO 9999
   FOR J=0 TO 9999
    GOSUB @RND:A=X/256
    GOSUB @RND:B=X/256
    GPAGE 0:GPSET A,B,15
    GPAGE 1:GPSET A,B-192,15
   NEXT
  NEXT
 END
@RND
 X=(X*5+3)%65536
 RETURN

 これを実行すると画面には5本の直線が引かれるだけとなります。
 この乱数列の周期は65536で上位8ビットだけを見た場合に0〜255の値が一様に発生しているため画面の多くの部分にドットが表示されるべきなのだけどそれなのに256x5=1280個のドットしか描かれないというのはあまりに少なすぎます。
 これは発生する乱数に偏りがあるからというわけではなく0〜255までほぼ均等に発生しているのですがその数字の組み合わせそのものが少ないためです。これこそが、線形合同法のにおける問題(2)なのです。
 このような規則性は乱数を一次元的(0〜255まで均等に発生しているかどうか)に見ても分からないので2次元(X、Y座標を使って表示)もしくは多次元において検証する必要があります。 このプログラムではドットが表示されているか否かということだけに注目しているためドットの色は白で固定なのですがドットの色を随時変えることで同じ場所にどの程度の頻度で表示しているかというのが視覚的に分かるようになるので下記のように変更してみるのもいいかもしれません。

 GPAGE 0:GPSET A,B,GSPOIT (A,B)+1
 GPAGE 1:GPSET A,B-192,GSPOIT (A,B-192)+1


 このことから疑似乱数を使い下位ビットを捨てて使用するという使用方法をとる場合であっても線形合同法の場合は2つの数字を組み合わせて使用する場合において明確な規則性が出てしまい実用性の面において問題が発生する場合があるといえます。
 しかし、プチコン標準のRNDでできていることができないというのはさすがに気になるためこれを何とかして改善したいところでしょう。

 これは線形合同法をやめてM系列乱数を使用するとかxoreshiftを使うという方法によって解決は可能になります。

 例えば、M系列乱数ならば、線形合同法と比べて長い周期でなおかつ多次元に分布させることが可能になります。
 M系列乱数がどんな乱数かを簡単に説明すると予めP個の乱数を配列変数などに確保しておいてその中で最も古い乱数(新しいものから数えてP番目の乱数)と最新のものから数えてQ番目の乱数のXORを取りそれを新しい乱数として生成するというものです。この場合はPとQの値で周期は変わるものの最大周期は2^Pー1になります。
 リングバッファで確保しておけば処理そのものは単純になるのですが、いくら単純とはいえプログラムに組み込んで使うならばできるだけ短くて処理の速いものが望ましいでしょう。あくまで乱数を発生させるのが目的ではないからです。

 しかし、扱える上限数値が低いプチコンの場合はOverflowの可能性がさらに高まるし、速度においても線形合同法と比べて劣ります。
 単純で高速な線形合同法で十分な周期やばらつきが得られるならばそれがベターです。
 実は、線形合同法も工夫次第では周期を延ばしたり多次元分布をさせることも可能です。

 その1つの方法として私が考えた方法はカウンタを併用する方法です。1回ごとにインクリメントするカウンタを用意すれば座標が1つずつずれていくので理論上画面をドットで埋め尽くすことが可能になります。要するに線形合同法の問題(2)にある組み合わせて使用する場合にランダムではなくなるという問題を克服が可能になるということです。

 カウンタの周期を65536にしてしまえば乱数の周期と重なってしまうため周期は65536になってしまうけどこれを65535にすることで理論上の周期をほぼ2乗に引き上げることが可能になります。これはMとM-1が互いに素になっているからです。

《 リスト5 》
 ACLS
 PNLTYPE "OFF"
 X=0:Y=0
  FOR I=0 TO 9999
   FOR J=0 TO 9999
    GOSUB @RND:A=X/256
    GOSUB @RND:B=X/256
    GPAGE 0:GPSET A,B,15
    GPAGE 1:GPSET A,B-192,15
   NEXT
  NEXT
 END
@RND
 Y=(Y+1)%65535
 X=(X*5+Y)%65536
 RETURN

 これを実行すると確かにどんどん埋め尽くされていくもののランダムという感じが全くせずに明らかにパターン性を感じてしまいます。これは上記の線形合同法の公式におけるAに相当する「5」が65536に対して小さすぎるためです。
 これを大きくすれば解決する(たとえば12345とかに変えればかなり自然にドットが描画されていく)問題ですが、それはプチコンで扱える数字に上限があるため無理です。(最大値を計算すると809095109になってしまい余裕でOverflowになる)
 したがって、公式のMの値を小さくするしかありません。

 そこでMの値は4096にしました。
 それによって最大127までAの値を上げることが可能になり、かなり見た目のばらつきを持たせることが可能になります。周期が4096になるAの値はたくさんあるのですが、実際にドットを表示してみて発生した乱数に見た目の規則性が最も見られなかった「117」を採用しました。

《 リスト6 》
 ACLS
 PNLTYPE "OFF"
 X=0:Y=0
  FOR I=0 TO 9999
   FOR J=0 TO 9999
    GOSUB @RND:A=X/16
    GOSUB @RND:B=X/16
    GPAGE 0:GPSET A,B,15
    GPAGE 1:GPSET A,B-192,15
   NEXT
  NEXT
 END
@RND
 Y=(Y+1)%4095
 X=(X*117+Y)%4096
 RETURN

 規則性はほぼ無くなり上位8ビットを使う限りは全く問題はないように見えるでしょう。
 ちなみに771582回のループ(1543164回の乱数発生)で256x256の範囲をドットで埋め尽くすことができました。(期待値は764646回なのでほぼ期待値通り)
 これならばRNDの置き換えは十分にできそうです。
 線形合同法による乱数が苦手としている2次元分布にも十分使えると思うのでプチコンで普通に使う分には特に困ることはないと思います。

 これで終わってもいいのですが4096で割った数字を発生させることにしました。
 つまり、0以上1未満の乱数ということです。

《 リスト7 》
 ACLS
 PNLTYPE "OFF"
 X=0:Y=0
  FOR I=0 TO 9999
   FOR J=0 TO 9999
    GOSUB @RND:A=X*256
    GOSUB @RND:B=X*256
    GPAGE 0:GPSET A,B,15
    GPAGE 1:GPSET A,B-192,15
   NEXT
  NEXT
 END

@RND
 Y=(Y+1)%4095
 X=(X*479232+Y)%4096/4096
 RETURN

これによって下記の2つのメリットがうまれてきます。

 (1)使いやすい
 (2)上位ビットが優先して使用される

(1)0〜1の乱数というのは一般的なBASIC言語では非常にポピュラーであるため使用に慣れている人も多いということです。これが0〜4095の乱数だとダイスで1〜6の目を表示したいというだけでも4096で一端割ってから6をかけて1を足して整数化するという手間が加わってしまいます。
 つまり、4096の約数の乱数を発生させない限りは必ず4096で割るという手間が入ってしまうためにそれならば事前に4096で割ったものを発生した方がいいということです。

 これが4096ではなく8192だったらそういうわけにはいきません。
それはプチコンの小数部は12ビットであるため1/4096単位の数に丸められてしまうためです。
 
(2)乱数の返り値が0〜1の小数であれば「0〜3の乱数が欲しい」という際にはAに乱数の返り値が入っている場合はFLOOR (A*4)もしくは0 OR A*4いう方法をとるのが普通ですがこれが0〜4095であればA%4という方法をとるのが普通でしょう。しかし、A%4のような方法では下位ビットが優先的に使用されてしまうためランダム性が極めて低くなってしまいます。
 C言語の基本ライブラリである<stdlib.h>に含まれるrand関数は線形合同法によるものですが下位ビットを捨てて0〜32767の値で返しているので上記のような偶数と奇数が交互出るという問題は発生しないもののそれでもRAND_MAXの値で割って「事実上0〜1の乱数の状態」にして使用することが推奨されているくらいなのです。
 発生した乱数の下位から使うというのは市販ゲームでも実際に使用され問題になったこともあるためそういう問題を少しでも軽減するためにはやはり小数で発生させた方が都合が良いと感じました。

 あとプチコンで扱える数字が1/4096単位ならば上限2048や1024の乱数でもいいという考えの人もいるかもしれないです。しかし、少しでも周期が長い方がいい(1024にしてしまうと周期は1/16になってしまう)わけだし、それだけではなくプチコンで扱える数字が1/4096単位ということはそれ以下の数字は無視されるということです。
 その結果が上記リンク先のコラムに書いている演算誤差に繋がっているわけですが、4096で事前に割っておくことで普通に使うだけで下位ビットの周期性の短さは演算誤差で打ち消されてしまう可能性が高くなるということです。
 つまり、線形合同法の問題点が自然消滅する可能性が高いというわけです。
 もちろん、わざわざ4096倍して使えば下位ビットの周期性の短さは健在になりますが、これが100倍とか1000倍とかの「4096の倍数でない」ならば演算誤差で消えて無くなる可能性が高くなります。

 次にこの乱数にって発生した数値的に偏りがどの程度あるのかをモンテカルロ法によって検証してみました。

《 リスト8 》
 C=0:X=0:Y=0
 FOR I=1 TO 100000
  GOSUB @RND
  A=X
  GOSUB @RND
  B=X
  IF A*A+B*B<1 THEN C=C+1
 NEXT
 ? C*4/100000
 END
@RND
 Y=(Y+1)%4095
 X=(X*479232+Y)%4096/4096
 RETURN

 これを実行すると「3.14」となりこれは円周率にかなり近い値になっていることから普通に使用して問題ないレベルだと推測されます。

 あと気になるのは速度でしょう。。
 10万回ループによって実行してみたところRND関数は198フレーム、この疑似乱数は590フレームの実行時間となりました。
 確かにRND関数と比べたら遅いのですが、1フレームあたりだと169回発生できるためメインルーチン1回につき8個の乱数を発生させても1フレームの1/20以下の時間で済みます。
 またこの乱数で使用しているカウンタだけどメインルーチンで他にカウンタを使用しているならばそのカウンタを使えばY=(Y+1)%4095が不要になります。その場合はそのカウンタの変数がPの場合はX=(X*479232+P%4095)%4096/4096とする必要がるのですが、リストが短くなっただけではなく速度も10万回で463フレーム(1フレームあたり216回)ということで1.5倍も高速化できています。(0〜1の乱数専用であればY=(Y+0.0003)%0.9998X=(X*117+Y)%1としてX、Yそれぞれに0〜1の初期値を与えればさらに短く、かつ、速くなるし、0.00030.1に変えればさらに3文字分短くなる。こちらも参照。)
 また、線形合同法の問題を理解して上位ビットを優先して使う場合にはリスト6からカウンタを省略すればさらに短縮ができます。

 この疑似乱数の周期は16773120であり256x256程度なら余裕でランダムなドットによって埋め尽くすことが可能になるのですが、実際は最大で2048x2048までは埋め尽くすことが可能です。ただし、1024x1024を越える場合は縦横サイズによって埋められない場合もあります。
 実際にどんな感じかは、プチコンでは検証が不可能なのでPC用に簡単なソフトを作りました。こちらからダウンロードできます。(4096x4096まで検証が可能)

 今回はRND関数の代わり使える疑似乱数について考えたのですが、長期の周期性が求められてない場合やプレイヤーにとって気分の良いばらつきの疑似乱数を発生させる場合には乱数テーブルを用意してそれを読み取るという方法もあります。
 「気分が良い」というとかなり抽象的ですが、1/2の成功確率のイベントに10回連続で失敗とかいうのは一般的な演算によって生成される疑似乱数なら起きてしまう可能性は十分にあるのですが、予めテーブル化しておけばそれは防ぐことが可能になるということです。
 また、常に一定の乱数を使用するのではなく失敗が続けば確率が上がるようにして成功までの期待値が2回になる(体感的に1/2の成功確率になるようにする)という方法もあります。

 乱数はうまく使うことで、さまざまなゲームにおいてよりゲーム性を高めたり、よりプレイヤーに配慮したものにしたりすることが可能になります。プチコン標準のRND関数で困ることはないという人もいるでしょうが、それでは不十分な場合には疑似乱数の作り方やそれを使用する場合の注意点を把握して効果的に使うことが必要になります。今回書いた疑似乱数はシードを与えることで再現性のあるゲームを作るという際には非常に有効活用できるでしょう。


RETURN

inserted by FC2 system