창고지기의 탄생과 PSPACE-완전이라는 난제
두들푸시처럼 상자를 밀어 목표 지점에 넣는 퍼즐에는 일본어 '倉庫番(そうこばん)'에서 온 이름, 소코반(Sokoban)이 붙는다. 우리말로 옮기면 '창고지기'다.
일본의 작은 회사가 만든 퍼즐
소코반은 1982년 일본의 게임회사 씽킹래빗(Thinking Rabbit)이 발표했다. 창업자 이마바야시 히로유키(今林宏之)가 만든 이 게임은 캐릭터가 상자를 밀어 창고의 지정된 위치에 정리하는 단순한 규칙이었지만, 규칙의 단순함과 난이도의 격차가 상당해서 PC와 여러 콘솔로 이식되며 세계적으로 퍼졌다. 이후 '소코반'이라는 이름 자체가 상자 밀기 퍼즐 장르 전체를 가리키는 보통명사처럼 쓰이게 됐다.
5개 판에서 시작해 20개 판으로
소코반의 첫 버전은 지금 알려진 것보다 훨씬 작았다. 이마바야시는 NEC PC-8001용으로 딱 5개 판짜리 초기 버전을 먼저 만들었고, 이후 그래픽을 다듬고 판을 20개로 늘려 1982년 12월 상업판으로 정식 출시했다. 이 상업판은 NEC PC-8801용 카세트테이프로 처음 나왔고, PC-8001mk2와 후지쓰 FM-7용으로도 함께 발매됐다. 이듬해에는 샤프 X1, MZ-2000, NEC PC-6001 등 당시 일본에서 쓰이던 여러 개인용 컴퓨터로 이식이 이어졌다. 상업적으로도 성공해서 1984년 7월까지 2만 5천 장 넘게 팔렸고, 특히 MSX판 하나만 40만 장 넘게 팔릴 정도로 인기를 끌었다. 2018년 기준으로는 소코반 시리즈 전체 누적 판매량이 410만 장을 넘어섰다고 알려져 있다. 이 성공은 1983년 일본에서 이른바 '퍼즐 게임 붐'을 촉발한 계기 중 하나로도 꼽힌다.
왜 유독 어려운가
소코반이 다른 퍼즐과 구별되는 지점은 상자를 당길 수 없다는 규칙에서 나온다. 한 번 잘못 민 상자는 되돌릴 방법이 없으니(게임 안에서 '되돌리기' 기능을 쓰지 않는 한), 몇 수 앞을 내다보지 않고 두면 필연적으로 막다른 길에 몰린다. 게다가 상자가 여러 개일 때는 한 상자의 이동 가능 여부가 다른 상자들의 위치에 따라 계속 바뀐다. 상자 하나를 목표로 옮기는 순서를 잘못 정하면, 그 상자가 다른 상자의 통로를 막아버리는 식이다. 흔히 나오는 실수 하나는 상자를 벽 모서리 쪽으로 밀어 넣는 것이다. 상자가 벽과 벽이 만나는 구석에 완전히 박히면, 그 지점이 목표 칸이 아닌 이상 다시는 밀어낼 방법이 없다. 초심자가 가장 자주 막히는 지점이 바로 이런 '구석 데드락'이고, 몇 수 앞서 상자가 어느 방향으로 밀릴지, 그 끝에 벽 구석이 있는지를 먼저 확인하는 습관만 들여도 막히는 빈도가 크게 줄어든다.
PSPACE-완전이라는 딱지
캐나다 앨버타 대학의 컴퓨터과학자 조지프 컬버슨(Joseph Culberson)은 1997년 논문에서 소코반이 'PSPACE-완전(PSPACE-complete)' 문제라는 것을 증명했다. 어려운 용어지만 뜻은 비교적 간단하다. 컴퓨터과학에서는 문제의 어려움을 몇 단계로 분류하는데, 우리가 흔히 듣는 'NP-완전'은 스도쿠처럼 답을 미리 알려주면 맞는지 빠르게 확인할 수 있지만 처음부터 답을 찾기는 오래 걸리는 문제군을 말한다. PSPACE는 이보다 한 단계 더 넓은 분류로, 답을 검증하는 것조차 쉽지 않을 수 있는 문제까지 포함한다. 소코반이 PSPACE-완전이라는 건, 상자와 목표 지점의 개수를 계속 늘려가는 일반화된 소코반 퍼즐을 항상 빠르게 풀어내는 방법은(적어도 지금까지 알려진 바로는) 존재하지 않는다는 뜻이다. 이는 소코반이 NP-완전으로 알려진 다른 많은 퍼즐보다 이론적으로 더 다루기 까다로운 부류에 속한다는 의미이기도 하다.
증명은 어떻게 이뤄지는가
컬버슨의 증명 방식도 짚어볼 만하다. 이런 유의 증명은 대개 이미 어렵다고 알려진 다른 문제를 지금 다루는 문제로 '변환'해서, 만약 지금 문제를 빠르게 풀 수 있다면 원래 그 어려운 문제도 빠르게 풀 수 있게 된다는 모순을 보이는 방식으로 이뤄진다. 컬버슨은 '선형 유계 오토마타(linear bounded automaton)'라는, 사용할 수 있는 메모리 양이 미리 정해진 제한적인 튜링 기계 모델을 가져와, 이 오토마타의 계산 과정 전체를 소코반의 상자와 벽 배치만으로 흉내 낼 수 있음을 보였다. 즉 오토마타가 각 단계에서 갖는 내부 상태와 테이프 내용을 창고 안 상자들의 위치로 인코딩하고, 오토마타의 한 계산 단계를 상자를 한 번 미는 행위에 대응시킨 것이다. 이렇게 하면 "이 오토마타가 특정 계산을 끝마칠 수 있는가"라는 질문이 "이 소코반 판을 풀 수 있는가"라는 질문과 정확히 같아진다. 창고 안에서 상자를 미는 단순한 동작 하나하나가, 실은 계산 모델의 한 단계와 정확히 대응하도록 설계될 수 있다는 게 이 증명의 핵심 아이디어다.
사람은 푸는데 컴퓨터는 못 푸는 판도 있다
이 난해함은 이론에서 끝나지 않고 실제 인공지능 연구에서도 그대로 드러난다. 연구자들은 오랫동안 '엑스소코반(XSokoban)'이라는 90개 문제로 이뤄진 표준 벤치마크 모음으로 자동 풀이 프로그램(solver)의 성능을 겨뤄왔는데, 컴퓨터의 처리 속도가 수십 년간 비약적으로 빨라졌는데도 여전히 사람은 어렵지 않게 푸는 몇몇 판을 최신 solver가 끝내 풀지 못하는 경우가 남아 있다고 알려져 있다. 사람은 판 전체를 몇 개의 작은 부분 문제로 쪼개 패턴으로 인식하고 접근하는 반면, 컴퓨터는 원칙적으로 가능한 모든 상자 이동 순서를 뒤지는 탐색에 가깝기 때문에 이런 간극이 생긴다. 규칙은 다섯 줄로 설명되는 게임 하나가, 40년 넘게 계산복잡도 이론과 인공지능 탐색 알고리즘 연구 양쪽에서 계속 다뤄지는 소재로 남아 있는 이유이기도 하다.
우리가 만나는 판은 다르다
물론 이건 '판 크기를 무한히 키울 수 있는 일반화된 소코반'에 대한 이론적 결과다. 두들푸시처럼 상자 몇 개, 12개의 정해진 판으로 구성된 게임은 사람이 직접 풀 수 있는 범위 안에 있다. 다만 왜 어떤 판은 몇 수 만에 막히고 어떤 판은 한참을 고민해야 하는지, 그 난이도의 뿌리를 따라가면 이 이론에 닿는다는 것 정도는 알아둘 만하다. 상자를 하나 밀 때마다 사실상 판 전체의 가능성을 재계산하고 있는 셈이다.