どうも、こんばんは。taroです。
今回はゲーム等でしばしば登場する乱数についてのお話をします。
乱数というと確率論の中の一分野なのですが、これが意外と難しいです。
難しいからと言ってほっておくと、この分布の確率モデルはどうでといって積分記号を何個もつけた 式を書き付けてしまいかねないので辞めにします。
今確率モデルという言葉を出しましたが、確率を計算することとモデルを作ることはほぼ同じです。 いきなりムツカシイ言葉遣いでなんのことだかさっぱりかもしれませんが、

例えば、宇宙人が存在する確率ってどれ位でしょうか？

「居るか、居ないかの2通りだから、1/2だね」なんていうと、信じる人も居るかもしれません。
これはあるモデルでは正しいです。つまり、「居る」・「居ない」という二つしかなく、また「この二つが 同様の確からしさである」ということです。ちょっと言葉遊びみたいですが、これを侮ってはいけません。
確率の計算が間違っていることと確率のモデルが間違っていることは、計算間違いでもしない限り同じだからです。
例えば、サイコロの目がどの目が出るのも「同様に確からしい」というのは直感的に正しそうで、 「宇宙人がいるのといないのは同様に確からしい」のはなんかおかしいというのは分かりやすいですが、 ちょっと普段使わないような数学の世界でのモノについては、数学を専門でやったことが無い限り、 気づきにくいです。

Arrayをランダムにシャッフルする

 

実はこのエントリを書こうと思ったきっかけは、wonderfl上で１行でArrayをシャッフルする というエントリがあるのですが、ちょっと確率論的な誤りがあって、別のエントリforked from: forked from: １行でArrayをシャッフルするがそれを示す良いテストとなっていたからです。（こういうことは分かるのに、コードは全く書けない・・・プログラム、アルゴリズム、数学はどれも別物ですね・・・）
勝手にネタにしてしまってすみません。「コードが書けないくせに、数学の話ばっかりしやがって！」と直接罵って下さい。
実は、１行でArrayをシャッフルするには2つ問題点があります。

• sortを用いて配列を分布が一様になるようにランダムに並び替えるということがほぼ不可能であり、もし実装したとしても計算量が多すぎて現実的ではないこと
• 上記とは反対に、一見分布が正しいかのように計算してしまっていること

2点目はちょっとしたミスで、sortが配列を破壊的に操作をしてしまい、それをfor文で回している為に、 一回目にシャッフルした結果をさらに次のループでシャッフルし、というようにfor文が回るたびにその結果をシャッフルしてしまうので、 1点目の問題を上手くテスト出来ていません。そしてそれを上手くテスト出来ているのが、forked from: forked from: １行でArrayをシャッフルする です。これは単にsliceをつけて元の配列が破壊されるのを防いだだけですが、その結果、このアルゴリズムの分布が一様でないことが分かります。

では何故でしょう？
Flash Playerの誤動作ではありません(笑)

実は、これには群論的な問題と確率論的な問題の二つが密接に絡んでいて、きっちり説明するのは大変なのですが、大体の理屈を説明いたします。
項目に分けて説明しますので、その項目についてご存知の方は読み飛ばしてください。

Array.sort

まず、sortに関数を渡すことが出来るのですが、

var arr:Array = [1, 2, 3, 4];

arr.sort(function (a:int, b:int):int {
    return (a < b) ? -1 : 1;
});

この関数は順序関係を定義する関数ですが、並べ替えをするときに、

• aをbより先に並べたい場合は-1
• bをaより先に並べたい場合は1
• aとbが同等の場合は0

という感じで定義します。多い順に数字を並べるには、

 

var arr:Array = [1, 2, 3, 4];

arr.sort(function (a:int, b:int):int {
    return (a > b) ? -1 : 1;
});

どっちが1でどっちが-1か分からなくなりそうですね。
配列を全順序関係Rによってソートしたいとき、 数学的な擬似コードで示すと、

arr.sort(sortCallback);

function sortCallback(a:Object, b:Object):int {
	return (a R b) ? -1 : 1;
}

つまり、Rが例えば、>だとしてみてください。ソートした結果、配列は、 >の順番に並びます。(前の要素 > 次の要素の順番)

sortを使うと何故一様でなくなるか？

sortというのは一般的に二つの要素を比較し、それを何らかのロジックによって入れ替えるという操作を繰り返しますが、数学的にこの操作を互換といいます。列のどんな並べ替えも全てこの互換だけで実現することが数学的には可能なのですが、もう一つの大事な性質として、偶置換と奇置換というものがあります。どんな列に対してもそれを互換だけで表現したとき、互換の数が偶数個であるか奇数個であるかというのは、列によって決まっています。
少し数学的な表現になりすぎましたので、雰囲気の伝わる例として、

1, 2, 3のから二つの数字を選んでその数字の場所を入れ替えたとします。つまり、1回互換をしたとします。この時、結果が2, 3, 1となることはなりません。というのは、1,2,3を並べ替えて2, 3, 1にするためには最低でも2回の操作が必要となります。また、ちょうど3回の操作(奇数回の操作)で2,3,1にすることは出来ません。

ということは、上のコードで1,2,3を並べ替えた結果6通りについてそれらが確率が一様に分布しているかを検証していますが、そもそも並べ替えの回数がそれぞれの順列によって違うので、一様には分布するとは限りません。また、sortは内部的には恐らくクイック・ソートのような方法で実装されているのですが、(sortのコール・バック内で引数に来る数字をtrace等で追ってみるといいです。)sortするということは全部の要素を万遍なく比較して、互換することになります。つまり、どの要素も最低でも1回は置き換えられるということになります。

• ある順列からある順列に並べ替えるには互換の回数が奇数回か偶数回か決まっている
• 順列の長さによって、互換の回数が少ないもの、多いもののばらつきが変化する
• ソートを使う限りは、どの要素も最低1回は並べ替えられる
• その結果、なりやすい順列となりにくい順列の差が出てくる

ということとなり、具体的にどの互換がなりやすいかとうのは、sortによって互換の起こる回数と配列の長さに依存して偏ってしまいます。恐らくどの要素も最低1回は並べ替えられるという制限が大きいのだと思います。逆に並べ替えが起きないこともある。というようなアルゴリズムであれば、ばらつきは無くなって来ます。

ばらつきの少ない並べ替えの方法

弊社村井のエントリでも取り上げられているようなアルゴリズムは直感的で特に面白みがないかもしれませんが、数学的にはばらつきが少ないです。そしてこのアルゴリズムのポイントは並べ替えが起きないこともあるということです。これがある意味では、結果の偏りをなくしています。

ここまで来るとまた、問題が起きてきます。それは何故並べ替えを行いたいのか？という根本的な問題です。例えば、カードのシャッフルのようなゲームであれば、順列の期待値が平均化されるということは大して嬉しくありません。なぜならば、[1, 2, 3]というカードを並べ替えて[1,2,3]みたいに、何回か並べ替えは起きるのに、結局元に戻る、とか、ちょっとしか並べ替えが起きていないということが起こるのは嬉しくない場合もあります。

あえて結果をばらつかせたい方法

厳密な方法でこれを実践するのは難しく、かなり直感的なものとなると思います。要は並べ替えの尺度みたいなのを用意して、オリジナルと比較して並べ替えが余り起きていなければ、もう一度やり直すということをします。例えば、並びの数が少ない(a[i]+1=a[i+1]となる箇所が少ない)とかは、一つの例でしょう。話を簡単にするため並べ替えるものは1～nの自然数とします。

function test(arr:Array):Number {
	var count:int = 0;
	for (var j:int = 0; j < arr.length - 1; ++j)
		if (arr[i] + 1 == a[i + 1])
			++count;
	
	return (arr.length - 1) ? (count / (arr.length - 1)): 0;
}

例えばこのようなtest関数を用意します。testは隣同士が再びまた隣同士になっている割合を だすのですが、例えばこの割合が0.5以上だったら再シャッフルというアルゴリズムを埋め込んでみると、オリジナルとは違った、見た目がランダムな感じの並び替えとなります。 次がわざと並べ替えの分布を偏らせてみたサンプルです。