ここしばらく、月刊で「日経ソフトウェア」へHTML5に関する連載をさせていただいています。毎回、HTML5のAPIや、ゲームのアルゴリズムを紹介していたのですが、先日、Twitterで読者の方から、どや顔で紹介した、Fisher-Yatesアルゴリズムが間違っているとのご指摘を受けました。ちなみに、Fisher-Yates法とは、配列をシャッフルする際に用いるアルゴリズムで、非常に少ない手順でよりランダムに並び変えることができます。

それで、改めて調べてみると・・・私が書いた方法では、シャッフルの精度が下がってしまうことが分かりました。お恥ずかしい話です。

私が間違えて書いたコード:

// カードを定義
var cards = [];
for (var i = 0; i < 52; i++) {
  cards[i] = i;
}
// Fisher-Yatesアルゴリズムでシャッフルする
for (var i = 0; i < 52; i++) {
  var r = Math.floor(Math.random()*52);
  var tmp = cards[i];
  cards[i] = cards[r];
  cards[r] = tmp;
}

正しいFisher-Yatesアルゴリズムのコード:

// カードを定義
var cards = [];
for (var i = 0; i < 52; i++) {
  cards[i] = i;
}
// Fisher-Yatesアルゴリズムでシャッフルする
var n = cards.length;
for (var i = (n-1); i > 0; i--) {
  var r = Math.floor(Math.random()*(i+1)); // ---(*1)
  var tmp = cards[i];
  cards[i] = cards[r];
  cards[r] = tmp;
}

私が書き間違えたのが(*1)の部分です。このように、入れ替えるカードを選ぶときに、どこでも好きなところから取るよりも、まだ入れ替えていない部分からカードを取り出した方が、より良いシャッフル精度を出すことができるのです。ランダムの範囲を狭めることでより精度が出るというのは感覚的ではないので、よく考えないといけない点ですね。勉強になりました。

改めて調べてみて分かったのですが、私と同じように精度の出ないサンプルを載せている方が多くいました。多くの人が掲載しているからと言って、正しい訳ではないというのも、良い教訓でした。@MilkSoldierさんのご指摘に感謝です。

参考) http://d.hatena.ne.jp/bellbind/20081105/1225886625

Comments:
名無し上記アルゴリズムですが、i==0の時は必ずr==0となるためi>0にすべきではないでしょうか? (2016/03/20)
クジラ飛行机確かに。コードを修正しました。 (2016/03/30)
Name: