Solvable Sokoban Without a Solver via Diffusion

컴퓨터 과학의 세계에는 해결책을 확인하는 것은 쉽지만, 그 하나를 찾아내는 데는 브루트 포스(brute force) 방식으로 풀 경우 우주의 나이보다 더 긴 시간이 걸릴 만큼 방대한 가능성의 미로를 헤매야 하는 매우 복잡한 문제들이 존재한다. 이것들은 단순히 어려운 퍼즐이 아니라, 답으로 가는 경로가 단지 긴 것이 아니라 지수적으로 길어서, 한 걸음을 내디딜 때마다 새로운 가능성의 우주가 열리는 동시에 다른 가능성들은 닫혀버리는 문제들이다. 이와 같은 가장 유명한 예 중 하나는 소코반(Sokoban)이라는 게임이다. 이 게임은 격자판 위에서 단 하나의 캐릭터가 상자를 밀어서 특정 목표 지점으로 옮기는 방식으로 진행된다. 함정은 캐릭터가 오직 밀기만 할 수 있고 당길 수는 없다는 점이며, 일단 상자가 구석에 끼어버리면 영원히 갇혀버리는 경우가 많다는 것이다. 상자 하나의 위치가 전체 판의 도달 가능성을 완전히 바꿀 수 있기 때문에, 이 게임은 작은 독립적인 작업들로 분해될 수 없다. 이를 해결하려면 단 하나의 움직임을 실행하기 전에 모든 상호작용을 고려한 총체적인 계획이 필요하다. 수십 년 동안, 이러한 종류의 새로운 유효한 퍼즐을 생성하는 능력은 하나의 도전 과제였다. 왜냐하면 풀 수 있는 미로를 만드는 것은 그것을 푸는 것만큼이나 어렵고, 미로가 제대로 작동하는지 확인하려면 모든 가능한 움직임을 시뮬레이션하기 위해 강력한 컴퓨터가 필요하기 때문이다.

최근 한 연구는 컴퓨터에게 문제를 푸는 법을 가르치지 않고도 이러한 복잡한 퍼즐을 생성하는 놀라운 방법을 발견했다. 연구진은 인공지능 모델이 주변 글자를 바탕으로 빈칸의 단어를 추측하며 크로스워드 퍼즐을 완성하는 인간처럼, 소코반 격자의 누락된 조각들을 채우도록 훈련시켰다. 모델은 수천 개의 실제 퍼즐을 보여주며 벽, 바닥, 상자의 패턴을 학습하도록 했지만, 어떤 퍼즐이 풀 수 있는 것인지 알려주지 않았으며, 작동하는 게임을 만드는 것에 대한 보상도 주지 않았다. 모델은 단지 눈에 보이는 타일들을 바탕으로 숨겨진 위치에 어떤 타일이 들어가야 하는지를 예측하는 법을 배웠을 뿐이다. 결과는 놀라웠다. 모델이 처음부터 새로운 퍼즐을 생성했을 때, 그중 77.4퍼센트가 풀 수 있는 것이었다. 이는 모델이 솔버빌리티(solvability, 해결 가능성)를 보장하도록 명시적으로 훈련받지 않았음에도 불구하고, 단지 빈칸을 채우도록 훈련받았을 뿐인데 얻어낸 놀라운 결과이다. 연구진은 풀 수 있는 퍼즐을 만드는 능력이 모델이 배운 별개의 기술이 아니라, 게임의 국소적(local) 패턴을 학습하는 과정에서 나타난 자연스러운 부산물임을 발견했다.

이 접근 방식의 성공은 모델이 격자를 어떻게 생각하느냐에 달려 있다. 텍스트를 작성하는 것과 같이 순차적인 데이터를 생성하는 전통적인 컴퓨터 프로그램은 첫 번째 단어를 결정하고, 그다음 두 번째, 세 번째를 결정하는 고정된 순서로 작동한다. 이러한 선형적 접근 방식은 소코반을 다루는 데 어려움을 겪는데, 격자 초기에 내린 결정이 격자 끝부분에 가능한 것을 제한하여 프로그램이 나중에 수정할 수 없는 충돌을 만들기 때문이다. 그러나 이 연구에 사용된 모델은 고정된 순서를 따르지 않는다. 모델은 모든 셀이 숨겨진 완전히 빈 격자에서 시작하여, 무작위 순서로 하나씩 드러내며 진행한다. 각 단계에서 모델은 현재 상태의 전체 판—여기에 있는 벽, 저기에 있는 상자, 그리고 다른 곳의 빈 공간들—을 살피고, 다음 숨겨진 위치에 무엇이 적절한지를 결정한다. 이를 통해 모델은 한쪽 구석에 벽을 배치하고 반대쪽 구석에 목표물을 둔 다음, 새로운 조각을 드러낼 때마다 전체 판에 대한 이해를 조정하며 그 둘을 연결하는 통로를 찾아낼 수 있다. 이러한 유연성은 인간 플레이어가 게임에 대해 생각해야 하는 방식, 즉 판의 먼 부분들 사이의 비국소적(non-local) 상호작용에서 난이도가 발생한다는 점을 반영한다.

이 방법이 얼마나 잘 작동하는지 테스트하기 위해 연구진은 5만 개의 새로운 퍼즐을 생성하고 표준 솔버(solver)로 각각을 확인했다. 그들은 거의 4분의 3의 퍼즐이 즉시 풀 수 있다는 것을 발견했다. 더욱 의미 있는 것은 풀 수 없는 퍼즐들에 일어난 현상이었다. 풀 수 없는 경우의 94.5퍼센트에서, 내부 벽 하나를 제거하는 것만으로도 퍼즐을 고칠 수 있었다. 이는 모델이 단순히 무작위로 추측한 것이 아니라, 약간의 사소한 오류가 해결을 가로막고 있을 뿐 거의 완벽하게 올바른 구조를 만들고 있었음을 시사한다. 연구진은 또한 모델이 훈련 중에 본 퍼즐들을 단순히 암기한 것이 아닌지 확인하기 위해, 생성된 퍼즐을 기존 데이터셋과 비교했다. 그 결과 생성된 퍼즐들이 실제 보지 못한 퍼즐들과 마찬가지로 훈련 데이터와 똑같이 차이가 있음을 발견했다. 모델은 특정 사례의 목록을 배운 것이 아니라 게임의 기저에 깔린 구조를 학습한 것이다.

연구는 또한 연구진이 모델의 확신도를 조절했을 때 모델의 행동이 어떻게 변하는지 탐구했다. 모델이 자신의 선택에 더 단호하게 만들면, 평소보다 벽이 약간 더 많은 퍼즐을 만드는 대가를 치르더라도 솔버빌리티 비율을 거의 99퍼센트까지 높일 수 있었다. 그러나 기본 설정은 원래 훈련 세트에 있는 벽의 밀도와 완벽하게 일치하는 퍼즐을 만들어냈다. 구조와 무작위성 사이의 이러한 균형이 핵심이다. 모델은 유효한 퍼즐이 되기 위해서는 벽과 상자가 매우 특정한 방식으로 어우러져야 한다는 것을 배웠고, 빈틈을 올바르게 채우는 법을 배움으로써 의도치 않게 해결 가능성의 규칙을 학습했다. 연구진은 개별 타일을 예측하는 능력이 향상되는 것을 멈춘 후에도 솔버빌리티라는 전역적(global) 속성에 대한 모델의 성능이 계속 개선되었다는 점에 주목했다. 이는 두 목표가 별개임을 나타낸다. 즉, 모델이 단일 타일을 잘 채울 수는 있어도 전체 퍼즐을 잘 만드는 것은 아닐 수 있지만, 이 경우에는 국소적인 세부 사항을 마스터하는 것만으로도 전역적인 해결책을 여는 데 충분했다는 것이다.

이 발견의 함의는 단순히 더 나은 퍼즐을 만드는 것을 넘어선다. 이는 단순한 국소적 훈련 목표로부터 복잡한 전역적 속성이 나타날 수 있음을 보여준다. 모델은 퍼즐이 풀려야 한다고 배운 적이 없었음에도 불구하고, 그렇게 만들 수 있는 법을 배웠다. 이는 데이터 자체의 구조 안에 해결책의 논리가 포함되어 있으며, 시스템의 모든 부분 간의 관계를 이해할 수 있는 모델은 그것을 해결하는 능력까지 물려받을 수 있음을 시사한다. 연구진은 모델이 생성을 유도하기 위해 숨겨진 솔버를 사용하지 않았음을 확인했다. 과정의 모든 단계는 격자의 가시적인 부분들에 기반한 모델 자신의 예측에 의해 구동되었다. 모델이 해결 경로를 전혀 보지 않고도 풀 수 있는 미로를 생성할 수 있었다는 사실은, 시스템의 패턴을 깊이 있게 학습하여 그 가장 어려운 속성까지 재현해 낼 수 있는 힘을 입증한다.

결국, 이 연구는 문제를 생성하는 것과 해결하는 것 사이의 장벽이 이전에 생각했던 것만큼 높지 않음을 보여준다. 모델에게 단순히 패턴을 완성하도록 훈련시킴으로써, 연구진은 유효하고 복잡한 도전을 만들어내는 능력을 끌어냈다. 모델은 플레이할 가치가 있는 게임을 만들기 위해 그 게임의 그랜드마스터가 될 필요가 없었다. 단지 타일들의 규칙을 이해하기만 하면 되었다. 이 접근 방식은 인공지능을 생각하는 새로운 방법을 제시하며, 만약 우리가 시스템에게 복잡한 세계 내의 국소적 관계를 이해하도록 가르친다면, 그 시스템이 명시적으로 배우지 않더라도 자연스럽게 그 세계의 전역적 과제를 헤쳐 나가는 법을 배울 수 있음을 시사한다. 생성된 퍼즐들은 완벽하지는 않았지만, 아주 작은 조정만으로도 작동할 수 있을 만큼 근접해 있었으며, 이는 모델이 게임의 본질을 파악했음을 증명했다.