Show HN: 브라우저에서 돌아가는 Sokoban 최적해 AI 솔버

TL;DR Highlight

A* 검색으로 Sokoban 최소 이동 해를 브라우저에서 밀리초에 구했다

Who Should Read

LLM 시대에 고전 탐색 알고리즘(A*)으로 상태 공간 문제를 효율적으로 풀어 보고 싶은 백엔드·프론트엔드 개발자

Core Mechanics

AI라고 부르지만 LLM이 아니라 A* 탐색이다
- Sokoban 최적 솔버를 A* 탐색 문제로 풀었다.
- 원래 C++로 짠 최적 솔버를 순수 JavaScript로 옮겨 브라우저에서 돌린다.
상자 한 번 미는 것을 탐색 한 단계로 잡았다
- 간선 비용은 키퍼가 미는 위치까지 걷는 최단 거리에 1을 더한 값이다.
- 걷는 단계는 탐색에서 건너뛰면서도 총 이동 수는 진짜 최소값이 나온다.
상태를 정수 몇 개로 압축했다
- 상자는 도달 가능한 칸 위에서 32비트 정수로, 키퍼는 숫자 하나로 담는다.
- 상태 하나가 약 8바이트 키라서 약 1KB 객체 대신 수백만 상태가 수십 MB에 들어간다.
큐와 해시도 메모리 할당 없이 만들었다
- A* 프런티어는 비용을 키로 쓰는 버킷 큐다.
- 방문 집합과 부모 링크는 평평한 typed array 해시에 둔다.
데드락 가지치기로 A*의 최적성을 유지한다
- 목표에서 역방향으로 도달 가능한 칸을 계산해 죽은 칸 표를 만든다.
- 얼어붙은 상자 검사로 풀 수 없는 상태를 버린다.
- 벽을 고려한 푸시 거리 하한을 휴리스틱으로 써서 최적해를 보장한다.

Community Reactions

오래된 의미의 AI가 반갑다는 의견
- 전문가 시스템, A*, SAT 같은 고전 기법이 다음 AI 돌파구의 일부가 될 수 있다는 의견이다.
- LLM 출력을 고전 AI 방식으로 제약하자는 아이디어도 나왔다.
15번 보드도 브라우저에서 가능할 수 있다는 의견
- WASM으로 속도를 올리는 방안이 제안됐다.
- 상태를 키퍼 도달 가능 영역 전체로 저장하거나 BFS를 쓰는 방안이 제안됐다.
- 최신 Sokoban 솔버의 가지치기 기법을 참고하자는 의견도 있었다.
최신 솔버보다 뒤처지고 예제도 쉽다는 비판
- 공개된 SOTA Sokoban 솔버들에 비해 작고 단순한 레벨에만 통한다는 의견이다.
- 함정 상태가 많은 어려운 예제가 없다는 지적도 있었다.
직접 풀어 본 경험과 규칙 차이 지적
- 12번 보드에서 불가능하다고 접어 둔 첫 수가 최적해였다는 경험이 올라왔다.
- 내가 푼 초기 상태에서도 솔버가 더 적은 이동 수를 냈다는 경험도 있었다.
- 원래 Sokoban과 달리 키퍼의 마지막 위치도 목표여야 한다는 점이 지적됐다.

How to Apply

내 문제의 상태를 비트마스크 키로 바꿔 보기
- 지금 객체나 JSON으로 들고 있는 검색 상태 하나를 골라라.
- 정수 키로 압축해 Map 메모리와 속도를 비교해라.
한 걸음 대신 의미 있는 동작을 간선으로 삼기
- 워크플로·경로 탐색에서 의미 없는 중간 단계를 묶어 한 번에 건너뛰어라.
- 비용은 중간 단계의 합으로 계산해 최적성을 지켜라.
LLM 출력 뒤에 고전 탐색 검증기 붙이기
- 에이전트가 낸 계획을 A*나 제약 검사로 유효성을 확인해라.
- 불가능한 상태 표를 미리 만들어 가지치기에 써라.
무거운 탐색은 서버에서 미리 계산해 재생하기
- 브라우저에서 못 돌리는 케이스는 오프라인으로 풀어 결과를 저장해라.
- 클라이언트는 저장된 해를 재생만 하게 해라.

Try It

복사해서 바로 해보기

# Claude나 ChatGPT에 그대로 붙여넣기 (논문 방법의 간이 버전)

너는 Python 개발자다. 아래 방식으로 작은 Sokoban 최적 솔버를 30줄 이내로 짜 줘.
- 탐색 단위: 상자 한 번 밀기(macro-push). 비용 = 키퍼가 미는 위치까지 BFS 최단 거리 + 1
- 상태: (상자 위치 frozenset, 키퍼 위치)
- 휴리스틱: 각 상자에서 가장 가까운 목표까지 맨해튼 거리 합 (admissible)
- 데드락: 목표에서 역방향 당기기로 도달 불가능한 칸은 가지치기
- 규칙: 모든 상자와 키퍼가 목표 위에 있어야 승리, 목표 수 = 상자 수 + 1

보드:
{{보드를 # 벽, $ 상자, . 목표, @ 키퍼로 붙여넣기}}

이어서 해 볼 것: 같은 보드를 단계별 BFS 대비 확장 상태 수로 비교해 줘.

Terminology

A*출발점부터 든 비용에 목표까지 남은 거리 추정치를 더해 가장 유망한 길부터 파 보는 탐색. 내비게이션이 큰길부터 시도하는 것과 비슷하다.

admissible heuristic실제 비용보다 절대 크게 잡지 않는 추정치. 이 조건이 있어야 A*가 찾은 답이 최적임이 보장된다.

버킷 큐비용별로 칸을 나눠 놓고 낮은 칸부터 꺼내는 큐. 힙 정렬 없이 우선순위 큐를 흉내 낸다.

데드락한번 그렇게 되면 어떻게 해도 풀 수 없는 상태. 상자가 구석에 끼는 경우가 대표적이다.

macro-push걷는 여러 걸음과 상자 밀기 한 번을 묶어 탐색의 한 간선으로 취급하는 방식.