TECH 으로 돌아가기
TECH HACKER NEWS 7분 읽기 30 READS

에이전트 430개로 만든 세계 최강 소코반 솔버, 그 방법과 의미

소코반(Sokoban)은 1982년 일본에서 처음 출시된 퍼즐 게임으로, 작업자가 상자를 밀어 지정된 목표 칸에 올려놓는 것이 전부다. 규칙은 단순하지만 1997년 PSPACE-완전 문제임이 증명될 만큼 계산적으로 어렵다. 사람이 풀 수 있는 레벨도 보통 수백에서 수천 번의 이동을 요구하고, 한 수에서 분기 가능한 경우의 수는 평균 16개, 큰 보드에서는 176개까지 치솟는다. 이 때문에 몇 수만 지나도 단순 완전탐색은 사실상 불가능해진다.

개발자 Healey가 공개한 솔버 'Soksolv'는 소코반 커뮤니티의 두 표준 벤치마크인 Large Test Suite와 Open Test Suite 모두에서 지금까지 공개된 어떤 솔버보다 많은 레벨을 풀었다고 밝혔다. 중복을 제거한 9,756개 레벨(평균 상자 16개, 풀이당 약 830수·160회 밀기)을 대상으로, 24개 레벨은 자동 솔버로서는 세계 최초로 풀어냈고, 다른 솔버도 푸는 레벨에서는 전체 소요 시간이 약 3.2배 빨랐다.

사람이 코드를 한 줄도 쓰지 않았다

이 프로젝트에서 가장 주목할 부분은 결과물 자체보다 제작 방식이다. 저자는 코드를 단 한 줄도 직접 작성하지 않았다고 말한다. Claude Code에서 Opus 5.5 세션 하나를 14일간 유지하면서, Sonnet 5.5·Opus 5.5·Fable 5.2를 섞은 약 430개의 서브에이전트를 동원했다. API 환산 비용은 약 3,500달러 수준이었고($100 요금제와 리셋을 활용), 작업의 절반가량은 이동 중에 아이폰으로 /remote-control에 구술하는 방식으로 진행했다. 연구·검증·장시간 벤치마크 실행에는 AMD EPYC 기준 15,000 vCPU-시간이 들었다.

저자는 솔버 개발을 '언덕 오르기(hill climbing)'의 가장 순수한 형태로 봤다. 측정할 지표가 푼 레벨 수와 총 소요 시간 두 가지로 명확하기 때문이다. 그는 변경 불가능한 기준 버전 하나, 실험당 가설 하나, 동결된(frozen) 검증기, 별도의 승격 테스트 묶음이라는 구조를 세웠다. 에이전트가 편집할 수 없는 별도 패키지의 검증기는 2,632개의 알려진 풀이를 한 수씩 재생해 가지치기 규칙을 검증했고, 이 과정에서 잘못된 가지치기 규칙 두 개를 실제로 걸러냈다.

부정행위를 막은 것은 규칙이 아니라 동기 설계

초기 LLM이 테스트를 주석 처리해 목표를 '달성'하던 기억 때문에 저자는 에이전트의 부정행위를 우려했다. 그러나 실제로는 부정 징후가 전혀 없었는데, 그는 에이전트의 동기를 순수한 점수 경쟁이 아니라 실험과 학습 쪽으로 유도한 덕분으로 추정한다. 아울러 머신러닝 금지(감사 어려움), 경쟁 솔버 코드 열람 금지(비효율 설계 복제 위험), 하드코딩 금지(부정행위), Go 언어 사용, 15GB 메모리 상한 같은 제약을 걸었다. 기존 솔버 위에 쌓지 않은 이유도 분명하다. 남의 설계 결정에 묶이면 그 배경을 모른 채 종속되어 한 자릿수 이상의 개선이 불가능해진다는 것이다.

탐색 공간을 줄이는 고전 기법들의 재현

알고리즘적으로 보면 Soksolv는 소코반 연구의 축적된 지혜를 충실히 구현한다. 핵심은 '걷기는 공짜이고 오직 밀기만이 퍼즐을 바꾼다'는 통찰이다. 따라서 탐색은 밀기 단위로 이루어지고, 작업자의 위치는 정확한 칸이 아니라 도달 가능한 영역(플러드 필)으로 추상화된다. 같은 상자 배치에 작업자가 같은 구역에 있으면 동일한 상태로 간주해 중복을 제거하고, 터널에 갇힌 강제 밀기는 하나의 매크로 수로 묶어 트리를 얕게 만든다. 대부분의 탐색 공간이 사실상 '죽은' 영역이라는 점에서, 데드락 칸 감지(Holland #68에서는 69개 바닥 칸 중 19개가 영원히 상자를 둘 수 없다)와 작업자가 닿지 못하는 영역을 공략하는 PI-corral 가지치기가 큰 역할을 한다.

솔버의 뼈대를 이루는 두 기법도 흥미롭다. 하나는 완성된 상태에서 상자를 '당기며' 시간을 되감는 후방 탐색이다. 전방과 후방 탐색이 중간에서 만나면 각 트리의 깊이가 절반으로 줄어 b^d개의 노드가 약 2·b^(d/2)로 감소한다. 특히 전방에서는 구석에 밀린 상자가 데드락이 되지만, 후방에서는 구석에서 다시 빼낼 수 있어 죽은 칸이 사라진다. 다른 하나는 Festival 솔버의 저자 Yaron Shoham이 제안한 FESS(Feature Space Search)다. 단일 점수 대신 '목표에 오른 상자 수'나 '작업자 영역' 같은 특징들의 조합 공간을 번갈아 탐색하는 방식으로, Microban #35에서 최선 우선 탐색이 1,259회 확장(그중 405회를 한 칸에 소모)한 반면 FESS는 823회로 끝냈다.

한국 실무자 관점에서 이 프로젝트가 던지는 함의는 두 갈래다. 알고리즘 측면에서는 FESS와 고전 계획 분야의 '참신성(novelty)' 기반 탐색처럼 수십 년간 다져진 기법이 여전히 최전선이라는 점, 그리고 동시성 설계처럼 사람이 어려워하는 영역이 프론티어 모델에게는 오히려 강점이 될 수 있다는 점이다. 다만 비용(약 3,500달러·1만5천 vCPU-시간)과 14일이라는 기간, 그리고 명확한 측정 지표와 동결 검증기라는 전제가 있었기에 가능했다는 한계도 분명하다. 결국 성과의 핵심은 모델 자체보다 '움직일 수 없는 기준과 속일 수 없는 검증기'라는 실험 구조를 사람이 먼저 설계했다는 데 있다.

SOURCE · HACKER NEWS
원문 전체 보기 → https://healeycodes.com/introducing-the-worlds-strongest-sok...
SHARE
NEXT · CHOOSE

변화를 읽었다면,
내가 만들 수익 구조를 고릅니다.

정보를 더 모으는 데서 멈추지 않고, 광고·외주·판매·중개·구독 중 내 상황에 맞는 출발점을 정해보세요.

21가지 수익 구조 살펴보기 →
처리 중...