인공지능) Tree search2

§ MCTS ( Monte- Carlo Tree Search)

* 몬테 카를로 : 공식이 없어도 시뮬레이션만 수행하면 풀 수 있다.

( 대표적인 예 : 파이(3.141592...) - 랜덤 시뮬레이션으로 품 )

==> 게임 트리를 성장시켜보며 시뮬레이션 하는 기법

- Exploration (탐색) : 새로운 것을 찾는 것

- Exploitation (활용) : 내가 알던 것을 활용하는 것

이 둘 중, 무엇을 중요시 할 것인가에 대한 딜레마가 있다.

○ Bandit Problems : 슬롯 머신을 돌릴 때, 하나의 머신에서 하겟는가? 아니면 여러 머신에서 하겠는가?

- UCB1 : 공식을 이용 --> 현실에서 가장 많이 사용

- Flat Monte Carlo : 동일한 확률

- e-Greedy (입실론 그리디) : e만큼 무작위로 --> (1-e) 만큼 가장 좋은 것

○ UCB1

보편화 된 게임에선

c의 값을 조정함으로서 밸런스 조정

○ MCTS는 불균형 트리를 만든다.

--> 방문 하는 곳만 다시 가기 때문에

--> 상수 c는 경험적으로 조정

○ MCTS 의 과정

Selection -> Expansion -> Simulation -> Backpropagation