기술 요약: 몬테카를로 순열 탐색 (MCPS)

문제 정의

몬테카를로 트리 탐색 (MCTS) 은 게임 플레이 및 의사결정을 위한 지배적인 알고리즘이며, 특히 학습 데이터 부족이나 계산적 제약으로 인해 심층 강화학습이 불가능한 영역 (예: 일반 게임 플레이) 에서 두드러집니다. 조상 노드의 통계와 All-Moves-As-First(AMAF) 휴리스틱을 활용하여 표준 UCT 를 개선한 GRAVE(Generalized RAVE) 와 같은 MCTS 변형들이 존재하지만, 이들은 두 가지 주요 정보원에 의존합니다: 특정 수로 시작하는 플레이아웃의 통계와 해당 수가 나중에 등장하는 플레이아웃의 통계입니다.

본 논문은 기존 접근법의 한계를 지적합니다: 즉, 노드로 이어지는 수의 순서가 다른 순서로 나타나는 플레이아웃에 포함된 통계 정보를 충분히 활용하지 못한다는 점입니다. 교환 법칙이 성립하는 게임 (Hex 등) 에서는 수의 어떤 순열이든 동일한 상태에 도달합니다. 비교환 법칙 게임 (AtariGo 등) 에서는 순열이 서로 다른 상태로 이어질 수 있지만, 논문은 수들의 통계적 가치가 여전히 정보적 가치가 있다고 가정합니다. 목표는 문제별 튜닝, 모델 학습, 또는 편향 하이퍼파라미터 없이 GRAVE 를 개선하는 범용 MCTS 알고리즘을 개발하는 것입니다.

방법론

핵심 개념: 몬테카를로 순열 탐색 (MCPS)

MCPS 는 노드 평가 과정에 세 번째 통계원을 도입합니다. 경로 $(a_0, a_1, \dots, a_d)$로 도달한 노드 $s$에서 행동 $a$를 평가하기 위해, MCPS 는 세 가지 구별된 플레이아웃 집합에서 데이터를 집계합니다:

1. 직접 통계 ($Q$): $s$로 가는 경로로 시작하고 바로 뒤이어 행동 $a$가 수행되는 플레이아웃.
2. AMAF 통계 ($\tilde{Q}$): $s$로 가는 경로로 시작하며, 행동 $a$가 시퀀스 후반부에 등장하는 플레이아웃 (표준 GRAVE 접근법).
3. 순열 통계 ($\hat{Q}$): $\{a_0, a_1, \dots, a_d, a\}$ 집합의 수들이 어떤 순서로든 어떤 위치에든 포함된 플레이아웃.

가중치의 수학적 유도

논문은 이러한 세 가지 추정기를 결합하기 위한 수학적 유도를 제공합니다. 통계가 독립적이라고 가정할 때, 저자들은 결합된 추정기의 분산을 최소화하는 가중치를 유도합니다.
$n$, $\tilde{n}$, $\hat{n}$을 세 가지 통계에 대한 표본 개수라고 할 때, 최적 가중치 ($\beta, \tilde{\beta}, \hat{\beta}$) 는 표본 개수에 비례합니다:
$$\beta = \frac{n}{n + \tilde{n} + \hat{n}}, \quad \tilde{\beta} = \frac{\tilde{n}}{n + \tilde{n} + \hat{n}}, \quad \hat{\beta} = \frac{\hat{n}}{n + \tilde{n} + \hat{n}}$$
이 볼록 결합은 GRAVE 알고리즘에 사용되던 편향 하이퍼파라미터의 필요성을 없애주며, 매개변수가 없는 가중치 체계를 제공합니다.

알고리즘적 구현

• 선택 (Selection): 수의 가치는 세 추정기의 가중 평균으로 계산됩니다.
• 순열 통계 계산: $\hat{Q}$를 효율적으로 계산하기 위해, 알고리즘은 비트셋으로 표현된 최근 플레이아웃의 슬라이딩 윈도우 (기본값 $W=10,000$) 를 사용합니다. 노드 $s$에 대해, 알고리즘은 $s$로 가는 경로상의 모든 수에 대한 비트셋을 교집합하여 전체 경로 시퀀스를 포함하는 플레이아웃을 식별합니다. 그런 다음 이 결과를 후보 수 $a$의 비트셋과 교집합하여 관련 플레이아웃을 분리합니다. 이는 효율성을 위해 64 비트 워드 연산 (POPCOUNT 및 비트 스캔) 을 사용하여 수행됩니다.
• 동결 (Freezing): 노드가 임계값 방문 횟수 ($\rho=30$) 에 도달하면, 해당 노드의 순열 통계가 계산되어 "동결"됩니다. 이후 이 노드는 전체 부분 트리의 기준이 되어, 자손 노드들이 이를 재계산 없이 이러한 통계를 상속받도록 합니다.
• 수 코딩 (Move Coding): 서로 다른 보드 위치 간 지식 이전을 가능하게 하기 위해, 수들은 정확한 좌표가 아니라 게임 관련 특징 (예: 플레이어, 목적지 셀, 전투 트리거) 에 기반하여 정수 코드로 매핑됩니다.

주요 기여

1. 알고리즘적 확장: GRAVE 알고리즘을 확장하여 MCTS 선택 규칙에 순열 통계를 통합한 MCPS 제안.
2. 이론적 개선: 독립성 가정 하에 추정기 분산을 최소화하는 가중치 공식 유도 및 GRAVE 편향 하이퍼파라미터 제거.
3. 효율적인 구현: 비트셋과 슬라이딩 윈도우를 사용하여 순열 통계를 계산하는 방법으로, 수의 순서로 인한 조합적 폭발을 효율적으로 처리할 수 있게 함.
4. 범용 적용성: 특정 매개변수 튜닝 없이 다양한 게임 유형 (교환 법칙 및 비교환 법칙) 에서 알고리즘이 작동함을 입증.

실험 결과

저자들은 Hex, Go, AtariGo, NoGo, 그리고 맞춤형 비대칭 전쟁 게임 (Wargame) 등 다섯 가지 게임에 대해 MCPS 와 GRAVE 를 비교 테스트했습니다. 모든 경우, 각 구성당 800 게임이 동일한 시간 예산 하에서 수행되었으며 (각 알고리즘이 먼저 두는 경우 400 게임씩), 다음과 같은 결과가 도출되었습니다.

• Hex: MCPS 는 $7\times7$ 이상의 보드에서 GRAVE 를 능가하며, 더 큰 보드에서는 승률이 70–76% 에 달합니다. $5\times5$ 보드에서는 비트셋의 오버헤드로 인해 MCPS 가 약간 불리합니다. MCPS 가 더 깊은 트리를 구축하기 때문에 보드 크기가 커질수록 우위가 커집니다.
• Go: MCPS 는 $7\times7$ 이상의 보드에서 GRAVE 를 능가합니다. 특히 더 큰 보드 ($13\times13$, $15\times15$) 에서는 시간 예산이 증가함에 따라 승률 격차가 크게 벌어집니다 (2 초 기준 최대 63.75%). MCPS 는 시간이 늘어남에 따라 일관되게 더 깊은 트리를 구축하는 반면, GRAVE 의 트리 깊이는 종종 정체되거나 감소합니다.
• AtariGo: MCPS 는 모든 구성에서 GRAVE 를 능가하며, 작은 보드 ($5\times5$, $7\times7$) 에서 가장 큰 개선을 보입니다. 더 큰 보드에서는 게임이 종종 탐색이 종료 상태에 도달하기 전에 종료되므로 더 깊은 트리의 이점이 제한되어 우위가 감소합니다.
• NoGo: MCPS 는 가장 균일한 개선을 보여주며, 모든 셀에서 GRAVE 를 능가하고 승률은 57% 에서 69% 사이입니다. 개선은 보드 크기와 시간 예산 전반에 걸쳐 일관적입니다.
• Wargame: MCPS 는 $9\times9$ 이상의 보드에서 GRAVE 를 능가합니다. 시뮬레이션 길이가 짧아져 초당 플레이아웃 수가 15–33% 더 많아졌으며, 결정적인 게임 상태에 더 빠르게 수렴합니다.

중요성 및 주장

본 논문은 MCPS 가 심층 학습이 옵션이 아닌 시나리오를 포함한 범용 MCTS 응용 분야에서 GRAVE 보다 상당한 개선을 나타낸다고 주장합니다. 성공의 주요 메커니즘은 "더 잘 정보화된 선택 규칙"으로, 이를 통해 알고리즘은 다음과 같은 이점을 얻습니다:

• 더 깊은 탐색 트리를 구축.
• (일부 게임에서) 반복당 시뮬레이션 작업 감소.
• (AtariGo 와 같은 게임에서) 종료 상태에 더 근접하게 도달.
• (Go 에서 관찰됨) 추가 계산 시간을 유망한 라인에 대한 더 깊은 탐색으로 전환.

저자들은 이 알고리즘이 문제별 수정이나 학습이 필요 없는 범용적이라고 강조합니다. 결과는 MCPS 의 이점이 게임의 관련 의사결정 지평 내에 생성된 깊이 이득이 있을 때 가장 두드러진다고 시사합니다. 논문은 세 가지 통계원을 결합하는 개념이 순열을 넘어 다른 유형의 통계에도 재사용 가능하다고 결론지었습니다.