Monte Carlo Tree Search

강화학습 공부를 하면서 몬테카를로 트리 탐색에 대해 알게되어 검색해보니 Decision making 알고리즘 중 하나.

 

 

몬테카를로 트리 탐색 : 의사결정을 하기위한 탐색 알고리즘.

어떻게 움직이는 것이 가장 좋은지 분석하면서 random sampling을 해서 search tree를 확장해나간다.

몬테카를로 트리 탐색은 매번 네 단계를 거친다.

1. selection
2. expansion
3. simulation
4. backpropagation

selection

루트 노드에서 시작해서 자식 노드를 선택하면서 내려가서 리프 노드에 다다른다. 가장 승산있는 수로 확장시킬 자식 노드를 선택한다.

expansion

리프 노드에서 게임이 종료된다면 하나 이상의 자식 노드를 생성하고 그 중 하나의 노드 C를 선택한다.

Simultion

확장을 통해 선택한 C로부터 랜덤 플레이아웃을 실행한다.

Backpropagation

플레이아웃의 결과로 C 노드부터 루트 노드까지의 노드 정보를 갱신한다.

 

몬테카를로 트리 순회의 각 단계의 예:  선택 ,  확장 ,  시뮬레이션 ,  역전달

 

 

 

참고자료

https://ko.wikipedia.org/wiki/%EB%AA%AC%ED%85%8C%EC%B9%B4%EB%A5%BC%EB%A1%9C_%ED%8A%B8%EB%A6%AC_%ED%83%90%EC%83%89

몬테카를로 트리 탐색 - 위키백과, 우리 모두의 백과사전