윈도 프리셀(Freecell) 게임의 카드 섞기 알고리즘
(solitairelaboratory.com)많은 분들이 플레이 해 보셨을 윈도의 프리셀은 카드를 무작위로 배열하고, 각 카드 배열마다 번호가 붙어있습니다. 같은 번호를 선택하면 동일하게 카드가 배열되죠.
윈도 2000 이전까지는 1~32,000번까지 있었지만 XP 이후로 1,000,000번까지 늘어났습니다.
번호를 입력했을 때 카드 배열을 생성하는 알고리즘은 공개되어 있어 다른 프리셀 프로그램들에서도 사용됩니다.
이 알고리즘은 짧은 C 코드로 구현되었고, MS의 컴파일러에서 구현한 rand() 함수와 srand() 함수에 종속되어 있습니다.
원래 난수 발생 알고리즘은 random인 듯 보이지만 실은 그렇지 않은 pseudo-random number의 수열을 발생시키는 점화식을 사용합니다. 각 rand() 함수 구현마다 방식은 다르지만, 첫 번째 seed가 같으면 그 뒤에 따라 나오는 난수열이 동일함은 거의 모든 알고리즘이 공통으로 갖는 특성입니다. 그러니 카드 배열 알고리즘이 deterministic이라면 모든 카드 배열은 seed에 의해 deterministic으로 정해지는 셈이죠.
살짝 주제에서 벗어나는 이야기지만, 얼마나 임의적으로 보이는 pseudo-random number를 생성할 수 있겠느냐도 오랜 연구 주제 중 하나였습니다. TAOCP Vol.2에서도 이 내용을 간략하게 다룹니다.
참고로 윈도 도움말에는 “증명되지는 않았지만 여기에서 플레이하는 게임은 모두 해결법이 있습니다”라고 쓰여있으나, 여러 사람들의 시도에 따르면 11982번은 지금까지는 깰 수 없는것으로 알려져있습니다.
32,000번 너머에도 146692, 186216, 455889, 495505, 512118, 517776, 781948번 등 깰 수 없다고 알려진 카드 배열들이 있습니다.