Windows FreeCellゲームのカードシャッフルアルゴリズム
(solitairelaboratory.com)多くの方がプレイしたことのあるWindowsのFreeCellは、カードをランダムに並べ、それぞれのカード配置に番号が付いています。同じ番号を選ぶと、同一のカード配置になります。
Windows 2000以前までは1〜32,000番まででしたが、XP以降は1,000,000番までに増えました。
番号を入力したときにカード配置を生成するアルゴリズムは公開されており、ほかのFreeCellプログラムでも使われています。
このアルゴリズムは短いCコードで実装されており、MSのコンパイラで実装された rand() 関数と srand() 関数に依存しています.
8件のコメント
タグ兄さん、お上手ですね
本来、乱数生成アルゴリズムは random に見えても、実際にはそうではない pseudo-random number の数列を生成する漸化式を使います。各
rand()関数の実装ごとに方式は異なりますが、最初の seed が同じなら、その後に続く乱数列が同一になることは、ほぼすべてのアルゴリズムに共通する特性です。したがって、カード配列アルゴリズムが deterministic であるなら、すべてのカード配列は seed によって deterministic に決まるわけです。少し話が脱線しますが、どれだけランダムに見える pseudo-random number を生成できるかという点も、長年にわたる研究テーマの一つでした。TAOCP Vol.2 でもこの内容が簡単に扱われています。
実際、コンピューターには真のランダムという概念はありません。
そのため、通常は人の行動をms単位で測定し、これをランダム seed として使います。
乱数は現在時刻のタイムスタンプを使っているものだと思っていましたが、勘違いしていましたね（笑）。共有ありがとうございます。
初期化するときに seed として時間を使うことはよくありますよね。時間は常に変化していますから。
ちなみに、Windowsのヘルプには「証明はされていないが、ここでプレイするゲームにはすべて解法がある」と書かれていますが、複数の人の試みによれば、11982番はいまのところクリア不可能だと知られています。
32,000番以降にも、146692、186216、455889、495505、512118、517776、781948番など、クリア不可能だと知られているカード配置があります。
いや、これをどうやって書き留めておいて解けないのか突き止めたんでしょう？ すごい執念のある人が多いですね！
怖い人たち……！