몬테카를로 트리 탐색: 복잡한 멀티플레이어 게임에서의 단점, 장점 및 한계에 대한 고찰

1. 서론

몬테카를로 트리 탐색(MCTS)은 선택, 확장, 시뮬레이션, 역전파의 네 단계로 의사 결정 트리를 구축하는 탐색 알고리즘 계열이다. 모든 상태에 대해 완전한 평가 함수를 요구하는 대신, 이 방법은 수많은 시뮬레이션을 통해 행동의 품질을 추정하며, 드물게 방문되는 대안의 탐험과 알려진 행동의 활용 사이의 균형을 맞춘다. 이러한 특성은 바둑, 체스, 쇼기와 같은 게임, 특히 완전 정보를 가진 2인 환경에서 뛰어난 결과에 기여했다(BROWNE et al., 2012).

그러나 현대의 디지털 및 테이블탑 게임은 더 복잡한 조건을 제시한다: 여러 상대, 숨겨진 정보, 무작위성, 큰 행동 공간, 실시간 결정 등이다. 이러한 상황에서 시뮬레이션을 한 번 더 추가한다고 해서 항상 더 나은 결정이 나오는 것은 아니다. 플레이어 수가 많아지면 탐색 트리가 커지고 상대방의 응답을 모델링하기 어려워진다. 불완전 정보는 숨겨진 상태가 부적절하게 처리될 때 전략 융합을 일으킬 수 있으며, 시간 압박은 사용 가능한 계산 예산을 감소시킨다. 이러한 시나리오에서 MCTS의 적용이 증가하고 있음에도 불구하고, 문헌은 여전히 파편화되어 있고 고전 게임에 집중되어 있다.

2. 목표

이 연구의 일반적인 목표는 멀티플레이어 디지털 및 테이블탑 게임, 특히 불완전 정보, 확률성, 시간 제약이 있는 환경에서 MCTS의 반복되는 한계를 식별하고 정리하는 것이었다.

구체적인 목표로, 이 연구는 이러한 한계를 완화하는 전략을 수집하고, 향후 연구를 안내하며 더 비교 가능하고 재현 가능한 평가를 촉진할 수 있는 연구 격차를 식별하고자 했다.

3. 방법론

2013년부터 2025년 사이에 발표된 연구를 대상으로 문헌 검토를 수행했으며, IEEE Xplore, HAL Science Ouverte, Google Scholar 데이터베이스에서 검색했다. 검색 전략은 "Monte Carlo Tree Search"와 "MCTS"라는 용어를 디지털 게임, 보드 게임, 멀티플레이어 게임과 관련된 표현과 결합했다. 선별은 제목이나 초록이 MCTS, 직접적인 변형 또는 경쟁적 또는 협력적 게임에 적용된 하이브리드 방법을 다룬 연구를 고려했다. 범위를 벗어난 연구, 전문에 접근할 수 없는 문서, 검토의 목표와 범위가 호환되지 않는 연구는 제외했다.

검색을 통해 24개의 레코드가 검색되었으며, 그 중 2개는 쿼리 간에 중복되어 22개의 고유한 잠재적으로 관련 있는 연구(영어 17개, 프랑스어 5개)가 도출되었다. 선별 후 18개의 연구가 전체 분석을 위해 선택되었고 4개는 제외되었다. 최종 코퍼스는 IEEE Xplore에서 13개, HAL에서 3개, Google Scholar를 통해 발견된 2개의 연구를 수집했으며, 선택된 것 중 15개의 텍스트는 영어, 3개는 프랑스어였다. 연구는 게임 유형, 사용된 알고리즘, 환경 제약, 보고된 결과, 완화 전략에 따라 분류되었다. 주제 분석은 세 가지 구조적 한계 범주—성능 한계, 전술적 사각지대, 상대 모델링의 트레이드오프—와 두 가지 도메인 의존적 증폭 요인—불완전 정보와 실시간 결정—으로 구성되었다.

4. 결과 및 논의

분석된 연구들은 MCTS가 잘 정의된 상태, 중간 정도의 분기 계수, 높은 수의 시뮬레이션을 위한 충분히 큰 계산 예산을 가진 게임에서 가장 일관되게 수행된다는 것을 보여준다. 선택된 18개의 연구 중 8개는 디지털 게임을 다루었고, 6개는 보드 또는 테이블탑 게임을 조사했으며, 나머지는 카드 게임, 일반 게임 플레이 환경 또는 관련 응용을 분석했다. MCTS 기반 알고리즘은 14개의 연구에서 사용되었으며, 종종 신경망, 행동 공간 추상화, 시뮬레이션 정책, 매개변수 조정 기술과 결합되었다.

식별된 첫 번째 한계는 탐색 성능에 관한 것이다. 시뮬레이션 수를 늘리면 일반적으로 결정 품질이 향상되지만, 새로운 시뮬레이션이 이미 충분히 탐색된 궤적을 다시 방문하기 시작하면 한계 이득은 감소하는 경향이 있다. 바둑, 실시간 전략 게임, 테이블탑 게임에서 얻은 결과는 계산 예산을 두 배로 늘려도 어느 시점 이후에는 이득이 감소하거나 전혀 없을 수 있음을 보여준다. 또한, 기술 깊이에 관한 연구는 이 한계가 게임의 복잡성과 에이전트의 구성 모두에 달려 있음을 보여준다. 완화 전략에는 행동 공간 추상화, 시뮬레이션 단순화, N-Tuple Bandit Evolutionary Algorithm(NTBEA)을 통한 정책, 탐험 상수, 롤아웃 전략의 자동 조정이 포함된다(GOODMAN; PEREZ-LIEBANA; LUCAS, 2024).

두 번째 한계는 전술적 추론의 사각지대에 해당한다. MCTS는 샘플링된 연속의 평균 가치를 추정하기 때문에, 알고리즘은 특정 전술적 시퀀스, 장기적 위협 또는 드문 구성을 인식해야 하는 위치에서 실패할 수 있다. 바둑에서 사다리와 세마이 같은 상황은 숙련된 플레이어에게 명백한 전술적 구조가 탐색에 의해 식별되지 않을 수 있는 시나리오를 보여준다.

세 번째 한계는 상대 모델링에 관한 것이다. 3명 이상의 참가자가 있는 게임에서 탐색 과정은 트리의 루트에 있는 플레이어의 결정뿐만 아니라 각 상대방의 가능한 응답도 표현해야 한다. 각 상대에 대해 독립적인 구조를 유지하는 모델은 전략적 행동을 더 잘 표현하는 경향이 있지만 계산 비용을 상당히 증가시킨다. 반대로, 편집증적 탐색(Paranoid Search)과 일반화된 정책과 같은 단순화된 접근 방식은 이 비용을 줄이지만 관련 행동을 표현하지 못할 수 있다. 문헌은 선택적 초점, 상대방 응답의 일반화, 트리 분해에 기반한 접근 방식이 유망한 대안임을 시사하지만, 많은 수의 참가자가 있는 게임에서는 아직 거의 평가되지 않았다(BAIER; KAISERS, 2020).

불완전 정보는 이러한 한계를 심화시킨다. 카드 게임, 포켓몬 및 숨겨진 상태가 있는 기타 환경에서, 알려지지 않은 정보의 가능한 구성을 하나 가정하고 그것이 사실인 것처럼 탐색하는 것으로 구성된 결정화는 호환되지 않는 전략의 융합을 일으킬 수 있다. 불확실성을 처리하도록 설계된 몬테카를로 트리 탐색의 변형인 정보 집합 MCTS(Information Set MCTS)는 플레이어가 구별할 수 없는 상태를 그룹화하여 결정 시점에 실제로 사용 가능한 정보만 보존함으로써 이 문제를 줄인다(COWLING; POWLEY; WHITEHOUSE, 2012). 그럼에도 불구하고, 환경에 내재된 무작위성과 상대방의 행동을 추론해야 할 필요성은 생성된 추정의 신뢰성을 계속 제한한다.

전략 게임, MOBA, 1인칭 슈터와 같은 실시간 환경에서는 시간 제약이 중요한 요소가 된다. MCTS는 조합적 행동 공간, 다수의 유닛, 부분 관찰을 관리하면서 매우 짧은 간격으로 행동을 선택해야 한다. 이러한 맥락에서 계층적 추상화, 매크로 행동, 행동 가지치기, 지도 학습 또는 강화 학습을 통해 얻은 정책이 반복되는 전략으로 나타난다(ONTAÑÓN, 2013). 일부 상황에서는 대안 방법이 더 나은 성능을 발휘할 수 있다. 예를 들어, 롤링 호라이즌 진화 알고리즘(RHEA)은 짧은 행동 시퀀스를 진화시키고 지속적인 재계획을 수행하여, 탐색 트리가 빠르게 변하는 협력 게임과 고도로 확률적인 환경에 특히 적합함을 입증했다(SFIKAS; LIAPIS, 2022).

실시간 결정에 덜 의존하는 MCTS의 응용도 확인되었다. 예를 들어 자동 밸런싱, 플레이테스팅, 게임 디자인 지원 등이다. 이러한 시나리오에서는 처리 시간이 더 이상 중요한 제약이 아니므로 다양한 구성을 광범위하게 탐색하고, 불균형을 식별하며, 디자인 대안을 평가할 수 있다. 대부분의 연구가 제안된 접근 방식에 유리한 결과를 보고하지만, Kingdomino와 Pandemic 게임에서처럼 일부 연구는 경쟁 기술과 비교하여 MCTS의 성능이 더 낮음을 관찰했다.

5. 결론

검토는 또한 향후 연구를 위한 다섯 가지 관련 기회를 확인했다: (i) 불완전 정보가 있는 멀티플레이어 게임을 위한 공유 벤치마크의 채택 및 표준화; (ii) 더 많은 수의 참가자가 있는 게임에서 상대 모델링 기술의 체계적 평가; (iii) 인간 플레이어가 인식하는 복잡성과 탐색의 효과적 깊이 사이의 관계 조사; (iv) 픽과 밴의 이력을 고려한 3판 2선승제 및 5판 3선승제 경쟁 시리즈 연구; (v) 자동 밸런싱, 플레이테스팅, 절차적 콘텐츠 생성에서 MCTS 응용의 확장.