알파고의 원리와 그 버전들

알파고(AlphaGo)로 통칭되지만 실제 바둑 ai는 여러 버전이 있다.
이세돌을 이긴 알파고 lee, 타이젬 등 온라인 사이트에서 60연승 후 마지막 공식 대국으로 커제와 겨뤘던 알파고 master, 이 모든 걸 뛰어넘은 알파고 zero까지 있다. 각 버전이 등장하는 순간을 바둑을 좋아하는 개발자로서 실시간으로 목격하는 즐거움이 매우 컸다. 머신러닝은 잘 몰라서 알파고 실력에만 감탄하며 봤지만 이젠 익숙한 단어들도 조금씩 들려서 정리해봤다.

 

바둑 ai를 만든다고 생각해보자. 머신러닝 지식 없이 컴퓨터로 봇을 만든다면 모든 경우를 탐색해서 가장 좋은 한 수를 두겠지만 바둑도 그렇고 현실 세계에서는 모든 경우의 수를 다 해볼 수 없다. 다 할 수만 있다면 minimax 알고리즘으로 서로 최선을 다할 때 누가 이길지를 돌 가리기 시점에 알 수 있을 거고, 이건 마치 홀짝 게임과 같아진다. 그래서 많은 바둑 ai들이 MCTS로 모든 경우를 보지 않고 좋은 행동을 취할 수 있도록 탐색한다.

 

MCTS (Monte Carlo Tree Search)

root부터 시작해서 policy를 따르며 내려와 leaf node를 선택(Selection) 한다. 그 node에서 갈 수 있는 다음 node를 Expansion 해서 확장 후 Simulation 으로 최종 결과를 얻고 다시 뒤로 Backpropagation 하며 상태 값들을 업데이트한다.

 

대략 pseudo code를 적어보면 다음과 같다.

 def mcts(root): 
      
    while runnable(resource): # 컴퓨팅 능력이 가능한 순간까지 반복
        leaf = search(root) # 정책에 맞게 자식 탐색
        result = simulation(leaf) # 종료될때까지 다음 상태를 탐색
        backpropagate(leaf, result) # 결과를 바탕으로 트리 업데이트
          
    return best_child(root) # 검색 결과 가장 좋은 자식으로 이동

 

 

알파고

MCTS를 무한히 반복하면 minimax 결과에 수렴하는 만큼 모든 경우를 탐색하지 않고 적은 비용으로 좋은 효과를 기대할 수 있다. 하지만 이렇게 만든 ai는 인간을 못 이긴다. 그래서 딥마인드는 MCTS에 딥러닝을 더했다. 딥러닝을 바둑에 어떻게 적용시켰는지는 다음에 더 자세히 정리해 볼 예정이고, 여기서는 어떤 딥러닝을 더했는지만 정리해본다.

 

효율적인 탐색을 위해 크게 아래 두 가지 방향에 적용했다.

 

넓이를 줄이자 (Expansion)

현재 상태 s에서 행동 a를 하는 확률 $P(a|s)$를 아래 세 가지를 조합해서 구한다.

 

 

1) SL policy network (Supervised Learning)

인간 고수의 기보를 CNN(Convolutional Neural Network)으로 학습시킨다.

• 입력층: 바둑판 19x19에 각 위치별로 11가지 특징을 나타내는 48차원을 더한 19x19x48
• 1층: 5x5 필터 192개와 ReLU 함수
• 2~12층: 3x3 필터 192개와 ReLU함수
• 13층: 1x1 필터와 위치 정보를 뽑아내고 softmax 함수
• 출력층: 19x19에서 다음 수의 확률

위에는 대략 썼지만 더 자세히는 CNN으로 학습시키는 각 레이어 과정에서 zero padding을 추가한다. 바둑에서 3x3처럼 좁은 지역의 특징을 포착하는 CNN이 갑자기 왜 나왔나 싶지만, 이를 반복하면 넓은 지역의 특징도 포착할 수 있다. 이런 특징이 인간이 바둑을 두며 형세를 판단하는 것과 유사하다고 볼 수 있어서 성능이 나오는 것 같다.

 

2) RL policy network (Reinforcement Learning)

1)에서 구한 모델들로 self play 하며 강화 학습한다. 승리하면 +1, 패배하면 -1의 reward를 준다. 보통 강화 학습처럼 현재 상태에서 reward를 구하는 함수가 아닌 $P(a|s)$를 구해야 하기 때문에 policy gradient를 사용한다. 이렇게 self play로 더 학습을 시키면 SL policy network과 대결했을 때 80%의 승률을 기록한다고 한다.

 

 

3) Rollout policy

기보도 좋고 self play도 좋지만 바둑에는 꽤 높은 확률로 좋은 수로 특정 지을 수 있는 naive 한 패턴이 꽤 많다. 단수면 피하거나, 상대가 방금 둔 수의 바로 옆에 있는 8방향 수를 두거나 하는 일차적인 수부터, 3x3 남짓의 주변의 배석 상태를 수작업으로 모아둔 패턴과 비교하는 방법 등으로 빠른 시간에 괜찮은 수를 예측을 할 수 있다.

 

깊이를 줄이자 (Simulation)

끝까지 탐색을 하지 않고 value network 로 승률을 계산한다. value network는 CNN을 사용한 위 policy network와 비슷하지만 마지막 층이 다음 수의 확률이 아닌 예측 승률 값이다. 따라서 마지막 아웃풋에 추가적으로 tanh 속성의 함수를 통과시킨다.

 

 

이렇게 위에서 구한 policy network와 value network를 잘 몬테카를로 탐색에 잘 조합하여 다음 수를 예측한다.

 

알파고 제로

이름부터 제로로 그 특징을 보여주고 있지만 알파고 제로(AlphaGo Zero)는 알파고와 비교해서 다음과 같은 차이점이 있다.

1. rollout policy는 제거하고 policy network와 value network를 하나로 통일 (Dual network)
2. SL policy network에 사용했던 인간 기보 없이 강화 학습만 사용
3. 바둑 판의 여러 특징(48 채널)을 없애고 흑/백의 위치와 기본 정보(17 채널)만 사용
4. 기타 고도화로 학습에 필요한 하드웨어 비용 절감

 

알파 제로

알파고 이후 인간 기보 없이 강화 학습만 사용한 알파고 제로 다음으로 고(Go) 글자마저 없애 다른 게임에도 범용적으로 적용할 수 있는 알파 제로(AlphaZero)가 등장했다. 범용적인 적용을 위해 바둑에만 해당되는 지식을 제거한 채 학습시킨다. 그 예로, reward 값을 승/패로 국한하지 않는다. 또 바둑은 대국자의 진영이 존재하지 않아서 판을 8방향 전환해도 무방하기 때문에 이를 학습에 이용했는데 이 방법도 제거했다.

 

이렇게 다른 게임에 대해서 학습을 시켜보니 바둑뿐만 아니라 체스, 쇼기도 압도적인 성능을 보여줬다. 뿐만 아니라 알파고 제로보다도 강했다. 물론 여기에는 단순히 바둑 규칙을 제거한 것 외에 추가적인 튜닝이 있기 때문이지만 어쨌든 일반화 한 모델로 이긴다는 게 놀랍다.

각각의 버전에는 도메인 지식을 제거한 간결한 알고리즘과 효율적으로 학습시키기 위한 머신러닝 기술이 많이 들어가 있다. 깊이 이해할 자신은 없고 왜, 어떻게 발전해 나가는지는 공부하는 재미가 있을 것 같다.