Monte Carlo

• 확률 계산 알고리즘
• 정확한 확률 분포를 구하기 어려울 때 무작위 표본 추출을 통해 확률 분포를 도출하는 방법론

Tree Search

• 트리 모양으로 뻗어져 있는 검색 방법

MCTS MonteCarloTreeSearch

• TreeSearch에 MonteCarlo 알고리즘을 응용한 것으로 어떤 상태에서 게임이 종료될 때까지 모든 경우의 수를
  탐색하지 않고, 랜덤한 수를 두어가면서 게임을 한번 끝까지 진행해본다.

Upper Confidence Boundary of Tree

어느 정도 학습이 되어 있는 경우(SL) 선택 단계에서 이미 보상 결과가 좋은 것만 선택하게 되어 (Exploitation)과 탐사(Exploration)의 균형이 깨지게 된다. 이를 아용-탐사 딜레마라고 일컫으며, 이를 해결하기 위해 UCT가 사용된다.

적절한 브랜치(Leaf Node)를 찾는 법

• UCB1 수식 (Upper Confidence Boudnary)
  

Xj = 평균 보상
nj = 자식 노드의 방문-탐사(visit) 횟수
n = 부모 노드의 방문-탐사(visit) 횟수

덜 방문 했을 수록 방문-탐색의 가능성이 커짐.