破滅的プログラミングの末路#02 「サイコロの5と6が出にくい・・・気がするので乱数考察」
普通のプログラマなら直感的、反射神経的に理解しているような、
初歩的で単純な小ネタを記事にしていこうかと思います。
初歩的ですが、私はヘボなプログラマなので、よくやらかします。
自分への戒めのためにも、小ネタを書いていこうと思います。
誤りや適切でない内容がある場合は、コメントいただければ、
修正、内容の調整等検討します。
1. 乱数
Random.nextInt()などのような、
乱数値を取得するメソッドを使ったことがあるプログラマは多いと思います。
0以上、9以下の整数値の乱数を取得する関数、メソッドは、例えば、
JavaならRandom.nextInt(10)、
C#ならRandom.Next(10)、
Pythonならrandom.randint(0, 9)などになると思います。
多くのプログラマにとって、乱数の散らばり方や周期性は、
時に、イラつくほど、値が偏っていると感じられるものかもしれません。
我々が通常扱うのは、ほとんどの場合、疑似乱数であって、
アルゴリズムによって乱数値は生成されています。
利用する(内部的に利用されている)アルゴリズムによって、さまざまな癖がありますが、
今回は、その点はいったん置いておきます。
(暗号化用途ではなければ、
そのバラつきや、周期性の長さから、個人的なおススメは、
メルセンヌ・ツイスタによって生成された乱数です。)
以下の記事は、Javaの例ですが、他の言語でも同様だと思います。
rand.nextInt(10)の部分を
C#ならrand.Next(10)、Pythonならrandom.randint(0, 9)などのように読み替えると、だいたい想像つくはずです。
2. とりあえず、Javaで100億回、乱数値を取得してみた
ひとまず、Javaで、100億回、乱数値を取得してみます。
Random.nextInt(10)を使って、0から9の乱数値を100億回取得して、
それぞれの出現回数をカウントしました。
Random rand = new Random();
long[] numCounter = new long[10];
for(long count = 0; count < 10000000000L; count++) {
int value = rand.nextInt(10);
numCounter[value]++;
}
結果は、以下のようになりました。
| valueの値 | 出現回数 |
|---|---|
| 0 | 1,000,017,191 |
| 1 | 999,943,364 |
| 2 | 999,983,662 |
| 3 | 1,000,012,905 |
| 4 | 1,000,049,567 |
| 5 | 1,000,001,706 |
| 6 | 999,982,619 |
| 7 | 1,000,068,926 |
| 8 | 999,966,928 |
| 9 | 999,973,132 |
バラつきに関しては、数学的に分析した方がよいのかもしれませんが、
今回は数学回ではないので、ぱっと見で判断しましょう。
100億回の試行回数に対して、各数値の単純な出現回数だけに着目すると、
それほど大きな問題はなさそうです。
Javaの標準的な実装では、線形合同法で乱数生成されていますが、
それらの特性に関しては、今回は棚に上げておきます。
3. 生成された値に手心を加えると、悲惨な結果になる場合がある。
int value = rand.nextInt(10);のvalueに対して、
6面のサイコロを振った結果になるように計算してみましょう。
rand.nextInt(6)にすればいいじゃんっていうのは、今回は、なしの縛りプレイで。
int sainome = (value % 6) + 1;とかやれば、
サイコロの1から6の目を出せそうです。
(value % 6)の部分で、0から5になるので、あとは、サイコロの目に合わせて1足しているだけです。
徹夜のゲーム明けで寝不足な場合などは、これで問題ないとスルーしてしまいそうですが、
この計算は、まったくフェアではありません。
| sainomeの値 | 出現回数 |
|---|---|
| 1 | 1,999,999,810 |
| 2 | 2,000,012,290 |
| 3 | 1,999,979,833 |
| 4 | 1,999,986,037 |
| 5 | 1,000,049,567 |
| 6 | 1,000,001,706 |
1から4の目は、だいたい20億回出現していますが、
5と6の目は、10億回くらいしか出現しておらず、
およそ倍の開きがあります。
4. なぜ、賽の目の5と6があまり出なかったか・・・
今回は、小さな数値で試したので気付きやすかったのではないかと思います。
valueの値と、(value % 6)の値を並べてみるとすぐ分かります。
| valueの値 | (value % 6)の値 |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
| 6 | 0 |
| 7 | 1 |
| 8 | 2 |
| 9 | 3 |
上の表で、(value % 6)の値として、0, 1, 2, 3は2つずつあるのに、
4, 5は、1つずつしかありません。
これでは、フェアではありません。
5. 末路
乱数値は、時に、いらつくほど、バラつくものですが、
手心の加え方(乱数値をさらに演算する場合)によっては、より悲惨なことになりかねません。
今回の例はイメージしやすさ重視で、かなり極端な例にしているので、
実際には、今回に近い形でハマるケースは少ないかもしれませんが、
乱数利用時には、常に警戒しておくのはよいかと思います。
6. 対策
今回の例では、
int value = rand.nextInt(6);でも良いでしょうが、
rand.nextInt(6)はできないという、縛りプレイで考えてみます。
フェアかどうかの境界線は、valueの値が5以下かどうかにありそうです。
それ以外は、アンフェアであると判断して、アンフェアな値は無視することで、なんとかなりそうです。
int value = rand.nextInt(1000);の場合も考えてみましょう。
valueには、0から999までの数値がランダムに入ります。
この場合に、valueの値が5以下かどうかで判断して、
5以下はアンフェアとして無視すると、相当数が無視されることになって、
かなり効率の悪いアルゴリズムになりそうです。
無視すべきは、999の近くにありそうです。
| valueの値 | (value % 6)の値 |
|---|---|
| ... | ... |
| 990 | 0 |
| 991 | 1 |
| 992 | 2 |
| 993 | 3 |
| 994 | 4 |
| 995 | 5 |
| 996 | 0 |
| 997 | 1 |
| 998 | 2 |
| 999 | 3 |
この場合は、995までがフェアで996からがアンフェアであることになります。
アルゴリズムに落とし込むとこんな感じになりそうです。
-
int group = (1000 / 6);で、フェアなグループが何グループあるか求めます。 -
int unfairValueMin = (group * 6);で、アンフェアな最小値を求めます。 -
int value = rand.nextInt(1000);で生成された値をチェックして、
value < unfairValueMinがtrueのものはフェアであると判断して採用します。
それ以外は、アンフェアであるとして、
再度、乱数値を生成してフェアかどうかのチェックを繰り返します。 - フェアと判断した
valueを使って、(value % 6)を求めます。
※ この例以外にも、いろいろなアルゴリズムがあると思います。
JavaのRandom.nextInt()などでも、この種のフェアな対策がなされています。
さて、過度にフェアな値を求める必要がないケースも多いですが、
今回のような例を、うまくつかって、
逆に自らの意思で偏った乱数値を簡単に生成する方法もあります。
例えば、0から5を出す例では、
for(int i = 0; i < 100; i++) {
int value = (rand.nextInt(6) + rand.nextInt(6)) / 2;
System.out.println(value);
}
とか、
for(int i = 0; i < 100; i++) {
int value = rand.nextInt(3) + rand.nextInt(4);
System.out.println(value);
}
とか、
for(int i = 0; i < 100; i++) {
int value = (rand.nextInt(6) + rand.nextInt(6) + rand.nextInt(6)) / 3;
System.out.println(value);
}
とか、実際動かしてみたり、何が起こっているか考察してみると楽しいかもしれません。
(最後のコードは、5は、ほとんど出ないけど、2とか3は、めちゃめちゃ出るはず。)
どの程度偏らせるかは、やり方にもよりますし、
実際には、もっと厳密な方法が必要な場合もあります。