Hacker NewsAI · 머신러닝

AI로 만든 최강 소코반 솔버, 기존 솔버 능가

원제 The Strongest Sokoban Solver

107 포인트댓글 23
Key Point

AI 에이전트의 대규모 협력 개발 사례로, 복잡한 알고리즘 연구에서 프론티어 모델이 인간 개발자를 대체할 수 있음을 보여준다.

핵심 요약

  • Soksolv는 소코반(박스 밀어내기 퍼즐 게임) 솔버로 표준 벤치마크 양쪽에서 발표된 모든 솔버보다 많은 레벨(전체 13,315개 중)을 해결하며, 24개의 세계 최초 자동 클리어 기록을 포함했고 기존 솔버 대비 약 3.2배 빠르다.
  • 개발자는 Claude Code와 약 430개의 서브에이전트(Sonnet, Opus, Fable 모델 조합)를 활용해 한 번의 14일 단일 세션으로 개발했으며, API 비용은 약 3,500달러였다.
  • 소코반은 1982년 일본에서 출시된 게임으로 1997년 PSPACE-완전성이 증명되었으며, 작은 판도 수백 개에서 수천 개의 움직임이 필요한 거대한 탐색 공간을 가진다.
  • 솔버는 최고-우선 탐색으로 시작했으나 FESS(Feature Space Search) 논문의 방법을 직접 구현해 여러 특성(박스 배치, 자유 공간 연결성, 작업자가 접근 가능한 방 수 등)을 통해 탐색 공간을 보다 효율적으로 탐색했다.
  • 새로운 기법들로 역방향 풀링(시간을 거슬러 박스를 당기는 시뮬레이션)으로 전방 탐색과 만나는 깊이를 줄이고, 새로성(novelty) 개념으로 미탐사 영역을 보상하며, '레인' 아키텍처로 8개 코어 모두에서 병렬 탐색을 진행했다.
  • 팩토링 기법으로 레벨을 독립적으로 풀 수 있는 여러 부분으로 분해하고, 릴레이 전략으로 일부 박스가 목표에 도달한 뒤 더 작은 퍼즐로 재시작하는 방식도 도입했다.
  • 에이전트들은 깊은 뮬록(deadlock) 감지, 위치 중복 제거, 고립된 지역(corral) 우선 처리 등 다양한 가지치기와 휴리스틱을 발전시켜 탐색 공간을 축소했다.
  • 개발 과정은 플래닝 에이전트(Opus)가 15분마다 진행 상황을 점검하고 실험 방향을 결정하며, 빌더 서브에이전트가 각 실험을 별도 브랜치에서 구현하고, 분석가 서브에이전트가 진단 및 검토하는 구조로 운영됐다.
  • 계산 비용 제어와 벽시계 시간 단축을 위해 테스트 타임아웃 강제, 시간 소모적인 전체 벤치마크 대신 중간 신호(예: 알려진 솔루션 경로 추적) 활용 등의 메커니즘을 적용했다.
  • 개발자는 에이전트들이 위험을 회피하는 경향(과도한 검증 선호)을 직접 개입해 조정했으며, 초반 금지 규칙(기계학습 없음, 경쟁사 코드 무단 열람 금지)을 후반부에 풀어 기존 솔버 분석으로 팩토링 같은 기법을 발굴했다.
  • 전체 프로젝트는 792개 실험을 거쳤고, 15,000 vCPU-시간(AMD EPYC)의 계산 자원이 소요됐으며, 개발자는 맥북과 아이폰의 음성 명령으로 약 50% 작업을 이동 중에 수행했다.
AI 요약 안내

AI가 한국어로 정리한 내용입니다. 정확한 정보는 원문을 확인해 주세요.

요약 원칙 ↗