보드게임 시타델에서 몬테카를로 트리 탐색 기반 모델 훈련을 위한 상대방 모델링

1. 서론

몬테카를로 트리 탐색(MCTS)은 보드 게임에서 의사 결정을 위한 효과적인 기법으로 자리 잡았으며, 적응성과 도메인 특화 지식의 낮은 사용을 결합합니다. 그 성능은 바둑과 같은 완전 정보를 가진 결정론적 게임에서 두드러집니다(SILVER et al., 2016).

그러나 다중 플레이어, 숨겨진 정보, 시간 제약이 있는 환경에서는 시뮬레이션의 높은 계산 비용과 적응의 어려움으로 인해 응답성과 결정의 질이 저하되어 적용에 상당한 한계가 있습니다(POWLEY et al., 2014).

이러한 맥락에서 MCTS와 강화 학습(RL)을 통합하는 하이브리드 접근 방식은 계획 단계를 실행과 분리함으로써 유망함을 보여주고 있습니다. 검색을 사전에 저장하여 지속적인 결정 구조를 구축하면 게임 중 즉각적인 행동 선택이 가능해져 온라인 시뮬레이션의 필요성을 줄이고 전략적 깊이를 유지합니다(BROWNE, 2012; SWIECHOWSKI, 2023).

이 연구에서는 오프라인 강화 학습 기술을 결합한 하이브리드 MCTS 모델을 테스트하고 개발했습니다. 모델은 보드 게임 시타델(FAIDUTTI, 2016)의 시뮬레이션 환경에서 다양한 상대를 사용하여 훈련 및 테스트되었습니다.

2. 일반 목표

이 연구의 일반적인 목표는 숨겨진 정보가 있는 멀티플레이어 보드 게임에서 효율적으로 작동할 수 있는 하이브리드 MCTS-RL 프레임워크를 개발하는 것이며, 시타델을 사례 연구로 사용합니다.

제안은 지속적인 결정 구조의 오프라인 구축을 통해 전통적인 MCTS의 계산 병목 현상을 제거하여 런타임에 빠르고 강력한 행동을 가능하게 하는 것을 목표로 합니다.

3. 방법론

이 연구는 질적-양적 분석을 적용한 응용 실험 연구로 특징지어집니다.

첫 번째 단계는 보드 게임 시타델을 위한 디지털 시뮬레이션 환경의 개발 및 적응을 포함했습니다. 그 다음으로 인간 플레이어가 사용하는 실제 전략을 모방하도록 구축된 맞춤형 전략을 가진 5개의 전문 에이전트와 무작위로 행동을 선택하는 기준 에이전트의 개발이 이루어졌습니다. 환경과 개발된 에이전트의 검증 후, 하이브리드 MCTS-RL 프레임워크의 개발이 시작되었습니다.

MCTS 모델은 본질적으로 여러 시뮬레이션 실행을 통해 작동하는 휴리스틱 검색 알고리즘입니다. 이러한 시뮬레이션 중 방문하는 각각의 게임 상태에 대해 트리 데이터 구조에 해당 노드가 생성됩니다. 초기 게임 상태는 이 트리의 루트 노드를 나타냅니다.

그러나 전체 트리를 저장하고 미래의 결정을 위해 보존하는 제안은 엄청난 분기 계수로 인해 실행 불가능합니다. 이를 가능하게 하려면 트리를 추상화해야 합니다. 게임 상태는 기본 특성(예: 플레이어의 골드, 손에 든 카드 수)으로 나뉘고, 각 특성은 독립적인 데이터 테이블에 매핑됩니다.

이 구조에서 테이블의 행은 상태 특성의 가능한 값을 나타내고, 열은 에이전트가 취할 수 있는 가능한 행동(예: 골드 획득, 카드 뽑기)을 나타냅니다. 각 셀에는 두 값이 저장됩니다. 해당 상태에서 해당 행동을 취한 후 달성한 승리 횟수(n)와 이 조합이 탐색된 총 횟수(m)입니다. 이러한 테이블은 시타델 게임의 시뮬레이션을 통해 채워지면서 에이전트의 학습된 모델을 구성합니다.

훈련 과정에는 강화 학습 구성 요소가 포함됩니다. 각 시뮬레이션 게임 후 결과는 결정 테이블을 업데이트하여 미래의 선택에 영향을 줍니다. 승리는 보상으로 작용하여 효과적인 행동을 강화하고 다시 선택될 확률을 높이는 반면, 패배는 이 가능성을 줄입니다. 따라서 많은 시뮬레이션을 통해 모델은 지속적으로 적응하며, 새로운 대안의 탐색과 입증된 전략의 활용 사이의 균형을 맞추고 점차 더 효과적인 행동으로 수렴합니다.

4. 결과 및 논의

제안된 MCTS 모델의 성능을 평가하기 위해, 기준 전략(전문 에이전트 및 무작위 에이전트) 간의 파워 역학을 이해하는 것이 중요했습니다. 이를 위해 각 전략은 4명의 동일한 상대와 10,000번의 매치를 한 라운드로 진행했습니다.

그림 1의 히트맵은 각 전략(Y축)이 다양한 상대(X축)에 대해 보이는 성능을 보여줍니다. 전략들은 각각 뚜렷한 강점과 약점을 가지고 있습니다: 전문가 1, 2, 3은 대부분의 시나리오에서 유능한 반면, 전문가 4와 5는 상당히 덜 효과적입니다. 예상대로 완전 무작위 전략은 최소한의 구조를 가진 상대에 대해 매우 낮은 성능을 보입니다.

그림 1: 전략 간 비교.

다음 단계는 MCTS-RL 모델을 평가하는 것이었다. 각각 상대 중 하나에 초점을 맞춘 여러 훈련 세션이 진행되었으며, 각 모델 버전에 대해 총 100,000번의 훈련 매치가 수행되었다. 그런 다음, 각 훈련된 모델의 성능을 이전과 동일한 테스트 모델을 사용하여 모든 유형의 상대와 무작위로 추출된 다양한 상대에 대해 측정하였다.

그림 2에 표시된 히트맵은 각 모델의 통합 승률을 보여준다. 가장 주목할 만한 결과는 다양한 환경에서 훈련된 모델이 거의 모든 테스트 시나리오에서 일관된 성능을 보이며 다른 버전의 모델을 능가한 것이다. 이는 훈련 중 다양한 전략에 노출되는 것이 더 강력하고 일반화된 플레이 능력을 개발하는 데 필수적이었음을 시사한다.

그림 2: 훈련된 모델 간 비교.

Experts 4와 5를 상대로 훈련된 모델은 가장 약한 상대로 간주되었지만, 놀랍도록 효과적인 에이전트가 되었습니다. 반대로, 강한 상대로 간주된 Experts 1과 3을 상대로 훈련된 모델은 전반적으로 매우 낮은 성능을 보였습니다.

이러한 대조에 대한 가능한 설명은 고급 전문가 전략이 매우 특화되는 경향이 있는 반면, MCTS-RL 모델은 훈련 초기에 무작위 행동에 가깝다는 것입니다. 강한 상대와의 대결에서는 잠재적으로 유리한 행동조차도 모델이 성공 패턴을 인식할 만큼 충분한 승리를 거두지 못할 수 있습니다. 반면, 덜 특화된 상대와의 대결에서는 승리가 더 자주 발생하여 학습에 유리합니다. 그러나 이는 여전히 확인이 필요한 가설입니다.

5. 결론

이 연구는 MCTS 트리의 추상화를 사용하여 이동 간에 획득한 지식을 보존하는 제안된 접근 방식의 실행 가능성을 입증했습니다. 결과는 모델이 환경에 대해 강력한 전략을 개발할 수 있음을 확인했습니다.

다양한 환경에서 훈련된 에이전트의 우수한 성능은 여러 전술에 대한 노출이 일반주의 모델을 구축하는 데 기본적임을 보여줍니다. 또한, 연구는 최종 에이전트의 품질이 훈련 상대의 명백한 강점보다 다양성에 더 의존함을 나타냅니다.

향후 연구로, 덜 전문화된 전략이 더 강력한 전략보다 더 효율적인 모델을 초래한 실제 이유를 더 정확히 탐구하는 것이 흥미로울 것입니다. 또한, 제안된 모델을 다른 MCTS 모델과 비교하는 것도 접근 방식에 대한 더 정확한 평가를 얻는 데 도움이 될 것입니다.