클론다이크 솔리테어의 '이론적 한계'를 찾는 사람들 – 현재 기록 8.590%

윈도우에 기본으로 깔려 있던 그 카드게임 이야기

예전 윈도우 PC 켜면 늘 있던 카드 게임 기억나세요? 스페이드·하트·다이아몬드·클로버 네 가지 무늬를 순서대로 쌓아 올리는 그 게임, 정식 이름이 클론다이크(Klondike) 솔리테어예요. 많은 분들이 '시간 때우는 게임' 정도로 생각하지만, 사실 이 게임은 수십 년째 "승률의 이론적 상한선은 얼마인가?"라는 수학·컴퓨터과학 난제로 연구되고 있습니다. 놀랍죠?

이번에 소개할 프로젝트는 GitHub의 dacracot/Klondike3-Simulator라는 오픈소스 시뮬레이터인데요, 클론다이크 3장 뽑기 룰(덱에서 한 번에 3장씩 넘기는, 윈도우 기본판과 같은 규칙)의 최적 전략을 찾기 위한 도구예요. 현재까지 기록된 최고 승률이 8.590%입니다. 즉, 100판 중 8~9판 정도만 이길 수 있다는 뜻이에요.

왜 이게 어려운 문제일까

솔리테어가 풀기 어려운 이유는 정보가 숨겨져 있기 때문이에요. 체스나 바둑은 모든 말의 위치가 보이잖아요? 그래서 '완전정보 게임'이라고 불러요. 그런데 클론다이크는 카드 더미(stock) 안에 뒤집혀 있는 카드들이 뭔지 모르는 상태에서 플레이해야 해요. 이걸 '불완전정보 게임'이라고 합니다. 포커처럼요.

거기다 한 판을 끝까지 돌려봐야 이 판이 애초에 클리어 가능한 판이었는지조차 알 수 있어요. 수학자들은 "신이 모든 카드를 미리 봤다면 이길 수 있는 판의 비율(god-mode 승률)"을 대략 82~83% 정도로 추정해요. 반면 사람이 실제 플레이하듯, 숨겨진 카드를 모르고 플레이했을 때의 최적 승률은 아직 정확히 모릅니다. 이 프로젝트의 8.59%는 특정 전략을 대량의 샘플로 시뮬레이션한 결과고, 더 좋은 알고리즘이 나오면 이 숫자가 갱신될 수 있어요.

시뮬레이터는 어떻게 동작할까

이런 종류의 시뮬레이터는 대략 이런 구조예요. 먼저 무작위로 카드를 섞어 수백만 판을 생성합니다. 그다음 정해진 전략 규칙(policy)에 따라 각 판을 자동으로 플레이해요. 예를 들어 "킹이 놓일 빈 칸이 생기면 우선 비워둔다", "에이스가 나오면 즉시 파운데이션에 올린다", "뒤집힌 카드를 가장 많이 열 수 있는 수를 고른다" 같은 규칙들이죠. 판이 끝나면 승패를 기록하고, 수많은 판의 통계를 내서 해당 전략의 평균 승률을 구합니다.

여기서 핵심은 전략의 표현력과 탐색 깊이예요. 단순 휴리스틱(경험칙)만으로는 한계가 있어서, 일부 연구자들은 몇 수 앞을 미리 시뮬레이션해보는 '룩어헤드(look-ahead)'를 넣거나, 몬테카를로 트리 탐색(MCTS)처럼 알파고가 쓰던 기법을 변형해서 적용하기도 해요. 이 저장소는 비교적 단순한 규칙 기반 탐색을 빠르게 돌리는 쪽에 초점을 맞춘 것으로 보입니다.

비슷한 연구들과의 위치

클론다이크 승률 연구의 고전은 2008년 비요른 헬거슨 같은 연구자들의 시뮬레이션, 그리고 UCLA의 로널드 그레이엄 그룹 등에서 나온 분석들이에요. 최근엔 강화학습(Reinforcement Learning)으로 이 문제를 푸는 시도도 많습니다. 알파제로 계열 기법을 카드게임에 적용하는 연구가 늘고 있거든요. 프리셀(FreeCell)은 거의 모든 판이 풀린다고 알려져 있고, 스파이더 솔리테어는 난이도 단계별로 승률 차이가 커요. 클론다이크는 그 사이 어딘가에 위치한, 아직 완전히 정복되지 않은 게임입니다.

한국 개발자에게 어떤 의미가 있을까

실무에 직접 쓸 일은 많지 않아요. 하지만 이런 프로젝트는 알고리즘과 확률적 사고를 훈련하기에 정말 좋은 소재예요. 몬테카를로 시뮬레이션, 게임 트리 탐색, 휴리스틱 설계 같은 개념은 추천 시스템, 광고 최적화, 자율주행 경로 계획 등 현업 문제에도 그대로 쓰이거든요. 주말 사이드 프로젝트로 "나만의 솔리테어 AI 만들기"를 해보면서 멀티프로세싱, 성능 프로파일링, 통계 분석을 실전으로 배우는 것도 좋은 방법이에요.

또 하나, 이런 문제는 LLM(대형 언어모델)이 잘 못 푸는 영역이라는 점도 흥미로워요. 수많은 경우의 수를 탐색해야 하는 조합 최적화 문제는 여전히 전통적인 알고리즘이 훨씬 강합니다. 모든 문제가 AI로 풀리는 건 아니라는 걸 상기시켜 주죠.

마무리

게임 하나에 수학자와 프로그래머들이 수십 년간 달려들고 있다는 사실이, 저는 볼 때마다 신기해요. 여러분은 어린 시절 윈도우에서 솔리테어를 했을 때, 그게 최악의 경우 수십 억 번 카드를 돌려봐야 최적해가 나오는 난제라는 걸 상상이나 하셨나요? 작은 문제라도 깊이 파면 연구가 된다는 걸 보여주는 좋은 예시 같아요.