The Winnability of Klondike Solitaire and Many Other Patience Games

이 논문은 전이 테이블, 대칭성 깨기, 우세성 (dominance) 등 다양한 인공지능 기법을 활용한 범용 AI 프로그램 'Solvitaire'를 개발하여 35 가지의 73 개 솔리테이션 변형 게임의 승리 확률을 95% 신뢰구간 내에서 정밀하게 계산하고, 특히 'Klondike'의 승리율을 기존 결과보다 30 배 정밀하게 81.945% 로 규명했다고 요약할 수 있습니다.

핵심

솔리테어 (카드 게임) 의 운명: "이 게임은 정말 이길 수 있을까?"에 대한 답

이 논문은 우리가 매일 아침 커피를 마시며 하거나, 컴퓨터를 켜자마자 자동으로 뜨는 그 유명한 '클론다이크 솔리테어' (Windows 솔리테어) 가 정말로 이길 수 있는지, 그리고 그 확률이 얼마나 되는지에 대한 놀라운 답을 제시합니다.

저자들은 이 문제를 해결하기 위해 **'솔비테어 (Solvitaire)'**라는 이름의 초지능 AI 프로그램을 개발했습니다. 이 프로그램은 단순히 카드를 옮기는 것을 넘어, 게임의 모든 가능성을 계산하여 "이 게임은 81.9% 의 확률로 이길 수 있다"는 정밀한 결론을 내렸습니다.

이 복잡한 연구를 일반인도 쉽게 이해할 수 있도록 세 가지 핵심 비유로 설명해 드리겠습니다.

---

1. 미로 찾기: "모든 길을 다 걸어보는 AI"

솔리테어 게임은 마치 거대한 미로와 같습니다. 카드를 어떻게 배치하느냐에 따라 길이 열리기도 하고, 막히기도 합니다.

• 일반적인 플레이어: 우리는 미로에서 길을 찾을 때, "아, 여기는 막혔네"라고 생각하면 뒤로 돌아서 다른 길을 찾습니다. 하지만 실수할 수 있고, 가장 짧은 길을 찾지 못할 수도 있습니다.
• 솔비테어 (AI) 의 접근: 이 AI 는 미로에 들어서는 순간, 모든 가능한 길을 동시에 탐색합니다. "이 길로 가다가 막히면, 그전으로 돌아서 저 길로 가보자"를 수백만 번 반복합니다.
  • 만약 AI 가 모든 길을 다 찾아봐도 출구가 없다면, 그 게임은 100% 이길 수 없는 게임입니다.
  • 만약 출구를 하나라도 찾으면, 그 게임은 이길 수 있는 게임입니다.

이 논문은 이 AI 를 이용해 35 가지 다른 종류의 솔리테어 게임 (총 73 가지 변형) 에 대해 "이길 확률"을 계산했습니다. 마치 "이 미로에서 100 명 중 82 명은 탈출할 수 있다"고 통계적으로 증명해낸 셈입니다.

2. "생각하는 플레이어" vs "눈 가린 플레이어"

논문에서 언급한 가장 중요한 개념 중 하나는 '생각하는 플레이어 (Thoughtful)' 버전입니다.

• 일반적인 상황: 우리가 카드를 할 때, 뒤집힌 카드 (숨겨진 카드) 가 무엇인지 모릅니다. 운이 좋아야 이길 수 있죠.
• 이 연구의 상황: 저자들은 AI 에게 **"숨겨진 카드의 정체를 미리 다 알려주겠다"**고 했습니다. 마치 눈 가린 상태에서 게임을 하는 게 아니라, 모든 카드가 투명하게 보이는 상태에서 "어떤 순서로 카드를 옮겨야 이길 수 있을까?"를 계산한 것입니다.

이것은 게임의 **최대 가능성 (Upper Bound)**을 보여주는 것입니다. "카드의 정체를 다 안다면 이 게임은 81.9% 이길 수 있다"는 뜻이지, 우리가 눈 가리고 할 때의 확률과는 다릅니다. 하지만 이 수치는 "이 게임이 얼마나 어려운지"를 알려주는 중요한 기준이 됩니다.

3. "지혜로운 규칙"과 "실수 없는 증명"

AI 가 모든 길을 다 탐색하면 시간이 너무 오래 걸립니다. 그래서 저자들은 AI 에게 **지혜로운 규칙 (Dominance)**을 가르쳤습니다.

• 비유: 미로에서 "벽을 뚫고 지나가는 길"은 애초에 존재하지 않으니 굳이 찾아보지 말라고 알려주는 것과 같습니다.
  • 예: "카드를 기둥 (Foundation) 에 올릴 수 있다면, 무조건 올려야 해. 나중에 다시 내려올 필요는 없어."
• 이 논문은 단순히 규칙을 적용하는 것을 넘어, "이 규칙이 정말로 옳은가?"에 대한 수학적인 증명을 처음으로 제시했습니다. 이전에는 "아마도 맞을 거야"라고 추측했던 규칙들을, "이론적으로 100% 안전하다"고 증명해낸 것입니다.

주요 발견: 우리가 놀랄 만한 사실들

이 연구로 밝혀진 몇 가지 놀라운 사실들은 다음과 같습니다:

1. 클론다이크 (Windows 솔리테어) 의 운명:

   • 숨겨진 카드를 다 안다면, **약 81.9%**의 게임은 이길 수 있습니다.
   • 이전 연구들은 이 수치가 84% 정도일 거라고 추측했지만, 오차 범위가 컸습니다. 이번 연구는 오차 범위를 30 배나 줄여서 매우 정밀하게 (±0.08%) 계산했습니다.
   • 흥미로운 점: 카드를 한 번에 1 장씩 뽑으면 이길 확률이 90% 이상으로 올라가지만, 3 장씩 뽑는 (일반적인) 방식은 확률이 떨어집니다. 카드를 한 번에 많이 뽑을수록 게임이 훨씬 어려워진다는 뜻입니다.

2. 이길 수 없는 게임도 있다:

   • 어떤 게임은 99.9% 이상 이길 수 있지만 (예: 프리셀), 어떤 게임은 0.0001% 정도만 이길 수 있습니다 (예: 브리티시 캐니스터).
   • 특히 '브리티시 캐니스터'는 100 만 번 중 1 번도 안 될 정도로 어렵습니다.

3. 실수 없는 검증:

   • 이 AI 프로그램은 기존에 있던 다른 솔리테어 해결 프로그램들의 **버그 (오류)**를 찾아냈습니다. 마치 "너는 여기서 실수했어"라고 지적하며, 더 정확한 답을 찾아낸 것입니다.

결론: 왜 이 연구가 중요한가요?

이 논문은 단순히 "카드 게임 이기는 법"을 알려주는 것이 아닙니다.

• 인공지능의 힘: 복잡한 규칙과 수많은 경우의 수를 가진 문제를 해결할 때, AI 가 어떻게 '지혜'를 발휘하여 효율적으로 문제를 푸는지 보여줍니다.
• 수학의 즐거움: "우리가 매일 하는 이 게임, 정말로 이길 수 있을까?"라는 단순한 호기심이, 수학과 컴퓨터 과학의 정밀한 분석을 통해 어떻게 정확한 숫자로 답이 나올 수 있는지를 보여줍니다.

마치 우주 탐사가 별의 위치를 정확히 계산하듯, 이 연구는 카드 게임의 우주에서 "이길 수 있는 별"과 "이길 수 없는 암흑"을 정확히 지도로 그려낸 것입니다. 이제 여러분은 솔리테어를 할 때, "아, 이 게임은 81.9% 확률로 이길 수 있는 게임이구나"라고 생각하며 즐기실 수 있습니다!

기술 요약

논문 요약: Klondike 솔리테어 및 기타 많은 패티언스 게임의 승리 가능성 (The Winnability of Klondike Solitaire and Many Other Patience Games)

이 논문은 찰리 블레이크 (Charlie Blake) 와 이안 젠트 (Ian Gent) 가 저술하여 2026 년 2 월 Journal of Artificial Intelligence Research (JAIR) 에 게재된 연구로, 다양한 솔리테어 (패티언스) 카드 게임의 승리 확률을 정밀하게 계산하기 위해 개발된 범용 인공지능 솔버 'Solvitaire'와 그 결과를 제시합니다.

1. 연구 배경 및 문제 정의

• 배경: 솔리테어 (패티언스) 게임은 200 년 이상 인기 있는 취미이며, 마이크로소프트 윈도우 솔리테어 (Klondike) 만 하루에 1 억 번 이상 플레이됩니다.
• 문제: 특정 게임이 무작위로 배분되었을 때 승리할 확률 (Winnability) 은 오랫동안 플레이어와 수학자들의 관심사였으나, 정확한 수치는 알려져 있지 않았습니다. 특히 Klondike 의 승리 확률에 대한 무지는 "응용 수학의 수치스러운 부분 (embarrassments of applied mathematics)"으로 불릴 정도였습니다.
• 기존 연구의 한계: 이전 연구들은 특정 게임에 맞춘 전용 솔버를 사용하거나, 애호가들에 의한 경험적 추정에 의존했습니다. 이로 인해 신뢰구간이 넓거나, 게임 간 비교가 어려웠으며, Klondike 의 경우 신뢰구간이 ±3% 수준으로 매우 넓었습니다.

2. 방법론: Solvitaire 솔버

저자들은 35 가지 다른 단일 플레이어 카드 게임의 73 가지 변형에 대해 승리 확률을 계산할 수 있는 범용 AI 솔버인 'Solvitaire' 를 개발했습니다.

• 핵심 알고리즘: 깊이 우선 탐색 (Depth-First Search, DFS) 기반의 백트래킹 알고리즘을 사용합니다.
• AI 기법 활용: 탐색 효율을 극대화하기 위해 다음과 같은 AI 기법들을 통합 적용했습니다.
  • 전위 테이블 (Transposition Tables): 동일한 상태의 재방문을 방지하여 중복 계산을 제거합니다.
  • 대칭성 깨기 (Symmetry Breaking): 테이블의 카드 더미 순서 등 본질적으로 동일한 상태를 식별하여 탐색 공간을 축소합니다.
  • 우위성 (Dominances): 특정 상황에서 특정 수를 무조건 수행하거나 수행하지 않아도 된다는 논리적 규칙을 적용하여 불필요한 분기를 제거합니다. (본 논문에서는 두 가지 주요 우위성에 대한 최초의 정밀한 증명도 제시했습니다.)
  • 스트림라이너 (Streamliners): 해가 존재할 가능성이 높은 경로를 우선적으로 탐색하여 승리 가능한 경우를 빠르게 찾되, 실패 시 완전 탐색으로 전환하는 휴리스틱 기법입니다.
• 유연한 규칙 정의: 게임 규칙을 JSON 형식으로 정의하여, Solvitaire 가 게임 엔진을 수정하지 않고도 다양한 규칙을 가진 게임을 처리할 수 있도록 했습니다.
• 시뮬레이션 방식: 'Thoughtful' 변형을 가정했습니다. 이는 숨겨진 카드의 위치와 무늬를 플레이어가 처음부터 알고 있다는 가정으로, 물리적 카드 게임의 'peeking' 또는 전자 게임의 'undo' 기능을 통한 정보 획득을 모델링한 것입니다.

3. 주요 기여 및 결과

3.1 Klondike 의 승리 확률 정밀 측정

• 결과: Klondike (Thoughtful 변형) 의 승리 확률을 81.945% ± 0.084% 로 계산했습니다.
• 의의: 이전 최고의 결과 (약 84.175% ± 2.998%) 에 비해 신뢰구간을 30 배 이상 축소했습니다. 이는 Klondike 승리 확률에 대한 불확실성을 획기적으로 줄인 것입니다.
• 변형 분석: 덱에서 카드를 뽑는 수 (Draw Size) 가 1 에서 13 까지 변할 때, 그리고 'Worrying back'(기초로 보낸 카드를 다시 테이블로 되돌리는 것) 이 허용될 때와 그렇지 않을 때의 승리 확률 변화를 정밀하게 분석했습니다. 예를 들어, Draw 3 일 때 승리 확률은 약 81.9% 이지만, Draw 13 일 때는 0.6% 로 급감합니다.

3.2 광범위한 게임에 대한 새로운 데이터

• 범위: Klondike, Canfield, FreeCell, Spider, Black Hole 등 35 가지 게임의 73 가지 변형에 대해 실험을 수행했습니다.
• 새로운 결과: 연구 대상 게임 중 상당수는 이전에 정밀하게 분석된 적이 없거나, 기존 결과보다 신뢰구간이 훨씬 좁은 새로운 데이터를 제공했습니다.
  • 예: Canfield (Thoughtful) 는 71.245% ± 0.031%, FreeCell 은 99.998881% ± 0.000207% 등.
• 오류 발견 및 수정: 기존에 존재하던 전용 솔버 (Birrell 의 Klondike 솔버, Wolter 의 Canfield 솔버 등) 에서 발견된 치명적인 버그 (특히 '우위성' 규칙 적용 오류) 를 Solvitaire 를 통해 발견하고 수정했습니다. 이로 인해 기존 연구 결과의 신뢰성이 재평가되었습니다.

3.3 이론적 증명

• 패티언스 게임에서 널리 사용되던 두 가지 핵심 '우위성 (Dominance)' 규칙에 대해 최초로 정밀한 수학적 증명을 제시했습니다. 이는 향후 AI 기반 솔버 개발의 이론적 토대를 강화했습니다.

4. 연구의 의의 및 결론

1. 응용 수학의 오랜 미해결 문제 해결: Stanislaw Ulam 이 몬테카를로 방법을 고안할 때 동기가 되었던 솔리테어 게임의 승리 확률 문제를, 그가 고안한 방법론을 현대적인 AI 기술과 결합하여 정밀하게 해결했습니다.
2. 범용 AI 의 성공 사례: 특정 게임에 최적화된 전용 솔버가 아닌, 범용 AI 솔버가 여러 게임에서 최첨단 (State-of-the-art) 성능을 발휘할 수 있음을 증명했습니다.
3. 데이터의 신뢰성: 기존 애호가나 연구자들의 데이터보다 훨씬 좁은 신뢰구간 (±0.1% 이내) 을 제공하여, 해당 게임들의 난이도와 전략적 깊이에 대한 이해를 깊게 했습니다.
4. 미래 과제: 본 연구는 모든 카드를 알 수 있는 'Thoughtful' 변형에 국한되었습니다. 실제 게임에서 카드를 모르고 플레이할 때의 승리 확률 (불완전 정보 게임) 은 여전히 해결되지 않은 난제로 남아 있으며, 이는 향후 연구 과제로 남았습니다.

결론적으로, 이 논문은 Solvitaire 라는 단일 AI 시스템을 통해 다양한 솔리테어 게임의 승리 가능성을 정량화하고, 기존 연구의 오류를 수정하며, 이론적 증명을 제공함으로써 솔리테어 게임 분석 분야에서 획기적인 진전을 이루었습니다.