AI '딥큐브에이(DeepCubeA)', 루빅스 큐브 도메인 지식 없이 몇 초 만에 해결

강화학습으로 조합 퍼즐 정복… 로봇공학·자연과학 응용 기대

인공지능(AI)은 체스와 바둑에서 이미 성공을 입증했지만, 루빅스 큐브 같은 더 어려운 퍼즐은 기계 지능으로 해결되지 않았습니다. 기계 학습에 독특하고 흥미로운 도전을 제기하는 고전적 조합 퍼즐입니다.

머신러닝 기법이 이전에 루빅스 큐브 해결에 사용됐지만, 효율적이고 신뢰성 있게 퍼즐을 풀지 못했습니다. 또한 이 기법들은 특정 도메인 지식에 의존해야 했습니다.

이제 캘리포니아대 어바인(UCI) 연구진이 특정 도메인 지식 없이 엄청나게 복잡한 퍼즐을 해결할 수 있는 '딥큐브에이(DeepCubeA)'라는 심층 강화학습 접근법을 만들었습니다. 인간 코칭 없이 몇 초 만에 루빅스 큐브를 해결합니다.

차원이 증가하면 근본적 조합 퍼즐 복잡성이 급격히 증가합니다. 예를 들어 15 퍼즐 최적 해는 일반 컴퓨터에서 1초도 안 걸리지만, 24 퍼즐 최적 해는 같은 기계에서 며칠 걸릴 수 있습니다.

이 연구에서 연구자들은 인간 도메인 특화 지식에 의존하지 않고 다양한 퍼즐 해결법을 학습하는 머신러닝 모델 개발을 시도했습니다. 최첨단 세 가지 접근법을 결합해 딥큐브에이를 개발했습니다.

1. 딥러닝
2. 고전적 강화학습(근사값 반복)
3. 경로 탐색 방법(가중 A* 검색)

몬테카를로 트리 탐색과 결합된 정책·가치 함수를 사용하는 심층 강화학습 알고리즘으로 루빅스 큐브를 해결합니다.

연구자들은 텐서플로(TensorFlow) 딥러닝 프레임워크로 네트워크를 훈련했습니다 — 약 100억 회 섞인 퍼즐과 완성된 퍼즐 시뮬레이션으로 훈련했습니다. 전체 과정은 약 1,000,000회 반복으로 36시간 걸렸습니다.

참고: Nature | DOI:10.1038/s42256-019-0070-z | UCI | 온라인 데모

훈련 완료 후 딥큐브에이는 각 테스트 구성에서 100% 정확도를 달성했고, 60.3% 경우 최종 상태까지 최단 경로를 찾았습니다.

딥큐브에이는 최단 경로 비용을 과대평가하지 않는 휴리스틱 함수를 사용합니다. 가중 A* 검색은 해 길이와 최적 해 길이 간 편차에 특정 한계를 둡니다.

조합 퍼즐 넘어 응용 분야

연구팀은 24 퍼즐, 라이트 아웃(Lights Out), 소코반(Sokoban) 등 다른 퍼즐에도 딥큐브에이를 훈련했습니다. 검증 가능한 대부분 경우에서 최단 경로를 찾았습니다.

이러한 연구의 궁극적 목표는 조합 퍼즐을 넘어 로봇공학부터 자연과학까지 적용 가능한 차세대 딥러닝 모델 개발입니다.

우리는 검색 엔진과 알렉사, 시리 같은 앱으로 매일 AI와 상호작용합니다. 하지만 이 시스템들은 진짜 지능적이진 않습니다: 쉽게 조작되거나 속을 수 있습니다.

이해, 추론, 계획이 가능한 더 강건하고 똑똑한 AI를 만들어야 합니다. 이 연구는 이 거대한 목표를 향한 작은 발걸음입니다.