아람코소코반 고수 레벨은 이렇게 만들었어요: 거꾸로 당겨서 가장 먼 배치 찾기
아리의 소코반을 처음 내놓았을 때 30단계를 모두 깬 이용자에게서 한 줄 의견이 왔습니다. "너무 쉽다." 실제로 처음 만든 레벨은 화물을 무작위로 흩어 놓는 방식이라, 가장 어려운 레벨도 최소 밀기 횟수가 12~14번 정도였습니다.
이 글은 그 뒤에 31~60단계 "고수 레벨"을 만든 방법을 정리한 개발 일지입니다. 핵심은 사람이 어려운 퍼즐을 상상해서 그리는 대신, 컴퓨터가 "이 방에서 가장 어려운 시작 배치"를 직접 찾게 한 것입니다.
무작위로 흩으면 왜 쉬워질까
처음 방식은 화물을 도킹 패드 위에 올려 둔 "완성 상태"에서 출발해, 로봇을 무작위로 움직이며 화물을 당겨 흩어 놓는 것이었습니다. 당기기로 만든 배치는 거꾸로 밀면 반드시 풀리기 때문에 "풀리지 않는 레벨"이 나오지 않는다는 장점이 있습니다.
문제는 무작위로 움직이면 화물이 멀리 가지 못한다는 점입니다. 몇백 걸음을 움직여도 대부분의 시간은 같은 자리를 맴돌고, 화물은 목표 근처에 남습니다. 그래서 퍼즐은 "어디로 밀지"보다 "누구부터 밀지"만 정하면 풀리는 수준에 머물렀습니다.
해결책: 거꾸로 당기며 모든 배치를 끝까지 찾기
그래서 무작위 대신 "완성 상태에서 갈 수 있는 모든 배치"를 빠짐없이 탐색하기로 했습니다. 너비 우선 탐색(BFS)으로 한 번 당길 때마다 단계를 하나씩 늘려 가면, 각 배치에 "완성 상태에서 몇 번 당겨야 도착하는지"가 정확히 매겨집니다. 이 숫자는 곧 그 배치를 풀 때 필요한 최소 밀기 횟수입니다.
- 방 모양과 도킹 패드 위치를 정합니다. 3×3 블록에 벽 조각을 찍어 꼬불꼬불한 창고를 만들고, 연결된 바닥만 남깁니다.
- 모든 화물이 도킹 패드 위에 있는 완성 상태를 출발점으로 둡니다. 로봇이 서 있을 수 있는 구역마다 출발점을 하나씩 만듭니다.
- 로봇이 화물 옆에 서서 뒤로 물러나며 화물을 한 칸 당기는 모든 경우를 다음 단계로 넣습니다. 같은 배치(화물 위치 + 로봇이 닿는 구역)는 한 번만 셉니다.
- 탐색이 끝나면, 화물이 하나도 도킹 패드 위에 없는 배치 중 단계 수가 가장 큰 것을 시작 배치로 고릅니다.
- 고른 배치를 정방향 풀이기로 다시 풀어 최소 밀기 횟수를 확인하고, 풀이를 처음부터 끝까지 실제로 재생해 정말 풀리는지 검증합니다.
숫자로 본 결과
생성기를 돌려 후보 45개를 만들고, 그중 밀기 횟수와 "밀 화물을 바꾸는 횟수"가 많은 30개를 골랐습니다. 화물을 자주 바꿔 밀어야 하는 퍼즐일수록 순서를 미리 생각해야 해서 체감 난도가 높기 때문입니다.
| 구분 | 1~30단계 (처음 방식) | 31~60단계 (고수 레벨) |
|---|---|---|
| 만드는 방법 | 무작위로 당겨 흩기 | 모든 배치 탐색 후 가장 먼 배치 |
| 화물 수 | 1~5개 | 4~5개 |
| 최소 밀기 횟수 | 가장 어려운 레벨도 12~14번 | 19~29번 |
| 최소 이동 횟수 | - | 47~152번 |
| 검증 | 풀이기로 풀리는지 확인 | 풀이 재생까지 30개 모두 통과 |
후보를 만드는 동안에는 화물 5개, 최소 밀기 68번이 필요한 배치도 나왔습니다. 하지만 너무 길면 재미보다 지루함이 커서 최종 선정에서는 빠졌습니다. 어려움과 재미 사이의 선은 결국 사람이 정해야 했습니다.
탐색은 얼마나 걸렸을까
방 하나를 끝까지 탐색할 때 만나는 배치 수는 방 모양에 따라 크게 달랐습니다. 후보 45개를 만드는 동안 한 방에서 탐색한 배치는 적게는 1,292개, 많게는 182,294개였습니다. 너무 커지는 방은 35만 개에서 탐색을 멈추게 했고, 밀기 18번 미만이거나 화물을 바꿔 미는 횟수가 6번 미만인 방은 버렸습니다.
이렇게 걸러 내다 보니 쓸 만한 방은 생각보다 드물었습니다. 45개를 얻을 때까지 무작위로 만든 방은 39,448개였고, 전체 생성에는 약 131초가 걸렸습니다. 1,000개 중 1개꼴로 "고수 레벨감"이 나온 셈입니다.
| 단계 | 화물 | 최소 밀기 | 최소 이동 | 특징 |
|---|---|---|---|---|
| 31 | 4개 | 19번 | 47번 | 고수 레벨 입문. 순서만 맞으면 짧게 끝나요. |
| 45 | 5개 | 21번 | 95번 | 화물을 12번 바꿔 밀어야 해요. |
| 55 | 5개 | 24번 | 152번 | 이동이 가장 긴 레벨. 길 찾기가 핵심이에요. |
| 60 | 4개 | 27번 | 111번 | 화물을 16번 바꿔 미는 마지막 관문이에요. |
정방향 풀이기도 같이 다듬었습니다. 밀기 한 번을 한 단계로 보는 너비 우선 탐색에, 죽은 칸으로는 밀지 않기와 "2×2 칸이 화물과 벽으로 꽉 차고 그중 목표가 아닌 화물이 있으면 버리기"(얼어붙은 덩어리 검사)를 더하자, 고수 레벨도 게임 화면 안에서 힌트로 계산할 수 있을 만큼 빨라졌습니다. 게임 안의 힌트도 이 풀이기를 그대로 씁니다.
막힌 걸 알려 주는 빨간불
고수 레벨은 한 번 실수하면 되돌릴 수 없는 상황이 자주 생깁니다. 그래서 화물이 "어떤 도킹 패드로도 다시 옮길 수 없는 칸"에 들어가면 바로 빨간불이 켜지게 했습니다. 이 칸은 도킹 패드에서 거꾸로 당겨 닿을 수 있는 칸을 미리 계산해 두고, 거기에 없는 칸을 "죽은 칸"으로 표시하는 방식으로 찾습니다.
힌트도 같은 풀이기를 씁니다. 지금 화면의 배치에서 풀이를 계산해 다음에 밀 화물과 방향을 노란 화살표로 보여 줍니다. 고수 레벨에서는 힌트를 3번까지만 쓸 수 있게 해서, 스스로 생각할 몫을 남겼습니다.
만들면서 배운 것
- 사람이 "어려워 보이는" 레벨을 그리는 것보다, 컴퓨터가 "실제로 가장 긴 풀이"를 찾게 하는 편이 확실했습니다.
- 탐색은 상태 수가 빠르게 늘어납니다. 같은 배치를 로봇 위치 대신 "로봇이 닿는 구역"으로 묶어 세자 탐색량이 크게 줄었습니다.
- 숫자가 큰 퍼즐이 늘 좋은 퍼즐은 아닙니다. 밀기 횟수와 함께 "화물을 바꿔 미는 횟수"를 기준에 넣자 체감 난도가 훨씬 잘 맞았습니다.
- 이용자의 한 줄 의견("너무 쉽다")이 가장 좋은 출발점이었습니다. 아람 광장에 남겨 주시는 의견도 이렇게 반영하려고 합니다.
자주 묻는 질문
- 고수 레벨도 모두 풀리나요?
- 네. 30개 모두 풀이기로 최소 풀이를 구한 뒤 처음부터 끝까지 재생해 실제로 풀리는 것을 확인했습니다.
- 레벨 옆의 "목표 수"는 무엇인가요?
- 아리가 찾은 풀이의 이동 횟수입니다. 그 이하로 풀면 별 3개를 받습니다.