몬테카를로 트리 탐색

한 줄 정의: 가능한 모든 수를 다 따져보는 대신, 유망해 보이는 몇몇 수를 골라 끝까지 임의로 시뮬레이션해보고 그 결과를 바탕으로 다음 수를 결정하는 탐색 방법입니다.

쉽게 풀면

바둑이나 체스처럼 한 수마다 가능한 경우의 수가 엄청나게 많은 게임에서는 모든 경우를 끝까지 계산하는 것이 사실상 불가능합니다. 몬테카를로 트리 탐색(MCTS)은 (1) 지금까지 성적이 좋았던 수를 우선 골라보고(선택), (2) 아직 안 가본 새로운 수를 트리에 추가하고(확장), (3) 그 지점부터 게임이 끝날 때까지 무작위로 대충 진행시켜 보고(시뮬레이션), (4) 그 결과(이겼는지 졌는지)를 거슬러 올라가며 각 수의 "성적표"에 반영합니다(역전파). 이 네 단계를 수없이 반복하면, 실제로 승률이 높은 수들이 점점 더 자주 선택되면서 좋은 수를 효율적으로 찾아내게 됩니다.

왜 중요한가

바둑, 체스와 같은 게임뿐 아니라 로봇 경로 계획, 자원 배분, 스케줄링처럼 상태 공간이 방대해 모든 경우를 다 따질 수 없는 순차적 의사결정 문제는 매우 흔합니다. 몬테카를로 트리 탐색은 완전 탐색 없이도 무작위 시뮬레이션을 반복해 통계적으로 유망한 선택지를 좁혀나갈 수 있어, 강화학습과 결합되면서 다양한 계획 수립 문제에 적용할 수 있는 범용 탐색 프레임워크로 주목받았습니다.

논문에서는 이렇게 쓰입니다

"제안 모델은 정책망과 가치망의 예측을 몬테카를로 트리 탐색과 결합하여 탐색 공간을 효율적으로 줄였다."

이 문장은 "신경망이 유망한 수를 미리 추려주고, 그중에서 몬테카를로 트리 탐색으로 실제 진행 결과를 시뮬레이션해 최종 결정을 내렸다"는 뜻입니다. 알파고와 같은 보드게임 인공지능뿐 아니라, 경우의 수가 방대한 계획 수립·자원 배분 문제 등 순차적 의사결정이 필요한 다양한 연구에서 활용됩니다.

"로봇 경로 계획 문제에서 몬테카를로 트리 탐색을 적용하여 장애물이 동적으로 변화하는 환경에서도 실시간에 가까운 경로 선택이 가능함을 보였다."

로봇공학에서 매 순간 변화하는 환경 속에서 다음 이동 경로를 빠르게 결정하는 데 이 탐색 방법을 활용했다는 뜻이다.

"자원 스케줄링 문제를 트리 형태로 모델링하고 몬테카를로 트리 탐색을 통해 근사 최적해를 탐색하는 프레임워크를 제안하였다."

완전탐색이 불가능한 조합최적화 문제를 트리 구조로 표현하고, 무작위 시뮬레이션을 반복해 실용적인 수준의 해를 찾아냈다는 의미다.

조금 더 깊게 보면

선택 단계에서 어떤 자식 노드를 탐험할지 정할 때는 흔히 UCT(Upper Confidence bound applied to Trees)라는 공식을 사용해, 지금까지 성적이 좋았던 수(활용)와 아직 충분히 시도되지 않은 수(탐험) 사이의 균형을 조절합니다. 알파고 이후에는 무작위 시뮬레이션 대신 신경망이 학습한 가치 추정치로 국면을 평가하는 방식이 널리 쓰이면서, 순수한 몬테카를로 시뮬레이션 없이도 몬테카를로 트리 탐색의 틀만 유지하는 변형들이 등장했습니다.

주의할 점

몬테카를로 트리 탐색은 이름이 비슷한 몬테카를로 시뮬레이션과는 다른 개념입니다. 몬테카를로 시뮬레이션은 무작위 표본을 반복 추출해 확률적 결과를 추정하는 일반적인 통계 기법이고, 몬테카를로 트리 탐색은 그 무작위 시뮬레이션을 "트리 구조의 탐색"에 결합해 다음 행동을 선택하는 의사결정 알고리즘이라는 점에서 목적과 쓰임이 다릅니다.