完璧なシャッフル

相変わらずマジック攻略サイトの開発中です。
ようやくシャッフルの方式が決まりました。

せっかくコンピュータでシャッフルするのですから、
人間様と違って完璧なシャッフルにしたい。
で、その完璧なシャッフルを実現する方式で悩んでいました。

現実世界で完璧なシャッフルをするのは、時間さえかければ実現できます。
サイコロを使って60枚の中から１枚を選び、次にまたサイコロを振って残りの５９枚の中から選び・・・というふうにやれば、完全にランダムな状態になります。

では、コンピュータではどうすればよいのか？
コンピュータはサイコロを持っていないので、サイコロのかわりに疑似乱数を使います。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
疑似乱数について知らない人の為の解説：

疑似乱数は、計算によって非常に長い乱数表を生成し、その表を順にたどることで乱数っぽいものを実現します。つまり、結局はワンパターンです。
ワンパターンとはいえ、そのパターンが長ければ実用上は乱数とほぼ変わらなくなります。
また、表を読み始める場所を日時等で変えれば、見た目上ワンパターンではなくなります。

ここで重要になるのは、そのパターンの周期です。長ければ長いほど、乱数っぽくなります。たとえば、周期が６だと、１→４→６→３→５→２→１→４→６→３→５→２という規則的なものになってしまいます。これが周期が１万くらいだと、かなりいろいろなパターンを含むことになり、スタート地点を毎回変えれば、人間の目ではなかなかパターンを見つけられなくなります。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

疑似乱数を求める計算式には代表的なものがいくつかあります。
私が悩んでいたのは、以下の２つです。
・メルセンヌ・ツイスタ（長いんでMTと略します）
・Xorshift

MTは、現状で最強の疑似乱数です。周期が天文学的（およそで、、4の後ろに0が5378個ほどつきます）なのが売りです。計算時間もそれほどかかりませんが、少しメモリを食うのが欠点です。

対するXorshiftは、計算が簡単でメモリも食いません。ただし、周期はそれほどではありません（およそで、３の後ろに0が38個です）。

ちなみに振るサイコロはどちらも42億面体です。

周期的にはどっちもデッキのシャッフルくらいはできそうですね。
では、メモリ食わないXorshiftにしましょう。

・・・と一度は決めたものの、乱数の精度がちょっと気になり、
なんとなく迷っていました。

迷っていても仕方がない。
ほんとのところ、Xorshiftだとどれくらい周期に余裕があるのか計算で求めてみました。

完全ハイランダーだと、60の階乗（６０×５９×５８・・・３×２×１）
＝約8×10の81乗（およそで、８の後ろに0が81個）

え。
Xorshiftじゃ足りないんですね。（ガーン）


・・・というわけで普通に最強乱数のMTでシャッフルすることに決定しました。
にしてもマジックって結構奥深いんですね・・・。Xorshiftで不足とは。
orz