목표 탭 수를 믿어도 되는 이유: 화살 쓸기 880판을 정확한 풀이기로 검증한 방법

화살 쓸기의 '목표'는 어림값이 아니라 풀이기가 증명한 최소 탭 수예요. 풀이기가 어떻게 최소를 찾는지, 판을 어떻게 걸러 내는지, 힌트와 별 규칙까지 개발 노트로 정리했어요.

화살 쓸기 화면 위쪽에는 탭과 목표라는 두 숫자가 있어요. 목표만큼 이하로 누르면 별 3개예요. 그런데 이 숫자가 "대충 이 정도면 되겠지"로 정해진 값이라면 별 3개는 믿을 수 없는 보상이 돼요. 더 적게 깨는 길이 숨어 있을지도 모르니까요.

그래서 제이월드 팀은 모든 판의 목표를 정확한 풀이기로 계산해요. 이 글은 그 풀이기가 어떻게 생겼는지, 판을 만들 때 어디에 쓰는지, 그리고 풀이기가 못 푸는 규칙을 왜 버렸는지를 실제 코드와 설계 문서에 적힌 수치로 정리한 개발 노트예요.

풀이기가 풀어야 하는 문제

먼저 규칙을 짧게 떠올려 볼게요. 화살을 누르면 그 화살이 머리 방향으로 미끄러지고, 앞에 있는 화살은 줄줄이 밀려서 판 밖으로 나가요. 한 번 누르면 누른 화살 + 앞에 있던 화살들(쓸기 묶음)이 사라져요. 남은 화살은 절대 움직이지 않아요. 그래서 판의 상태는 "어떤 화살이 남았는가" 하나뿐이에요.

이 성질이 풀이기를 쉽게 만들어요. 화살이 최대 30개로 제한되어 있어서, 남은 화살 집합을 비트 하나씩 켜고 끄는 비트마스크(32비트 정수 하나)로 적을 수 있어요. 문제는 이렇게 바뀌어요.

• 시작: 모든 비트가 켜진 상태
• 한 번의 탭: 누른 화살의 쓸기 묶음에 해당하는 비트를 끄기
• 목표: 모든 비트를 끄는 가장 짧은 탭 순서

화살을 한 개씩 모두 누르면 항상 깰 수 있어서, 목표는 화살 수 n 이하예요. 풀이기는 그 안에서 더 짧은 길이 있는지 찾아요.

풀이기의 세 가지 도구

풀이기는 반복 깊이 증가 탐색(IDA*)이에요. "탭 6번 안에 깰 수 있나?"를 먼저 묻고, 안 되면 7번, 8번으로 한도를 올려요. 처음으로 깨지는 한도가 곧 목표예요. 거기에 세 가지 도구가 붙어요.

하한값은 두 가지 논리로 만들어요.

1. 반드시 눌러야 하는 화살: 어떤 화살도 쓸어 주지 못하는 화살은 자기 자신을 눌러야만 나가요. 이런 화살의 수만큼은 반드시 눌러야 해요.
2. 큰 쓸기 합: 탭 k번은 서로 다른 화살을 눌러요. 그러니 k번으로 지울 수 있는 화살은 쓸기 크기가 큰 순서대로 k개를 더한 값 이하예요. 남은 화살 수에 닿을 때까지 더해 보면 최소 탭 수가 나와요.

한 가지 조심한 점이 있어요. 화살이 나가면 남은 화살들의 쓸기 묶음은 줄어들기만 해요. 그래서 "지금 판에서 잰 쓸기"는 이후 어떤 판에서도 상한이 돼요. 덕분에 부모 판에서 한 번 잰 값을 자식 판에서 다시 재지 않고 써도 안전해요. 반대로 얼음 화살은 나중에 녹으면 크게 쓸어 낼 수도 있어요. 처음 실험판은 눌러 볼 수 있는 화살만 하한값에 넣었다가, 얼음 판 400개 중 3개에서 목표를 실제보다 크게 잡는 것을 발견했어요. 지금 풀이기는 얼음 화살까지 모두 세요.

정말 정확한지 어떻게 아나요

"정확하다"는 말은 검증이 없으면 아무 뜻도 없어요. 설계 문서에 남은 검증은 이래요.

• 빠른 엔진과, 한 칸씩 움직여 보는 느린 시뮬레이터를 비교했어요. 무작위 탭 2,262번에서 결과가 어긋난 적은 0번이에요.
• 풀이기 두 종류(IDA*와 너비 우선 탐색)가 작은 판 40개에서 같은 목표를 냈어요.
• 풀이기가 낸 탭 순서대로 다시 눌러 보면 정확히 목표만큼에 깨져 별 3개를 받아요. 이 검사는 모든 판에 걸려 있어요.
• npm run check-levels 한 줄로 저장된 판 전부를 다시 풀어 목표와 힌트를 확인해요. 캠페인 146판, 튜토리얼 4판, 오늘의 판 730판이라서 합하면 880판이에요. 약 3초면 끝나요.

한 판이라도 어긋나면 검사가 실패로 끝나요. 그래서 새 판을 넣거나 규칙을 손볼 때 목표가 조용히 틀어질 수가 없어요.

풀이기를 판 고르기에 쓰는 방법

풀이기는 목표만 계산하지 않아요. 판을 걸러 내는 체로도 써요. 무작위로 만든 후보 판은 12단계 필터를 통과해야 판이 돼요. 값싼 검사부터 하고, 정확한 풀이는 맨 나중에 해요.

하한값과 욕심쟁이 검사만으로 4~5세계 후보의 71~80%가 정확한 풀이 전에 탈락해요(설계 실험 수치). 덕분에 합격한 판 하나를 얻는 데 정확한 풀이는 많아야 4.8번이면 돼요. 가장 큰 5세계 판이 중앙값 5.4ms, 95%가 약 65ms, 가장 느린 판이 약 1.2초에 풀렸어요(설계 실험 수치).

함정 필터가 특히 중요해요. 욕심쟁이 봇은 5세계의 무작위 판에서 절반만 목표를 맞혔어요. 절반의 판은 "제일 큰 쓸기부터"가 통하지 않아요. 풀이기가 있어서 "큰 걸 먼저 누르면 오히려 손해인 판"을 일부러 골라 둘 수 있어요.

풀이기가 못 푸는 규칙은 버렸어요

규칙 후보를 풀이기로 먼저 실험했어요. 두 후보가 버려졌어요.

구덩이를 넣으면 중앙값 풀이 시간이 0.5ms에서 303ms로 늘었어요. 느려서가 아니라, 정확한 목표를 보장할 수 없는 규칙은 쓰지 않는다는 원칙 때문에 버렸어요. 얼음과 끈은 "남은 화살은 움직이지 않는다"는 성질을 지켜서 살아남았어요.

풀이기가 게임 안에서 하는 일

풀이기는 만드는 쪽에만 있지 않아요. 플레이어 화면의 힌트도 같은 풀이기예요. 지금 판 상태에서 다시 풀어서 다음 최적의 한 탭에 불을 켜 줘요. 이미 몇 번 눌러 봤어도, 어느 상태에서든 힌트를 따르면 "지금까지 누른 수 + 남은 최소 탭"으로 끝나요.

별 규칙도 목표에서 나와요.

탭 수는 되돌리기로 취소한 만큼 빼고 세요. 되돌리기와 다시 시작은 공짜라서 눌러 보고 되돌려도 손해가 없어요. 힌트는 첫 번째는 별을 지키고, 결과 화면에 적힌 대로 힌트 2번부터는 별 2개까지예요. 광고로 별 3개를 살 수 없게 하려는 규칙이에요. 결과 화면의 별 3개 푸는 법 보기도 같은 최적 풀이를 보여 줘요.

정리

• 목표는 어림값이 아니라 정확한 풀이기가 증명한 최소 탭 수예요.
• 화살이 최대 30개이고 남은 화살은 움직이지 않아서, 판의 상태가 비트마스크 하나로 표현돼요.
• 풀이기는 반복 깊이 증가 탐색 + 하한값 + 기억표 + 큰 쓸기 먼저로 이루어져요.
• 저장된 880판(캠페인 146 + 튜토리얼 4 + 오늘의 판 730)을 check-levels로 통째로 다시 풀어 검증해요.
• 풀이기는 판을 거르는 체이기도 해요. 욕심쟁이 봇이 틀리는 "함정" 판을 일부러 골라요.
• 풀이기가 못 푸는 규칙(구덩이)은 재미 이전에 정확성 때문에 버렸어요.
• 힌트와 별 규칙도 같은 풀이기에서 나와요. 목표를 맞히면 진짜 최소예요.

직접 확인해 보고 싶다면 웹에서 플레이해 보세요. 목표 숫자와 같은 탭으로 깨졌다면, 더 짧은 길은 없어요. 게임 소개는 /apps/hwasal/에 있어요.

개발퍼즐 설계화살 쓸기

이 글은 제이월드 팀이 게임 설계 문서와 실제 플레이 수치를 바탕으로 썼고, 글을 다듬을 때 AI 도구를 함께 썼어요.