몬테카를로 트리 탐색(MCTS)

I. 효율적 경로 탐색, 몬테카를로 트리 탐색

가. 몬테카를로 트리 탐색의 정의

전체 경로 탐색 불가능 시 효율적 경로 탐색을 통해 최적의 판단을 수행하는 알고리즘

나. 몬테카를로 트리 탐색의 특징

정책
(Policy)
– 확장 단계에서 가장 높은 승률을 예측
– 트리 검색의 ‘폭’을 제한
가치
(Value)
– 현재 승산을 나타내는 역할
– 트리 검색의 ‘깊이’ 제한 역할

 

II. 몬테카를로 트리 탐색 절차

① 선택– 현재 상태에서 특정 경로 예측(수 읽기)
② 확장– 경로 예측 후 해당 지점에서 트리 확장
③ 시뮬레이션– ② 선택 시 종료시점까지 경로 예측
④ 역전파– ③ 결과 종합하여 노드 가치, 승산 예측
① ~ ④ 반복– CPU/GPU 기반 반복 처리, 정확도 증대

– GPGPU 같은 인프라의 발전으로 알파고, 왓슨, 엑소브레인 등 인공지능 발전 중

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^