몬테카를로(Monte-Carlo)는 모나코 공국의 10개 행정 구역 중 하나로, 카지노와 도박장으로 유명한 곳이다. 함수의 값을 확률적으로 계산하는 알고리즘을 몬테카를로 방법(Monte Carlo Method)이라고 하는데 도박의 도시에서 유래되었다.
광주과학기술원(GIST, 총장 임기철)은 AI대학원 안창욱 교수 연구팀이 대체 모델(Surrogate Model)을 기반으로 개발한 몬테카를로 트리 탐색(MCTS)* 방법을 실시간 상용 비디오 게임(Real-time Video Game)인 ‘스타크래프트 II’에 적용해 기존 MCTS에 비해 1만 배 빠르게 게임 상황을 예측함으로써 탐색 효율성과 성능 안정성을 획기적으로 향상시켰다고 밝혔다.
MCTS는 매우 효과적인 상황 예측 기법임에도 불구하고 그 복잡성이 높아 이전에는 스타크래프트와 같은 실시간 전략 게임(Real-time Strategy, RTS)에는 적용 자체가 불가능했으나, 이번 연구 성과로 게임뿐 아니라 실세계 문제에도 적용할 수 있을 것으로 기대된다.
몬테카를로 트리 탐색(Monte Carlo Tree Search, MCTS)은 복잡하고 불확실성이 있는 환경에서 의사결정을 위한 체험적 탐색 알고리즘으로, 게임을 할 때 주로 적용된다. 어떻게 움직이는 것이 가장 최적의 판단인지를 분석하면서 검색 공간에서 무작위 추출에 기초한 탐색 트리를 확장하는 데 중점을 둔다.
무작위 시뮬레이션을 기반으로 상황 예측에 대한 기댓값을 추정하는 기존 MCTS 기법은 실행 시간이 오래 걸리고 복잡하여 높은 연산량이 요구되는 실시간 상용 RTS 게임에 적용하는 데 한계가 있다.
특히 대표적 실시간 전략 게임인 스타크래프트 II는 각 게임 참여자가 제한적 환경 관측만 가능한 여건에서 자원 확보와 상대편의 종족․동태 등을 종합적으로 고려하여 게임을 운영해야 하기 때문에 복잡성이 매우 높다.
연구팀은 새로운 강화학습법을 통해 가상으로 재현된 게임 데이터를 학습해 대체 모델을 구축하고 이를 활용하여 시뮬레이션의 일부 결과만으로 상황 예측에 대한 기댓값을 추정할 수 있는 대체 모델 기반 MCTS 기법을 제안하였으며, 스타크래프트 II에 적용하여 그 성능을 검증하였다.
연구팀이 개발한 기법은 기존 MCTS와는 달리 대체 모델을 활용하여 게임 내 상태에 대한 기댓값을 시뮬레이션 없이 바로 추정하여, 짧게는 몇 분에서 길게는 몇 시간 걸리던 시뮬레이션 추론 시간을 밀리초(1천분의 1초)에서 초 단위 범위로 줄이는 데 성공했다.
이와 더불어 연구팀은 연구의 확장성과 재현성을 높이기 위해 대체 모델 학습을 위한 데이터 수집과 스타크래프트 II에서 데이터 분석이 가능한 자체 소프트웨어를 구현하는 데 성공했다.
수집된 데이터를 기반으로 대체 모델을 학습한 후 적용한 결과, 게임의 진행 결과를 기존 MCTS 대비 1만(104) 배 빠르게 예측했다.
안창욱 교수는 “이번 연구 성과는 몬테카를로 트리 탐색 기법의 활용이 불가능하던 실시간 게임 환경에서 각 개체의 실시간 행동(예, 공격, 후퇴 등) 결정을 가능하게 했다는 데 의의가 있다”며 “향후 상충하는 이해관계 갖는 실세계 응용 문제(자율주행, 주식거래 등)에 있어 실시간 의사결정을 내리는 데 활용될 수 있을 것으로 기대된다”고 말했다.
이번 연구는 한국연구재단 중견연구자지원사업과 정보통신기획평가원(IITP) 인공지능대학원 사업의 지원을 받아 수행되었으며, 연구 결과는 다학제 공학 분야 상위 2.5% 국제학술지 《Engineering Applications of Artificial Intelligence》에 2024년 7월 1일 게재되었다.
