Sokoban AI 솔버: JavaScript에서의 최적 경로 탐색

Menachem Kornreich는 고성능 JavaScript로 구현된 네이티브 C++ 솔버의 포트를 사용하여, 보장된 최적 해—즉, 최소한의 키퍼 이동 수—를 찾는 Sokoban AI 솔버를 개발했습니다. 이 도구는 브라우저 환경에서 복잡한 격자 기반 퍼즐을 효율적으로 해결하기 위해 '전통적인 AI' 탐색 기법을 적용하는 사례를 보여줍니다.

솔버의 기술적 구현

이 솔버는 A* 탐색 알고리즘을 기반으로 하지만, 단순한 구현에서 흔히 발생하는 상태 공간 폭발을 피하기 위해 여러 최적화 전략을 사용합니다.

매크로 푸시 A* 탐색

각 개별 키퍼 이동을 탐색 엣지로 취급하는 대신, 솔버는 매크로 푸시 방식을 사용합니다. 탐색 그래프의 각 엣지는 완전한 상자 밀기 하나를 나타냅니다. 엣지의 비용은 키퍼가 밀기 위치까지 최단 거리로 이동하는 데 드는 비용에 밀기 자체의 비용 1을 더한 값입니다. 이 방식은 개별 걷기 단계를 건너뛸 수 있게 하면서도 실제 최소 키퍼 이동 수를 정확히 계산할 수 있습니다.

상태 압축 및 메모리 관리

수백만 개의 상태를 제한된 메모리 공간에 맞추기 위해, 솔버는 컴팩트한 비트마스크 상태를 사용합니다:

• 상자 위치: 상자들은 보드의 도달 가능한 '라이브' 셀들에 대해 32비트 정수에 압축됩니다.
• 키퍼 위치: 키퍼의 위치는 별도의 숫자로 저장됩니다.
• 상태 표현: 이 방식은 상태를 약 1KB의 객체에서 단일 약 8바이트 키로 줄여, 수백만 개의 상태를 십 수 메가바이트 내에 수용할 수 있게 합니다.

성능을 위한 데이터 구조

솔버는 A* 프론티어에 다이얼 버킷 큐를, 방문한 상태 집합에는 오픈 어드레싱 해시를 사용합니다. 평탄한 타입화된 배열을 사용함으로써, 할당 없이 캐시 친화적인 구현이 가능해져 JavaScript에서 성능을 극대화하는 데 핵심적인 역할을 합니다.

데드락 가지치기

정확성과 최적성 보장을 위해 솔버는 두 가지 가지치기 기법을 사용합니다:

• 데드 스퀘어 테이블: 목표로부터 역방향 도달 가능성을 기반으로 생성된 정적 테이블로, 상자를 목표로 옮길 수 없는 칸을 식별합니다.
• 프리즈 체크: 벽을 고려한 밀기 거리 하한값을 기반으로, 확실히 해결 불가능한 위치를 버리는 메커니즘입니다.

성능 및 제약 조건

보드 1번부터 14번은 밀리초 단위로 실시간으로 해결되지만, 15번 보드(8개 상자로 구성된 미로)의 복잡도는 상당한 예외입니다. 이 특정 보드에 대한 최적 탐색은 약 4900만 개의 상태를 탐색하며 1GB 이상의 메모리가 필요합니다. 브라우저 탭의 제한을 초과할 수 있으므로, 15번 보드의 해결책은 C++로 24개 코어에서 병렬 A* 탐색을 사용해 오프라인으로 계산되었으며, 사전 계산된 해결책으로 재생됩니다.

커뮤니티 논의 및 통찰

Hacker News 커뮤니티에서는 이 프로젝트를 현대의 LLM 기반 AI와 대비하여 '전통적인 AI'(탐색 및 전문가 시스템)로의 복귀로 평가했습니다. 일부 사용자는 이 솔버의 접근 방식이 키퍼가 목표 지점에 도착해야 하는 특수한 변형의 Sokoban 퍼즐임을 지적하며, 승리 조건에 추가적인 제약을 더했다고 설명했습니다.

다른 기술적 비판과 제안도 커뮤니티 피드백에 포함되었습니다:

혹시 상태가 과도하게 압축된 건 아닐까요? 키퍼가 밀기 없이 도달할 수 있는 모든 위치를 (상자, [키퍼가 밀기 없이 도달 가능한 모든 위치])로 저장하는 방식은, 키퍼가 걷는 재계산을 줄일 수 있지 않을까요?

다른 간단한 가지치기 기법은 없을까요? 예를 들어, 이와 같은 최첨단 Sokoban 솔버에서 얻은 어떤 학습도 활용할 수 있을까요?

사용자들은 또한 솔버가 임의의 보드 상태에서 AI 해결을 트리거할 수 있도록 해, 상자를 적대적인 위치로 옮긴 후 해결책을 요청함으로써 퍼즐을 '악화'시키는 탐색이 가능하다고 지적했습니다.