MCTS(Monte Carlo Tree Search)

선택, 확장, 시뮬레이션, 역전파, 경로탐색, 알파고

---

I. 인공지능 알파고의 탐색 알고리즘, MCTS의 개요

가. MCTS(Monte Carlo Tree Search)의 정의

   - 최소, 최대 알고리즘의 성능을 개선하여 전체 경로 탐색이 불가능 할 때 효율적 경로 탐색이 가능한 알고리즘

---

II. MCTS의 동작방식과 주요정책

가. MCTS의 동작방식

구분	설명
동작 개념도
동작단계	선택à확장à시뮬레이션à역전파

- 선택 단계에서 게임이 종료할 때까지 랜덤 선택만 하는 순수 MCTS방식은 탐색 깊이가 깊어져 옳은 해를 찾을 수 있지만 탐색 속도는 느려 짐

나. MCTS의 주요정책 및 적용을 위한 3조건

구분	상세설명
주요 정책	Tree Policy	- 이미 존재하는 서치 트리에서 Leaf노드 선택하거나 생성 정책
	Default Policy	- 주어진 non-terminal state에서 value를 추정하는 정책
	Best Child Selection	- 최선의 승률이 예측되는 자식 노드를 선택하는 정책
3조건	1. 게임의 최대/최소 점수 값이 존재
	2. 게임의 규칙이 정해져 있으며, 게임이 완전 정보 게임이어야 한다.
	3. 게임의 길이가 제한되어 비교적 빨리 게임이 끝나야 한다.

- 정책을 어떻게 정하느냐 에 따라 MCTS 알고리즘의 종류가 결정

 

III. MCTS 알고리즘을 적용한 알파고

- 구성요소: MCTS, 강화학습, 정책망, 가치망, 딥러닝, CPU, GPU