Pourdots
500판이 모두 풀린다는 걸 어떻게 확인했나: 색 정렬 퍼즐 레벨 제작기
색 정렬 퍼즐을 하다가 한참 막히면 "이 판, 정말 풀리긴 하는 걸까?" 하는 의심이 듭니다. 그 의심은 근거가 있습니다. 색을 무작위로 섞어 병에 담으면 실제로 풀 수 없는 배치가 나오기도 하거든요. 그래서 Pourdots 는 출시 전에 본편 500판과 730일치 데일리 문제를 모두 컴퓨터로 직접 풀어 보고, 찾은 풀이를 레벨 파일에 함께 저장했습니다.
규칙부터 짧게
병 맨 위의 색은 같은 색 위나 빈 병에만 부을 수 있습니다. 색마다 조각이 4개씩 있고, 모든 병이 비었거나 한 색 4조각으로 채워지면 이깁니다. 판이 진행되면 특수 병이 하나씩 등장합니다.
| 특수 병 | 규칙 | 처음 나오는 판 |
|---|---|---|
| 작은 병 | 칸이 3개라 한 색을 다 담을 수 없음 — 끝날 때는 비어 있어야 함 | 61 |
| 가려진 칸 | 아래 칸의 색이 맨 위로 올라올 때까지 보이지 않음 | 121 |
| 잠긴 병 | 열쇠 색의 병 하나를 완성할 때까지 붓지도 꺼내지도 못함 | 201 |
| 한 색 병 | 정해진 한 색만 받음 | 301 |
판 하나를 만드는 과정
- 조건 정하기. 판 번호마다 색 수, 병 수, 특수 병 종류가 정해져 있습니다. 1판은 2색이고, 뒤로 갈수록 늘어 마지막 구간은 11~12색, 병은 최대 16개입니다.
- 후보 만들기. 그 조건으로 색을 섞어 배치 후보를 만듭니다. 섞는 데 쓰는 난수는 판 번호에서 만든 시드라서, 언제 다시 돌려도 똑같은 배치가 나옵니다.
- 풀어 보기. 풀이 프로그램이 후보마다 풀이를 찾습니다. 풀리지 않거나 너무 커서 정해진 탐색량 안에 못 푸는 후보는 버립니다.
- 고르기. 풀리는 후보를 최대 8개 모은 뒤, 필요한 수(이동 횟수)와 탐색량 순으로 줄 세워서 그 판의 난이도 위치에 맞는 것을 고릅니다.
이렇게 하면 어떤 판도 "운이 나빠 안 풀리는 판"이 될 수 없습니다. 레벨 파일에 실린 배치는 모두 컴퓨터가 끝까지 풀어 본 것입니다.
최소 수를 증명할 수 있는 판, 없는 판
풀이 프로그램은 A* 탐색을 씁니다. 남은 수를 절대 실제보다 크게 어림하지 않는 기준(같은 색끼리 붙은 덩어리 수에서 색 수를 뺀 값)을 쓰기 때문에, 끝까지 찾으면 찾은 풀이가 가장 짧은 풀이라는 것이 보장됩니다. 이 길이를 그 판의 기준 수로 씁니다.
문제는 판이 커질 때입니다. 색이 10개를 넘고 병이 14~16개가 되면 경우의 수가 폭발적으로 늘어납니다. 그래서 탐색은 4만 개 상태에서 멈추고, 그 안에 못 끝내면 '조금 덜 꼼꼼하지만 훨씬 빠른' 가중 탐색으로 바꿉니다. 이때 찾은 풀이는 반드시 풀리긴 하지만 가장 짧다는 보장은 없습니다.
결과적으로 500판 중 275판은 최소 수가 증명됐고, 225판은 빠른 탐색으로 찾은 풀이의 길이를 기준 수로 씁니다. 처음 74판은 모두 증명됐고, 증명하지 못한 첫 판은 75판이었습니다. 401~500판에서는 100판 중 16판만 증명됐습니다.
그래프에서 눈에 띄는 곳이 301판입니다. 276~300판의 기준 수 중앙값은 38 인데 301~325판은 31 로 내려가고, 증명 비율은 8% 에서 72% 로 뛰어오릅니다. 이유는 두 가지입니다. 301판부터 새 구간이 시작되면서 색 수가 그 구간의 낮은 쪽(10색)부터 다시 올라가고, 한 색 병이 들어오는 판에는 빈 병을 하나 더 줍니다. 특수 병이 빈 병 자리를 빼앗으면 풀리지 않는 배치가 너무 많아지기 때문입니다. 병에 여유가 생기면 풀이가 짧아지고, 컴퓨터가 끝까지 찾기도 쉬워집니다.
그래프가 매끈하게 오르지 않는 데는 다른 이유도 있습니다. 10판마다 한 번은 앞 구간 조건으로 만든 쉬운 '휴식 판'이, 25판마다 한 번은 그 구간에서 가장 어려운 후보를 고른 판이 나오도록 톱니 모양으로 설계했습니다.
별 셋의 기준이 1.1배인 이유
별은 기준 수의 1.1배 이하로 깨면 3개, 1.5배 이하면 2개, 그 밖에는 1개입니다. 기준 수가 최소 수와 같다는 보장이 없는 판이 절반 가까이 되기 때문에, 기준 수와 정확히 같아야만 별 셋을 주면 불공평할 수 있습니다. 반대로 가중 탐색 판에서는 플레이어가 기준 수보다 짧게 푸는 일도 생길 수 있습니다. 그런 기록을 찾았다면 컴퓨터를 이긴 겁니다.
앱을 고칠 때마다 다시 확인
레벨을 한 번 만들고 끝이 아닙니다. 앱의 자동 검사는 코드를 고칠 때마다 다음을 다시 확인합니다.
- 본편 500판과 데일리 730일 모두, 색마다 조각이 정확히 4개인지
- 저장된 풀이를 실제 게임 규칙대로 한 수씩 따라 하면 이기는지, 그 길이가 기준 수와 같은지
- 저장된 시드로 같은 배치를 다시 만들 수 있는지
규칙 코드를 잘못 고쳐 어떤 판이 풀리지 않게 되면 이 검사에서 바로 걸립니다.
막혔을 때 써 볼 요령
- 빈 병은 마지막 카드입니다. 빈 병에 아무 색이나 부으면 선택지가 확 줄어듭니다. 같은 색을 모을 수 있을 때만 쓰세요.
- 거의 다 찬 병부터 끝내세요. 한 색 4조각이 모인 병은 닫혀서 더 신경 쓸 필요가 없고, 잠긴 병의 열쇠가 되기도 합니다.
- 작은 병은 임시 보관함입니다. 한 색을 다 담을 수 없으니 결국 비워야 합니다. 잠깐 옮겨 둘 때만 쓰세요.
- 가려진 칸은 일찍 열어 보세요. 무엇이 숨어 있는지 알아야 계획을 세울 수 있습니다.