確率と乱数
確率の基本と、コンピュータで乱数を作る方法(擬似乱数)、乱数を思いどおりの範囲や割合で使う方法について説明します。
<注意>
このページでは、数式を表示するためにMathJaxを使用しています。ブラウザの設定でスクリプト実行をブロックしている場合、ページ内の数式が正しく表示されません。
確率の基本
ある出来事が起こる確率は、0(決して起こらない)から1(必ず起こる)までの数で表します。
起こりうる場合がどれも同じくらい起こりやすいとき、確率は次のように求めます。
定理
- \(\ A\ \)が起こらない確率は\(\ 1 - P(A)\ \)である。
- \(\ A\ \)と\(\ B\ \)が互いに影響しない(独立な)とき、両方が起こる確率は\(\ P(A)\,P(B)\ \)である。
- \(\ A\ \)と\(\ B\ \)が同時に起こらないとき、どちらかが起こる確率は\(\ P(A) + P(B)\ \)である。
期待値
結果に数値が付いているとき、「数値 × その確率」を全部足したものを期待値と言います。
何度も繰り返したときの平均にあたります。
何回で起こるか
1回あたり確率\(\ p\ \)で起こる出来事が、\(\ n\ \)回のうちに1回以上起こる確率は、「1回も起こらない」の反対として求めます。
\[ 1 - (1 - p)^n \]また、初めて起こるまでの回数の期待値は\(\ 1/p\ \)です。
例
毎フレーム1/64の確率で敵が弾を撃つとき、平均すると64フレームに1回撃つ。
60フレーム(NTSCで約1秒)のうちに1回以上撃つ確率は、\(\ 1 - (63/64)^{60} \fallingdotseq 0.61\ \)である。
平均の間隔が1秒を超えていても、1秒のうちに撃つことのほうが多い。
確率が一定のままだと、運が悪ければいつまでも起こらないことがあります。
「最後に起こってからの時間が長いほど確率を上げる」「一定の時間が過ぎたら必ず起こす」といった工夫で、待ち時間の長さを抑えられます。
擬似乱数
CPUは同じ入力からは必ず同じ結果を出すので、本当にでたらめな数は作れません。
そこで、決まった計算を繰り返して、でたらめに見える数の並びを作ります。これを擬似乱数と言います。
定義 (擬似乱数)
状態\(\ x\ \)と、状態を更新する関数\(\ f\ \)を決め、\(\ x_{n+1} = f(x_n)\ \)を繰り返して得られる数の並びを擬似乱数と言う。最初の状態\(\ x_0\ \)を種(シード)と言う。
状態が\(\ n\ \)ビットなら、状態は\(\ 2^n\ \)通りしかないので、いつか同じ状態に戻り、そこからは同じ並びを繰り返します。
繰り返すまでの長さを周期と言います。
同じ種からは、必ず同じ並びが出てきます。
これはデモの再生や、不具合の再現には便利です。
毎回違う並びにしたいときは、タイトル画面でボタンが押されるまでのフレーム数など、プレイヤーの操作で決まる値を種に混ぜます。
線形合同法
合同算術を使って、次の式で状態を更新します。
\[ x_{n+1} = (a\,x_n + c) \bmod m \]定理
\(\ m = 2^k\ \)のとき、\(\ c\ \)が奇数で、\(\ a \equiv 1 \pmod 4\ \)ならば、周期は最大の\(\ m\ \)になる。
たとえば8ビット(\(\ m = 256\ \))で\(\ a = 5,\ c = 1\ \)とすると、0～255のすべての値が1回ずつ現れます。
ただし、\(\ m\ \)が2のべき乗の線形合同法には、下位のビットほど周期が短いという弱点があります。
最下位ビットは0と1を交互に繰り返し(周期2)、下位2ビットは周期4、…となります。
線形合同法の値を使うときは、上位のビットを使います。
LFSR(線形帰還シフトレジスタ)
状態を1ビット右にシフトし、押し出されたビットが1だったら決まった値とEORを取る、という操作を繰り返します。
決まった値をうまく選ぶと、\(\ n\ \)ビットの状態で、0以外の\(\ 2^n - 1\ \)通りの値がすべて現れます(0になると0のまま抜け出せないので、0だけは使えません)。
シフトとEORだけで作れるので、ゲームでよく使われます。
16ビットで$B400を使うものは、周期が65535になります(擬似乱数のレシピ)。
続けて取り出した値の関係
続けて取り出した2つの値を、横軸と縦軸にとって点を打ったものです。
本当にでたらめなら、点は正方形全体にまんべんなく散らばるはずです。
- LFSRの値を続けて取り出すと、次の値は前の値を1ビットシフトしただけなので、点は数本の直線の上に並びます。
- LFSRを8回進めるごとに取り出すと、点はまんべんなく散らばります。
- 16ビットの線形合同法(\(\ a = 5,\ c = 1\ \))の下位バイトは、はっきりした縞模様になります。
1回の判定に1つだけ乱数を使うなら、続けて取り出した値の関係はあまり気になりません。
1フレームに何個も乱数を使う場合(敵の位置と速度を同時に決めるなど)は、1つ使うたびに何回か進めるか、性質のよい作り方を選びます。
乱数の範囲を決める
0～255の乱数\(\ r\ \)から、0～\(\ k-1\ \)の乱数を作る方法は、いくつかあります。
| 方法 | 計算 | 偏り |
|---|---|---|
| ANDで取り出す | \(\ r\ \mathrm{AND}\ (k-1)\ \) | \(\ k\ \)が2のべき乗なら偏りなし |
| 余りをとる | \(\ r \bmod k\ \) | 小さい値が少し出やすい |
| 掛けて上位を取る | \(\ (r \times k) \gg 8\ \) | 個数の偏りは同じだが、偏りがばらける |
| 範囲外なら引き直す | \(\ r < k\lfloor 256/k \rfloor\ \)になるまで引き直す | 偏りなし |
\(\ k\ \)が2のべき乗でないと、256通りを\(\ k\ \)等分できないので、どうしても偏りが出ます。
\(\ k = 6\ \)のとき、\(\ 256 = 6 \times 42 + 4\ \)なので、4つの結果は43回、残りの2つは42回現れます。
余りをとる方法では0～3が出やすく、掛けて上位を取る方法では、出やすい結果がばらけます。
差は約2%なので、多くの場面では問題になりませんが、偏りをなくしたいときは引き直します。
掛けて上位を取る方法は、乗算器を使えば割り算をしなくて済みます(乗算器と除算器)。
重みを付けて選ぶ
「アイテムAを50%、Bを30%、Cを20%」のように、確率に差を付けて選ぶには、重みを積み上げた表を使います。
| 結果 | 重み | 積み上げた値 |
|---|---|---|
| A | 128 | 128 |
| B | 77 | 205 |
| C | 51 | 256 |
0～255の乱数\(\ r\ \)を引き、積み上げた値が初めて\(\ r\ \)より大きくなる行を選びます。
重みの合計を256にしておけば、8ビットの乱数をそのまま使えます。
ばらつきの形を変える
1つの乱数は、どの値も同じくらいの確率で出ます(一様分布)。
乱数をいくつか足すと、真ん中の値が出やすく、端の値が出にくくなります。
サイコロ1個では1～6が同じ確率ですが、2個の和では7が最も出やすく、3個の和では釣鐘のような形に近づきます。
「だいたい真ん中だが、たまに大きくずれる」ばらつき(弾の散らばり、ダメージの幅など)を作りたいときは、乱数を2～3個足して使います。
並べ替え(シャッフル)
\(\ N\ \)個のものをでたらめな順番に並べ替えるには、次の方法(フィッシャー-イェーツのシャッフル)を使います。
- \(\ i\ \)を\(\ N-1\ \)から1まで1ずつ減らしながら、次を繰り返す。
- 0～\(\ i\ \)の乱数\(\ j\ \)を引き、\(\ i\ \)番目と\(\ j\ \)番目を入れ替える。
すべての並び方が同じ確率で出てきます。
「0～\(\ N-1\ \)の乱数を引いて入れ替える」を\(\ N\ \)回繰り返す方法は、一見同じに見えますが、並び方によって出やすさに偏りが出ます。