RL : Monte Carlo Tree Search (MCTS)

밑에는 알파고의 spec이다

Core	Algorithm
Deep Learning : Policy & Value	MCTS : predict best condition
CPU : 1000 operation / 1s simulation	RL : find best action
GPU : calculate state & predict next step	Policy & Value : provide baseline of odds in expansion step

실제로 알파고는 ‘Policy Function’과 ‘Value Function’이라 불리는 2개의 신경망으로 구성되었는데,

Policy Function이 다음 번 돌을 놓을 여러 경우의 수를 제시하면,

Value Function은 그중 가장 적합한 한 가지 예측치를 제시하는 역할을 한다.

이 과정에서 모든 경우의 수를 다 계산하는 것은 불가능하므로, 표본을 추출하여 승률을 어림잡는 몬테카를로 방법을 적용하는 것이다.

 

물론 그렇다고 하여 알파고가 인간과 똑같은 ‘직관과 추론’을 하여 바둑 게임에서 이겼다고 말하기는 어려울 것이다. 그러나 딥 러닝과 몬테카를로 방법으로 인간의 직관과 추론을 흉내 내었고, 그 성능이 바둑에서 인간을 능가하였다는 점에서 기존 인공지능의 한계를 돌파한 획기적인 사건으로 볼 수 있었다.

 

이처럼 엄청난 성능을 내는 Monte Carlo Method 를 적용한 Monte Carlo Search Tree 에 대해 포스팅 할 것이다.

기본개념

1. 무작위로 랜덤수를 생성한다.
2. 생성한 랜덤수를 기반으로 사용해서 구하고자 하는 정보의 확률을 계산한다.
3. 난수 생성이 무한에 가까워 질 경우 우리가 원하는 정보의 실제 값으로 근사한다.

목표

현실에서 우리가 만나는 데이터들은 상당히 한정적이고 적다.

따라서 이런 경우를 해결하기 위해서는 여러 변수들을 제외하고 실제보다 단순하게 모델을 구성한 뒤,

수 많은 케이스를 가지고 모델을 실험해야 한다.

실험횟수, 반복횟수가 점점 많아질 수록 얻는 값은 실제 값에 근사하게 된다는 것이 기본적인 목표이다.

 

조건

1. 게임의 최소/최대 점수 값이 있어야 한다.
2. 게임의 규칙이 정해져 있으며 완전정보 게임이다.
3. 게임의 길이가 제한, 비교적 빨리 simulation이 끝나야한다.

 

구조

MCTS 구조

1. Selection

현재 노드에서 어떠한 자식 노드로 넘어가야할지 결정하기 위해 random 수, 무작위추출을 이용한다.

따라서 root부터 현재까지 펼쳐진 무작위 트리를 선택한다.

2. Expansion

선택한 트리에서 게임이 종료가 된다면 Backpropagation을 통해 결과를 update한다.

게임이 종료되지 않는다면, 하나 이상의 자식노드를 생성하여 하나를 선택한다.

 

3. Simulation

확장된 자식노드에서 게임의 simulation을 돌려 게임의 종료가 될 때까지 시행한다.

게임이 종료가 되지 않는다면, 다시 Expansion을 한다.

 

4. Backpropagation

선택된 자식노드에 simulation 결과를 반영한다.

simulation 결과에 기초하여 기록된 값은 방문한 횟수와 simulation 결과로 나온 점수를 포함해야한다.

 

내가 이해한 느낌

1. 처음 training을 하는 과정에서 합성이 잘 된 case와 합성이 잘 안된 case 두 가지의 data들을 승패 결과 비교 data.

2. tree는 처음 selection은 무작위 추출을 할 것이고, expansion과 simulation을 한 결과들을 위의 data와 비교.

3. Backpropagation을 통해 정보 업데이트.

4. 만든 model을 기준으로 input data들을 판단.

 

참조

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

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

https://m.blog.naver.com/PostView.nhn?blogId=msnayana&logNo=220433811867&proxyReferer=https%3A%2F%2Fwww.google.com%2F

몬테카를로 트리탐색 (Monte Carlo Tree Search) MCTS

https://mongxmongx2.tistory.com/17

Monte Carlo Tree Search 알고리즘(MCTS)

http://codingdojang.com/scode/507?langby=#answer-filter-area

코딩도장