강화학습 겉햙기(7)[알파고와 MCTS]

알파고를 이해할때 학습과 실시간 플래닝 이라는 2단계로 나누어서 접근하면 좀더 쉽게 이해할수 있다.

알파고는 실시간으로 다양한 수를 머릿속에서 시뮬레이션 하기 때문에 이를 실시간 플래닝이라고 합니다

이에 실시간 플래닝 알고리즘으로 알파고는 MCTS를 사용합니다.

 

학습단계

MCTS는 크게 4가지 준비물을 필요로합니다.

사람의 기보를 이용해 지도 학습 정책 π_sl, 롤아웃 정책 π_roll, 스스로 대국하며 강화학습한 π_rl ,밸류 네트워크 V_rl 입니다. 요약하자면 3개의 정첵 네트워크와 1개의 밸류 네트워크를 필요로 합니다.

 

 

지도 학습 정책 π_sl

이 학습은 사람이 어디에 바둑돌은 둘것인지 분류 해주는 네트워크입니다.

학습결과 57%의 정답률을 기록했습니다.

 

 

롤아웃 정책 π_roll

롤아웃 정책은 사람 지식을 이용하여 만든 수만은 feature에 대해 선형결합 레이어가 하나 있을 뿐입니다.

롤 아웃 저액의 정확도는 24.2%입니다.

그럼에도 사용하는 이유는 계산속도가 훨씬 빠르기 때문에 MCTS 단계에서 같은시간동안 더 많은 수를 시뮬레이션 해볼수 있고, 결국 MCTS의 성능을 올려 주기 때문입니다.

 

강화 확습 정책 π_rl

 π_rl 은 π_sl과 완벽히 똑같이 생긴 뉴럴 네트워크이고, π_rl의 파라미터들은 π_sl 의 파라미터를 이용해 초기화 합니다.

하지만 π_rl은 self-play 를 통해 계속해서 강화됩니다

 

알파고에서 보상함수는 win = 1, lose = -1 , 그 외의 중간 보상은 전혀 없습니다.

또 policy gradient 방법론을 사용하였고, 그중에서도 리턴만 있으면 학습할 수 있는 알고리즘인 REINFORCE를 사용하였습니다.

GPU 50대 1일간 학습, 128경기 데이터 이용해 1개의 미니 배치 구성

 

 

밸류 네트워크 V_rl

_{아웃풋이 19 X 19 가 아니라 1개의 값입니다. 즉 각 상태의 밸류를 리턴하는 네트워크 입니다.}

주어진 상태 s부터 시작해서 π_rl 을 이용하여 플레이 했을때 이길지 여부를 예측하는 함수입니다.

그러나 중간보상이 없음으로 결국 승자를 예측하는 함수가 됩니다.

총 3천만 개의 각기 다른 게임에서 나온 상태를 가지고 데이터 셋을 만들었고, 해당 데이터 셋을 이용해

GPU 50개로 총 1주일간 학습을 하였습니다. 이렇게 가치함수 Vrl 이 학습이 되면 해당 경기의 승자가 누가 될지 가늠할수 있습니다.

 

MCTS

냅다 둬봐서 이길지 질지 예측하는 플래닝 알고리즘입니다

πrl 조차 프로 바둑기사에 비하면 조악한 수준입니다.

그래서 어떤 상황이 주어졌을때 그 상황에 특화된 최적 액션을 무수히 많은 시뮬레이션을 통해 찾습니다

실제로 알파고를 포함한 대부분의 바둑 AI들은 모두 MCTS를 사용하였다고해도 과언이 아닙니다.

MCTS를 사용하기 위한 2가지 조건

1. MDP를 알것 : 바둑의 규칙을 알고 있기 때문에 모델을 아는것과 같습니다.

                      요컨대 액션을 하고 나면 다음 상태가 어떻게 될 지와 얼만큼의 보상을 받을지를 액션을 해보기도

                      전에 정확하게 알고 있는 것입니다.

 

2. 게임 중간마다 시간적 틈 존재 : 바둑은 한판안에 1시간이라는 제한시간이 존재하고 제한시간을 다 사용해도

                                            초읽기가 존재하여 1분이 주어집니다. 이는 스타크래프트와 달라 MCTS가 바둑에서 유리합니다.

 

알파고에서의 MCTS 는 1.선택,

                              2. 확장,

                              3. 가치 평가,

                              4. 백 프로파게이션

이렇게 4단계로 구성되어 있습니다.

1~4 단계 까지 한바퀴를 돌면 트리에 새로운 노드 하나가 매달립니다. 여기서 노드는 바둑판의 한 상태에 대응됩니다.

해당 노드를 평가하고 거쳐온 경로의 액션의 가치를 업데이트 합니다.

 

1.  선택

선택단계는 루프 노드에서 리프 노드 까지 가는 과정입니다.

각 순간의 선택은 기존에 평가해놓은 액션의 밸류를 높은 액션을 선택하도록 기준을 세워야 합니다.

시뮬레이션을 진행하며 경험이 쌓일수록, Q(s,a) 의 영향력은 커지고, u(s,a)의 영향력은 줄어듭니다.

2. 확장

방금 도달한 리프 노드를 실제로 트리에 매달아 주는 과정입니다. 엣지들의 다양한 정보를 초기화 합니다.

3. 가치 평가

리프노드가 정식 노드가 되었을때, 이노드의 가치를 평가해주는것,

리프 노드 sL 부터 시작하여 빠르게 시뮬레이션 실행(πroll), 지도학습(πsl)

4. 백 프로파게이션

Q(s,a) 의 값은 해당 엣지를 지나서 도달한 리프 노드 밸류의 평균일때 그 값을 계산해주는 과정

이미 계산된 평균값이 있고, 새롭게 도달한 리프 노드의 밸류를 반영하기 위해 평균값 Q(s,a)를 업데이트 해주는 과정

 

알파고는 Q(s,a) 대신 방문 횟수가 가장 높은 액션 하나를 N(s,a) 로 경정론적으로 선택하였습니다.

알파고 제로

학습때도 MCTS 를 사용하자

각 스텝마다 MCTS를 돌려서 정답 확률 분포를 얻고, 그 분포와 현재 정책 네트워크의 아웃풋 사이 차이를 줄이는 방향으로

정책 네트워크를 업데이트 합니다.

πsl 대신 P 사용 ,Vrl 대신 v 사용, πroll 사용안함