공돌이의 노트정리

안녕하세요. 오늘부터 몇 편에 걸쳐 카드 게임 프리셀(FreeCell)을 푸는 알고리즘을 살펴보고자 합니다.

예전에 스도쿠와 네모로직을 푸는 알고리즘을 다룬 적이 있는데요. 이번 연재에서는 프리셀을 푸는 탐색 알고리즘을 종류별로 살펴보고, 같은 판을 여러 방법으로 풀어서 어느 방법이 얼마나 잘 푸는지 비교해 보려고 합니다. 이런 과정 속에서 각 알고리즘의 작동 원리도 간략히 살펴보도록 하겠습니다.

이 글에서는 먼저 프리셀의 규칙을 살펴보고, 프리셀을 푸는 일이 왜 길찾기 문제로 정의할 수 있는지 알아보겠습니다.

프리셀 규칙

프리셀은 윈도우에 들어 있던 카드 게임입니다. 카드 52장을 8개의 열에 무작위로 펼친 후, 무늬를 맞추어 4개의 덱을 다 쌓아 올리는 게임입니다.

규칙을 글로만 읽으면 감이 잘 오지 않으니, 프리셀을 처음 보시는 분은 아래 영상을 먼저 보시길 추천합니다. 프리셀 게임 한 판에 대해서, 카드를 옮길 수 있는 선택의 순간에 어떤 수는 되고 어떤 수는 안 되는지를 따라가보도록 하겠습니다.

<그림 1. 윈도우 프리셀 1번 판의 처음 모습>

프리셀 보드는 그림과 같이 세 부분으로 나뉩니다.

• 열(cascade): 보드에서 아래 8줄입니다. 각 열에서는 맨 아래 카드 한 장만 옮길 수 있습니다.
• 프리셀 칸(free cell): 왼쪽 위 4칸입니다. 아무 카드나 한 칸에 한 장씩 잠시 놓아 둘 수 있습니다.
• 파운데이션(foundation): 오른쪽 위 4칸입니다. 무늬별 카드를 A부터 K까지 순차적으로 쌓으며, 게임 종료 조건은 52장 모두를 파운데이션에 올리는 것입니다.

열에서 열로 카드를 옮길 때는 규칙이 하나 있습니다. 옮기려는 카드보다 숫자가 하나 크고 색이 다른 카드 위에만 놓을 수 있습니다. 예를 들어 빨간색 7♦는 검은색 8♣ 위에는 놓을 수 있지만, 같은 빨간색인 8♦ 위나 숫자가 둘 차이 나는 9♣ 위에는 놓을 수 없습니다.

<그림 2. 같은 빨간색인 8♦ 위로는 옮길 수 없는 7♦>

카드가 하나도 없는 빈 열에는 아무 카드나 놓을 수 있습니다. 그래서 빈 열은 프리셀 칸처럼 카드를 잠시 놓아 두는 자리로도 쓰입니다.

여러 장을 한 번에 옮기기

카드는 한 번에 한 장씩 옮기는 것이 원칙이지만, 순서대로 쌓인 묶음은 빈칸만 넉넉하면 한 번에 옮길 수 있습니다. 영상 중간에도 오른쪽 열이 비어 있어서, 이 빈 열을 이용해 10♣와 J♦ 두 장을 한 번에 옮기는 장면이 있습니다.

어떻게 이게 가능할까요? 먼저 10♣를 빈 열에 내려놓고, J♦를 옮길 자리인 Q♣ 위로 옮긴 다음, 빈 열에 있던 10♣를 다시 J♦ 위에 올리면 됩니다. 한 장씩 세 번 옮긴 결과와 똑같으니, 게임에서는 이 과정을 한 번에 처리해 줍니다.

<그림 3-1. 10♣를 빈 열로>

<그림 3-2. J♦를 Q♣ 위로>

<그림 3-3. 10♣를 J♦ 위로>

<그림 3-4. 세 번 옮긴 결과>

빈칸이 많을수록 한 번에 옮길 수 있는 장 수도 늘어나는데, 아래 식으로 구할 수 있습니다.

한 번에 옮길 수 있는 장 수 = (빈 프리셀 칸 수 + 1) × 2^(빈 열 수)

식에 대해서 설명하자면, 빈 프리셀 칸이 f개 있으면 묶음의 아래쪽 f장을 프리셀 칸에 빼 둘 수 있습니다. 그러면 남은 맨 위 카드를 먼저 옮기고 빼 둔 카드를 차례로 다시 얹으면 되니, f + 1장을 옮길 수 있습니다.

여기에 빈 열이 하나 있으면 두 배가 됩니다. 묶음의 아래쪽 f + 1장을 같은 방법으로 빈 열에 옮겨 두고, 나머지 f + 1장을 옮긴 다음, 빈 열에 둔 f + 1장을 그 위에 다시 얹으면 되기 때문입니다. 빈 열이 하나 늘 때마다 이렇게 두 배씩 늘어납니다.

단, 옮겨 갈 곳이 빈 열이면 그 열은 빈 열 수에서 뺍니다. 위 장면은 빈 프리셀 칸이 0개, 빈 열이 1개라서 (0 + 1) × 2^1 = 2장까지 한 번에 옮길 수 있습니다.

둘 수 있는 수와 길찾기

그렇다면 처음 판에서 둘 수 있는 수는 모두 몇 가지일까요?

윈도우 프리셀 1번 판에서는 8가지입니다. 각 열의 맨 아래 카드 8장 중 하나를 프리셀 칸으로 빼는 수가 전부입니다. 처음 판에는 다른 열로 옮길 수 있는 카드도 없고, 파운데이션에 바로 올릴 A도 맨 아래에 없기 때문입니다.

<그림 4. 처음 판에서 둘 수 있는 8가지 수>

빈 프리셀 칸이 4개이니 8 × 4 = 32가지가 아닌가 싶을 수도 있는데요. 프리셀 칸 4개는 서로 차이가 없어서 어느 칸에 넣든 그다음에 둘 수 있는 수가 똑같습니다. 그래서 카드마다 한 가지로 셉니다.

한 수를 두면 판이 바뀌고, 바뀐 판에서 다시 여러 수를 둘 수 있습니다. 이렇게 수를 하나씩 골라 나가다 보면 52장을 모두 올리는 길도 있고, 더 둘 수가 없어 막히는 길도 있습니다.

즉, 프리셀을 푸는 일은 처음 판에서 52장을 모두 올린 판까지 가는 길을 찾는 문제입니다.

문제는 이 경우의 수가 너무 많다는 점입니다. 영상의 112수를 두는 동안 카드를 옮길 수 있는 경우의 수는 평균 18가지, 최대 60가지였습니다. 평균 18가지씩 112수를 끝까지 펼쳐 보면 단순 계산으로 18^112, 약 10^140가지가 됩니다. 지금 컴퓨터로는 이걸 하나씩 다 따라가 볼 수가 없습니다.

그래서 어느 수부터 살펴보고 어느 수는 버릴지 정하는 방법이 필요합니다. 이 방법이 이번 연재에서 다룰 탐색 알고리즘입니다. 깊이우선탐색과 너비우선탐색의 차이는 예전에 간단하게 정리한 글이 있습니다.

같은 판을 다시 만들기

알고리즘끼리 공정하게 비교하려면 모두 같은 판을 풀어야 합니다.

윈도우 프리셀은 판마다 번호가 있습니다. 처음에는 1번부터 32000번까지였고, 나중 버전에서는 100만 판으로 늘었습니다. 판 번호를 난수의 시드로 넣어서 카드를 섞기 때문에, 섞는 방법만 똑같이 따라 하면 번호 하나로 같은 판을 다시 만들 수 있습니다. 섞는 방법은 Rosetta Code의 Deal cards for FreeCell 페이지에 정리되어 있습니다.

위 영상의 판도 이 방법으로 만든 1번 판에 해당합니다. 첫 줄이 J♦ 2♦ 9♥ J♣ 5♦ 7♥ 7♣ 5♥로 윈도우 프리셀 1번 판과 같습니다. 이번 연재에서는 알고리즘마다 이렇게 번호로 만든 같은 판들을 풀게 하여 성능을 비교하고자 합니다.

영상에서 둔 112수는 이 연재에서 다룰 빔서치(beam search)로 찾은 수순입니다.

다음 글에서는 탐색 없이 수를 고르는 가장 단순한 방법인 무작위로 고르기와, 그때그때 가장 좋아 보이는 수를 고르는 그리디(greedy) 방법부터 살펴보겠습니다.