2026/11/12 - [노트정리/알고리즘] - 프리셀(FreeCell) 풀이 알고리즘 - 게임 규칙과 길찾기 문제 (1)
앞서 글에서는 프리셀의 규칙을 살펴보았고, 프리셀 풀이를 길찾기 문제로 정의할 수 있다는 걸 알아보았습니다.
이번 시간에는 프리셀에서 현재의 판만 보고 그 다음 수를 고르는 방법을 세 가지 알아보겠습니다. (1) 둘 수 있는 수 가운데 아무거나 고르는 무작위 방법 (2) 파운데이션에 올릴 수 있는 카드부터 올리는 방법, 그리고 (3) 수를 둔 뒤의 판에 점수를 매겨서 가장 좋아 보이는 수를 고르는 그리디(greedy) 방법입니다.
측정 방법
세 방법을 윈도우 프리셀 1번부터 32000번까지 32,000판을 모두 풀게 해서 비교했습니다. 프리셀 풀이 연구에서 Microsoft 32K라고 부르는 묶음인데, 이 가운데 풀 수 없는 판은 11982번 하나라고 알려져 있습니다(Elyasaf 등, IEEE TCIAIG 2012).
수는 카드를 한 장씩 옮긴 횟수로 셉니다. (여러 장을 한 번에 옮기는 수는 앞서 글의 그림 3처럼 한 장씩 나눠 옮기는 횟수로 풀어서 세는데, 앞서 글의 영상에서 1번 판을 푼 112수도 여러 장을 한 번에 옮긴 17수를 이렇게 풀어서 세면 168수가 됩니다.)
판마다 카드를 옮기는 수의 한계는 1만 번으로 정했습니다. 고를 수 있는 수가 여럿이면 무작위로 하나를 고르는데, 난수는 판 번호로 정해서 카드를 옮기는 수를 재현 가능하게 했습니다. 그리고 푼 판은 처음 판부터 수순을 다시 두면서 모든 수가 규칙에 맞는지 검사했습니다.
걸린 시간은 따로 측정하지 않기로 하였습니다. 프리셀을 동작시키는 컴퓨터의 스펙 마다 다르기 때문이며, 대신 방법 마다 카드를 옮기는 횟수를 비교해 보겠습니다.
무작위로 고르기
프리셀을 풀 때 가장 단순한 방법은 아무 곳으로 옮겨보는 것 입니다. 여기서는 보드 판을 보고, 옮길 수 있는 경우 중에 무작위로 옮겨보기로 했습니다.
신기하게도 이렇게 해도 약 2퍼센트 정도는 프리셀 게임을 풀 수 있습니다(32,000판 중 638판이 풀이 완료). 당연히 풀이가 되긴 하지만 다른 방법보다는 훨씬 여러번 카드를 옮겨야 합니다. 풀이 한 경우에 대해서 카드를 옮긴 수의 중앙값이 853수로, 앞서 글의 영상에서 1번 판을 푼 168수와 비교하면 훨씬 많이 옮겨야 하는 것 입니다.
못 푼 판 가운데 17,880판은 둘 수 있는 수가 하나도 없게 되어서 막혔는데, 막히기까지 옮긴 수의 중앙값은 18수였습니다. 나머지 13,482판은 카드를 1만 번 옮길 때 까지 끝나지 않았습니다.
앞서 글의 1번 판은 7수 만에 아래 그림처럼 막혔습니다. 프리셀 칸 4개가 2♥, 3♦, 6♣, 8♠로 모두 찼고, 프리셀 칸의 카드와 열의 맨 아래 카드 중에 다른 열이나 파운데이션으로 옮길 수 있는 카드가 하나도 없습니다.

<그림 1. 무작위로 7수를 두고 막힌 1번 판>
파운데이션에 먼저 올리기
그렇다면 파운데이션에 올릴 수 있는 카드가 있을 때 그 카드부터 올리면 어떨까요? 올릴 카드가 없을 때만 무작위로 고르게 해 보았습니다.
프리셀에서 파운데이션은 오른쪽 위 4칸을 말 합니다. 무늬별 카드를 A부터 K까지 순차적으로 쌓는 곳입니다. 예를 들어 1번 게임 판에서 6열의 3♦와 2♣를 프리셀 칸으로 옮기면 A♣가 맨 아래에 나옵니다. 이 A♣는 아래 그림처럼 파운데이션에 올릴 수가 있습니다.

<그림 2. 3♦와 2♣를 프리셀 칸으로 옮긴 뒤 A♣를 파운데이션에 올리는 1번 판>
이런 식으로 파운데이션에 먼저 올리기로 풀어 보면, 약 2퍼센트(32,000판 중 597판 풀이 완료)가 풀이 되어 무작위와 비슷했습니다. 대신 푼 판에서 카드를 옮긴 수의 중앙값은 853수에서 439수로 줄었는데, 이동 횟수의 분포는 이 글의 아래에서 방법별 비교 그림으로 보겠습니다.
여담으로 두 방법이 공통적으로 푼 판은 66판뿐입니다. 하지만 두 방법이 푸는 판이 서로 아무 관계가 없다면 공통적으로 푼 판은 12판 정도입니다(무작위가 푼 638판의 1.87%). 실제 66판은 그 5배가 넘습니다. 처음 판에서 A 위에 쌓인 카드가 적은 판일수록 어느 방법으로든 잘 풀리기 때문입니다.
그리디
그리디는 먼 미래는 생각하지 않고, 눈앞의 이득이 가장 큰 선택을 하는 방법입니다. 여기서는 카드를 이동하는 선택지를 하나 고릅니다. 그 선택을 했을 때, 판의 점수를 눈앞의 이득으로 봅니다. 여러 선택지가 있을 텐데, 이 이득이 가장 큰 선택지만 고르는 겁니다. 이 글에서 판의 점수를 계산할 때, 그 판이 목표에서 얼마나 먼지를 어림하는 값인 휴리스틱(heuristic)을 씁니다.
프리셀에서 그리디를 위한 점수 계산 방법으로는 HSDH(Heineman's Staged Deepening Heuristic)를 썼습니다(Elyasaf 등, IEEE TCIAIG 2012). 선택지를 고를 때 각 선택에 대한 점수는 아래와 같이 계산합니다.
- 각각의 무늬마다 파운데이션에 다음으로 올릴 카드를 찾습니다. 예를 들어 스페이드 자리에 A♠까지 올라가 있으면 다음에 올릴 카드는 2♠입니다.
- 그 카드(여기서는 2♠)가 열에 있으면 그 위에 쌓인 카드 개수를 셉니다. 프리셀 칸에 있으면 0장으로 칩니다.
- 네 가지 무늬에 대해서 위와 같이 센 카드 개수의 총합이 HSDH가 됩니다.
- 이 때, 빈 프리셀 칸도 빈 열도 없으면, 다음 카드 위의 카드를 잠시 옮겨 둘 곳이 없어 빼내기가 더 어려우니 HSDH가 두 배가 됩니다.
즉, 이 휴리스틱에서 내가 어떤 카드를 옮긴다고 가정하고 난 후의 HSDH 점수를 식으로 쓰면 아래와 같습니다.
HSDH = k × (n♠ + n♥ + n♦ + n♣)
여기서 n♠는 스페이드의 다음 카드 위에 쌓인 카드 개수이고, n♥, n♦, n♣는 각각 하트, 다이아몬드, 클로버의 다음 카드 위에 쌓인 카드 개수입니다. k는 빈 프리셀 칸도 빈 열도 없으면 2, 아니면 1입니다.
HSDH는 다음 카드들 위에 쌓인 카드 개수라서, 작을수록 목표에 가까운 판입니다. 52장을 모두 올린 판은 0입니다. 그래서 그리디는 한 수마다 아래 최소화 문제를 풀어서 선택지를 고릅니다.
minm ∈ M HSDH(sm)
여기서 M은 지금 판에서 둘 수 있는 선택지들이고, sm은 선택지 m을 고른 뒤의 판입니다.
예를 들어 1번 판의 처음 판은 파운데이션이 비어 있으니 무늬마다 다음 카드는 A입니다. 아래 그림과 같이 A♦ 위에 4장(n♦ = 4), A♠ 위에 A♣를 포함해서 3장(n♠ = 3), A♣ 위에 2장(n♣ = 2), A♥ 위에 3장(n♥ = 3)이 쌓여 있습니다. 빈 프리셀 칸이 있으니 k = 1이고, HSDH = 1 × (4 + 3 + 2 + 3) = 12입니다.

<그림 3. 무늬마다 A 위에 쌓인 카드 개수를 더한 HSDH>
앞서 글의 그림 4에서 본 처음 판의 8가지 수에 대해서, 수를 둔 뒤의 HSDH를 구하면 아래 그림과 같습니다.

<그림 4. 처음 판의 8가지 수를 둔 뒤의 HSDH>
8가지 모두 프리셀 칸으로 카드를 빼는 수라서, 차이는 어느 카드를 빼는지에서 생깁니다. 3♦를 빼면 그 밑에 있는 A♠와 A♣ 위의 카드가 한 장씩 줄어들어서 HSDH가 10이 되고, 6♣나 8♣를 빼면 A♦나 A♥ 위의 카드가 한 장 줄어들어서 11이 됩니다. 나머지 다섯 장은 A 위에 있지 않아서 12 그대로입니다. 그래서 그리디는 3♦를 프리셀 칸으로 뺍니다.
한편, 지나왔던 판으로 되돌아가는 수는 고르지 않는데, 이런 규칙이 없으면 같은 카드를 두 자리 사이에서 왔다 갔다 하게 됩니다. 따라서 여기서는 이를 방지하는 규칙을 하나 더 두었습니다.
결과는 약 22퍼센트(32,000판 중 7,190판 풀이 완료)로 무작위 이동으로 푸는 것 보다 11배 넘게 풀었습니다. 푼 판에서 카드를 옮긴 수의 중앙값은 542수였습니다. 못 푼 판을 분석 해보면 아래와 같이 세 가지로 나누어 볼 수 있습니다.
- 둘 수 있는 수가 모두 지나왔던 판으로 되돌아 가는 수라서 멈춘 판: 16,423판(멈추기까지 옮긴 수의 중앙값 38수)
- 둘 수 있는 수가 하나도 없어서 막힌 판: 8,383판(중앙값 21수)
- 카드를 1만 번 옮기고도 끝나지 않은 판: 4판
그런데 HSDH는 다음 카드 위에 쌓인 카드 개수만 세기 때문에, 카드를 파운데이션에 올려서 다음 카드가 더 깊이 묻힌 카드로 바뀌면 오히려 커집니다. 그래서 그리디가 카드를 파운데이션에 올리지 않는 경우가 있습니다.
예를 들어 1번 판의 6수째가 그런 식 입니다. 다섯 수를 둔 뒤 A♠가 6열 맨 아래에 있는데, 이 A♠를 파운데이션에 올리면 스페이드의 다음 카드는 2♠가 됩니다. 2♠는 1열에서 4장 밑에 있어서 HSDH가 5에서 9로 커집니다. 반면 A♠를 3열의 2♥ 위로 옮기면 A♠가 여전히 맨 아래에 있으니 HSDH는 5 그대로입니다. 그래서 그리디는 A♠를 2♥ 위로 옮깁니다.

<그림 5. 6수째에 A♠를 파운데이션에 올리면 HSDH 9, 2♥ 위로 옮기면 5>
A♠는 14수째에 가서야 파운데이션에 올라가고, 1번 판은 17수 만에 아래 그림처럼 막힙니다. 파운데이션에 5장을 올렸지만 프리셀 칸이 3♦, 6♣, 4♦, 8♣로 모두 찼고 옮길 수 있는 카드가 없습니다.

<그림 6. 그리디로 17수를 두고 막힌 1번 판>
세 방법 비교
세 방법을 표로 비교하면 아래와 같습니다. 푼 비율의 ± 값은 95% 신뢰구간입니다.
| 방법 | 푼 비율 | 푼 판에서 옮긴 수(중앙값) | 못 푼 판이 끝난 방식 |
| 무작위 | 1.99% ±0.15%p(638판) | 853수 | 막힘 17,880판, 1만 번 13,482판 |
| 파운데이션 먼저 | 1.87% ±0.15%p(597판) | 439수 | 막힘 17,991판, 1만 번 13,412판 |
| 그리디(HSDH) | 22.47% ±0.46%p(7,190판) | 542수 | 지나왔던 판뿐 16,423판, 막힘 8,383판, 1만 번 4판 |
처음 판의 HSDH가 작은 판일수록 세 방법 모두 잘 풀었습니다. 처음 판의 HSDH는 A 4장 위에 쌓인 카드 개수의 합입니다.
| 처음 판의 HSDH | 판 수 | 무작위 | 파운데이션 먼저 | 그리디(HSDH) |
| 6 이하 | 3,574판 | 4.95% | 3.97% | 32.7% |
| 7~9 | 7,434판 | 2.37% | 2.68% | 28.0% |
| 10~12 | 9,673판 | 1.72% | 1.63% | 21.5% |
| 13~15 | 7,494판 | 1.28% | 0.97% | 17.8% |
| 16 이상 | 3,825판 | 0.60% | 0.65% | 13.7% |
푼 판에서 카드를 옮긴 수가 어떻게 퍼져 있는지는 아래 그림과 같습니다. 상자는 가운데 절반의 판이 들어가는 범위이고, 상자 안의 흰 선이 중앙값이며, 위아래 선 밖의 점은 다른 판보다 훨씬 많이 옮긴 판입니다.

<그림 7. 방법별로 푼 판에서 카드를 옮긴 수(세로축은 로그 눈금)>
파운데이션 먼저의 상자는 무작위의 상자와 거의 겹치지 않을 만큼 아래에 있어서, 푼 판에서 옮긴 수가 확실히 줄었다는 것을 알 수 있습니다. 같은 판끼리 비교해도 마찬가지인데, 두 방법이 공통적으로 푼 66판 가운데 58판에서 파운데이션 먼저가 더 적게 옮겼습니다. 그리디의 상자는 두 방법 사이에 있고, 그리디와 파운데이션 먼저가 공통적으로 푼 287판에서는 205판에서 파운데이션 먼저가 더 적게 옮겼습니다.
그리디가 무작위보다 훨씬 많이 풀지만, 무작위가 푼 판 중에서 312판은 그리디가 풀지 못했습니다. 그리고 풀 수 없는 11982번을 빼면 31,999판이 풀 수 있는 판이니, 그리디는 풀 수 있는 판의 4분의 3 넘게 놓치고 있습니다.
한 수 앞만 보면
세 방법은 한 번 둔 수를 되돌리지 않습니다. 프리셀에는 파운데이션에 올린 카드처럼 되돌릴 수 없는 수가 있어서, 지금 좋아 보이는 수가 나중에 막히는 판으로 이어지기도 합니다.
같은 HSDH를 쓰더라도 여러 수 앞을 내다보면 결과가 크게 달라지는데, Heineman의 staged deepening은 HSDH로 판의 순서를 정하면서 앞의 수를 여러 개 펼쳐 보는 탐색 방법으로 32,000판의 96%를 풀었습니다.
그리디를 그대로 쓰면서 앞을 내다보는 방법으로는 롤아웃(rollout)도 있습니다. 수마다 그 뒤를 그리디로 끝까지 두어 보고 결과가 가장 좋은 수를 고르는 방법입니다. 모든 카드를 펼쳐 놓고 하는 클론다이크에서는 점수로 고르는 그리디가 13.05%를 풀었는데, 롤아웃을 다섯 겹 쌓으니 70.20%를 풀었습니다(Yan 등, NIPS 2004, 다섯 겹은 200판에서 잰 값).
즉, 한 수 뒤의 판만 보고 수를 고르는 방법은 프리셀 연구에서 쓰는 휴리스틱을 써도 풀 수 있는 판의 4분의 1도 풀지 못합니다.
다음 글에서는 같은 HSDH를 쓰면서 막히면 되돌아가서 다른 수를 둘 수 있는 최선 우선 탐색(best-first search)을 살펴보고, 탐색이 있을 때와 없을 때를 같은 32,000판으로 비교해 보겠습니다.
'노트정리 > 알고리즘' 카테고리의 다른 글
| 프리셀(FreeCell) 풀이 알고리즘 - 게임 규칙과 길찾기 문제 (1) (0) | 2026.11.12 |
|---|---|
| 게임 24 풀이 (파이썬으로) (0) | 2024.04.03 |
| 네모로직 알고리즘 - 다양한 언어별 풀이 코드 (0) | 2019.09.09 |
| DBSCAN 자바 구현 실습 소스 코드 (4) | 2017.10.17 |
| 바이오인포매틱스 프로그래밍 연습 사이트 (0) | 2017.05.08 |
| 입력된 단어에서 모음의 순서만 역으로 바꾸는 프로그램 (0) | 2016.10.12 |
| 2차원 공간에서 퍼지 클러스터링(fuzzy clustering) 자바 구현 (0) | 2016.06.03 |
| 블로그의 스팸 덧글 검출하는 방법 - 자카드 유사도(Jaccard similarity). 자바 구현. (2) | 2016.06.03 |


