2016/05
-
Monte Carlo Tree Search 알고리즘(MCTS)Deep Learining 2016. 5. 4. 20:13
Monte Carlo Tree Search 알고리즘(MCTS) 1. 개요 MCTS는 주로 게임 AI에서 사용되는 알고리즘이다. 이 알고리즘은 최근에 알파고에 사용되었다. 현재 이 MCTS 알고리즘은 바둑, 체스, 오셀로 등의 모든 보드 게임 알고리즘에서 사용되고 있다. MCTS는 시뮬레이션을 통해 가장 승률이 좋은 행동을 하도록 하는 알고리즘이다.MCTS는 각 상태에서 움직일 수 있는 곳이 정해져 있어야 한다. MCTS는 이름이 말해주듯이 "game tree" 안에서 작동한다. 알고리즘의 시작은 이 트리의 루트노드로 부터 시작되며 자식노드는 새로운 게임 상태에 대한 정보를 나타낸다. 2. MCTS의 조건 MCTS는 다음 3가지 조건을 만족할 때 사용가능하다. 1) 최대, 최소 값이 존재2) 게임 규칙의 ..