さいころの目
XBOX360版のカルドセプトで、さいころの目が「偶数→奇数→偶数→奇数」と繰り返す不具合がありました。
http://blog.livedoor.jp/dqnplus/archives/870664.html
二人で交互にプレイする場合、片方は {1, 3, 5}の目のみ、もう片方は {2, 4, 6} の目のみ出ることになるので、ゲームにならない、結構致命的な不具合です。うっはぁ、これは惨いなぁ、、という話をお昼休みに同僚に話してました。
猫：（かくかくしかじか）なんだって〜。
同僚：なんじゃそりゃ！
猫：どういうふうに作っちゃったのかしらね〜。
同僚：まったく、どんなふうに作ったら・・・あぁ、線形合同法かも。
猫：あっ！ そっか、最下位ビットが0,1,0,1 になるっけ。
線形合同法というのは、疑似乱数を作るアルゴリズムの一つで、C の rand関数 とかに利用されています。ただ、ちょっと癖（というか欠点）があるので使い方には要注意です。とりあえず "百聞は一実行にしかず" なので、実行してみましょう。
| LCGs constA constB constM last | constA ← 13. constB ← 5. constM ← 12. last ← 8. LCGs ← [ last ← constA * last + constB \\ constM]. Transcript cr; show: 'A=13 B=5 M=12 X0=8'. 15 timesRepeat: [ Transcript cr; show: LCGs value ]
LCGs という変数に束縛してるブロックが、線形合同法のアルゴリズムです。（Smalltalk の 2項演算には、演算子の優先順位がなく左から順番に評価されるのに注意。\\ は余りを求める演算子）。
これの実行結果はこんな感じです。
A=13 B=5 M=12 X0=8 1 6 11 4 9 2 7 0 5 10 3 8 1 6 11
このパラメータの場合、12個周期で同じ並びの繰り返しになります。また、一見乱数のように見えても、奇数・偶数の繰り返しになっています。なるほどね〜。
線形合同法 による疑似乱数は、
- 周期性がある（最大で constM の周期にしかならない）
- 下位ビットのランダム性が非常に低い
という欠点があります。特に最下位ビットは、常に同じビットになるか、0と1が交互に出るかのどちらかです。
* * *
多分、カルドセプトのプログラマは 何にも考えずに ライブラリの疑似乱数生成関数 を使っちゃって、それが線形合同法をつかってた・・ってオチだと思います。
猫もへっぽこプログラマなので*1、全然アルゴリズムを知らない（勉強しようとしない）悪いプログラマなのですが、猫が新人の時は、この手の「知らないと痛い目を見る」問題は先輩がいろいろ叩き込んでくれました。そうしていろいろ覚えていったものだけど、そういうゆとりがあるほうが今の業界では珍しいから 「プログラマとしての基本」を叩き込まれないプログラマが増えているのかな、とか思ったり。
せつないにゃ〜。
