프리셀(Freecell) 게임에 자신있는 사람 모여라~ Freecell Project

웹 서핑중 재미있는 사이트 발견

바로 프리셀 프로젝트(Freecell Project)

이 사이트의 소개를 보자면...

마이크로소프트 윈도우즈에 포함된 프리셀(Freecell) 게임은 전 세계에서 가장 인기있는 게임 중 하나입니다. Windows 95, Windows 98 에 포함된 프리셀 게임의 게임 셋팅숫자는 32,000 가지였는데, 많은 이들이 32,000 가지의 게임이 모두 풀릴 수 있는지에 대해 의문을 가졌습니다. 그래서 시작된 것이 프리셀 게임풀기 프로젝트 였고, 각각의 사람들이 자신이 풀어 본 게임 넘버를 리포팅하고, 풀리지 않는 게임은 다른 사람들이 풀도록 하는 방식이었습니다. 그리고 결국 최후까지 풀리지 않던 게임은 #11,982 였고, 인공지능인 휴리스틱 서치(Heuristic Search) 프로그램을 통해 확인한 결과 어떠한 방법으로도 풀 수 없다는 것이 증명되었습니다. (From Wikipedia)

Windows XP에서는 1,000,000 가지의 프리셀 게임 셋팅이 제공됩니다. Freecell 프로젝트는 이 백만가지의 게임 중 사람이 풀 수 있는 셋팅이 몇 가지인지 확인해 보는 프로젝트입니다. -_-; 사이트에 접속하면 아직 풀리지 않은 프리셀 게임이 주어지고, 이 게임을 풀게되면 해당 넘버의 게임셋팅은 풀렸다는 기록이 서버에 저장됩니다. 이런식으로 게임을 반복하여 사람이 풀수있는 게임들이 백만가지의 경우 중 얼마나 되는지 알아내는 것이 목표입니다. 풀수있는 (Solvable) 목표수치는 99% 이며, 자신이 풀어본 게임 넘버는 자동으로 저장되고, 아직 풀리지 않은 게임 셋팅이 제공됩니다.

뭐 이런 식이다...

새로 시작한 프로셀 6연승을 달리다가 1 패... 크흑...

심심한 사람은 가끔 위의 웹 사이트에 접속해서 프리셀을 한게임씩 해보는 것도 재미있을 것 같다. 로그인을 하면 자신의 계정으로 푼 문제 넘버가 저장되지만, 굳이 로그인을 하지 않아도 된다.
 
PS) 보통 프리셀 문제는 다항시간 내에 풀수 있으나, 4*n 개의 카드로 임의로 생성되는 게임을 일반화해서 푸는 알고리즘은 NP Hard 에 속하는 것으로 알려져 있다. ( 2000년 증명되어 2001 년 논문으로 출간 ) 풀 수 있는 프리셀 게임들을 자동으로 풀어주는 다양한 프로그램들도 공개되어 있는데, 그중 하나는 여기서 다운받아 볼 수 있다.