GM 오락실
← 프로젝트 회고 · Algorithm
RETROSPECTIVE · 회고

기차 선로 퍼즐 난이도: 풀이기 탐색 수로 매겼더니 지옥행이 1분 만에 풀렸다

Algorithm

「다음 역은」은 판 위에 선로를 깔아 객차를 순서대로 태우고 도착역까지 보내는 퍼즐이다. 깔 수 있는 선로 수가 정해져 있고, 터널 · 정거장 · 차단기 · 신호기 · 발판 · 분기기 같은 장치가 섞인다. 차례로 열리는 노선도와, 날마다 네 등급(완행 · 급행 · 특급 · 지옥행)으로 나오는 오늘의 열차가 있다. 판은 전부 생성기로 만들고 풀이기로 검증한다.

해가 하나뿐인 판 만들기: 깎기

무작위로 놓은 판은 대부분 해가 여러 개다. 객차가 4대인 판은 해가 하나만 나올 확률이 아주 낮다. 그래서 만든 뒤에 깎았다.

  1. 무작위로 객차와 도착역을 놓고, 풀이기로 최소 선로 수를 구한다.
  2. 해가 여럿이면 '다른 해만 지나가는 칸'을 하나 골라 장애물을 놓는다.
  3. 다시 풀어서 해가 하나가 될 때까지 반복한다.

장애물은 해를 없애기만 하고 새 해를 만들지 않는다. 그래서 깎아도 최소 선로 수는 그대로이고, 원래 정답은 계속 정답이다.

첫 난이도: 풀이기가 얼마나 헤맸나

처음엔 난이도를 풀이기가 탐색한 노드 수로 쟀다. D = log2(노드 수 + 1). 노선도는 역마다 목표 D를 정해 두고 가장 가까운 판을 골랐고, 오늘의 열차 등급도 D 구간으로 나눴다.

그런데 어느 날 지옥행이 5×4 판, 객차 3대, 선로 8개, 장치 하나 없는 판으로 나왔다. 1분이면 풀렸다. 풀이기의 탐색 수는 빈칸이 많을수록 커진다. 선로를 놓을 수 있는 자리가 많으면 풀이기는 그만큼 헤매지만, 사람은 작은 판을 한눈에 본다. 풀이기에게 어려운 것과 사람에게 어려운 것이 달랐다.

사람이 머리 쓰는 것으로 다시 재기

등급 기준을 사람이 실제로 고민하는 것들로 바꿨다. 깔아야 할 선로 수, 세 갈래로 갈라지는 자리 수, 챙길 객차 수, 그리고 장치마다 다른 몫이다. 풀이기 탐색 수는 작은 보정으로만 남겼다.

X = 선로 수
+ 1.5 × 세 갈래 수
+ 2 × (객차 수 − 2)
+ 장치 몫 // 신호 2 · 분기기 · 발판 갈림길 1.5 · 차단기 · 정거장 1 · 터널 0.5 …
+ 0.25 × (D − 11)

지옥행은 X가 높은 판에서 고르고, 장치 없는 판의 비율에 상한을 뒀다. 바꾼 뒤 지옥행은 세 갈래 자리의 중간값이 2에서 4로 늘었고 객차 4대 판이 많아졌다. 노선도는 그대로 D 기준으로 두었다.

있으나 마나 한 터널

터널은 판의 한쪽 입구로 들어가 다른 입구로 나오는 장치다. 터널이 두 쌍인 판을 보다가, 한 쌍은 타지 않아도 같은 선로 수로 풀리는 판을 찾았다. 장식이 되어 버린 장치다. 플레이어는 '이걸 어떻게 써야 하지'를 고민하다 쓸 필요가 없었다는 걸 알게 된다.

검사를 하나 더 넣었다. 터널 쌍마다 그 쌍을 바위로 바꾸고 다시 풀어 본다. 같은 선로 수로 풀리면 그 쌍은 장식이니 바위로 바꾸고 정답을 갱신한다. 돌려 보니 터널이 두 쌍인 판은 전부 한 쌍이 장식이었고, 한 쌍짜리 판은 모두 터널 없이는 풀리지 않았다. 고친 뒤에는 남은 터널이 전부 꼭 타야 풀린다.

판 묶음을 다시 만드는 스크립트는 이 수정 전의 판 풀에서 뽑는다. 그대로 다시 돌리면 장식 터널이 돌아오므로, 빌드 뒤에 이 검사를 꼭 다시 돌리도록 작업 문서에 적어 두었다.

검증

모든 판의 정답을 처음부터 다시 돌려 도착하는지 확인하고, 객차 4대 판 몇 개는 실제 게임 화면에서 정답을 깔아 끝까지 가는지 봤다.

배운 점

  1. 풀이기의 탐색 수는 풀이기의 난이도다. 사람의 난이도는 사람이 고민하는 것(선로, 갈림길, 챙길 것, 장치)으로 재야 한다.
  2. 해를 하나로 만들 때는 '없애기만 하는' 조작을 쓰면 최소 수와 정답이 흔들리지 않는다.
  3. 장치가 정말 필요한지는 빼 보면 안다. 빼도 풀리는 장치는 퍼즐이 아니라 장식이다.
  4. 고친 결과가 빌드 파이프라인 바깥에 있으면 다음 빌드가 되돌린다. 검사를 빌드 순서에 넣어야 한다.
Gunmo Lee
since 2021.07
기차 선로 퍼즐 난이도: 풀이기 탐색 수로 매겼더니 지옥행이 1분 만에 풀렸다 | GM 오락실