Mastering the Game of Go without Human Knowledge (AlphaGo Zero)

ABSTRACT
Alphago Zero는 인간의 데이터를 빼고 강화 학습만을 기반으로 하여 압도적인 성능을 이끌어내어 이세돌과 대국하였던 Alphago Lee를 상대로 100 : 0 으로 승리하였다.

Alphago Lee simple review

b-1. Policy network -> 선택의 너비를 줄여주는 network : 확률분포를 리턴한다.
b-2. Value network -> 선택의 깊이를 줄여주는 network : 상수를 리턴한다.

a-1. Rollout policy -> 빠른 시뮬레이션을 위한 작은 네트워크(정확도는 24.2%, 한 번 선택하는데 2μs)
a-2. SL policy network -> 인간의 기보(3천만 수)를 19 * 19 * 48의 Input으로 CNN(Layer : 13) 학습된 네트워크(정확도는 57%, 한 번 선택하는데 3ms)
a-3. RL policy network -> REINFORCE 알고리즘을 사용한 SL policy와 동일한 형태의 네트워크, reward는 게임이 끝난 시점에서 주워지며, 이기면 +1, 지면 -1
a-4. Value network -> RL policy를 따랐을 때에 누가 이길지 예측하는 네트워크

MCTS(Monte Carlo Tree Search)

선택하다가 선택지가 Leaf까지 오면 SL policy로 하나를 더 두고
Value network와 Rollout policy를 반반 섞어서 가치를 평가하고 저장한다(Q function).

Alphago Zero

핵심 아이디어 : MCTS를 Policy Iteration의 operator로 학습에 사용

  1. 혼자서 번갈아가며 게임을 진행
  2. 매 state 마다 MCTS를 통해 π를 계산하고, 샘플링 하여 action을 정한다.
  3. 게임이 끝나면 z값을 정한다. 이기면 1, 지면 -1
  4. 각 state 마다 (s, π, z)가 남는다.
  • 1000번의 update 마다 checkpoint 저장
  • 새로 생긴 checkpoint는 기존 network와 붙어서 55% 이상의 승률을 보이면 기존의 network를 대체하여 data 생성 network가 된다.
  • 한번의 action을 선택하기 위해 1600번의 MCTS를 수행한다. (총 0.4초 소요됨)
  • 한 action에 생성 된 subtree는 다음 action에 재사용된다.
  • p는 π 와 같아지도록, v는 z와 같아지도록 θ를 update
  • 데이터는 과거 게임에서 쌓은 (s, π, z) 중 random sampling 하여 사용
  • input : 19 * 19 * 17
    19 * 19 : 바둑판, 17 : 현재 시점에서 최근 8수의 위치 정보(흑 + 백 해서 16) + 현재 플레이어가 흑 or 백
  • input은 한개의 Conv block과 39개의 Residual Block을 통과
  • 최종적으로 Value와 Policy는 각각 1차원 tanh와 362(19 * 19 +1(바둑 규칙 중 안두는 것이 있다))차원 softmax를 return 함.
  • Value network와 Rollout policy를 반반 섞어서 가치를 평가하고 저장하던 것이 Value network로 변경 (Q function)
  • Leaf Node에 도달하면 NN을 evaluate하여 prior와 Q를 계산
  • 1~3을 여러번 반복하여 search가 종료되면, 최종 확률 분포 π가 리턴

초기 30수는 T를 1로 주어 방문횟수와 비례하도록 선택하게 해줘 여러 곳을 방문해보라고 하고, 그 이후에는 T를 0으로 설정하여 방문횟수가 높은 곳을 선택하게 한다.

위 그래프에서 Alphago Zero는 인공지능이 사람이 하지 않는 move를 보이면서 사람보다 훨씬 잘할 수 있다는 것을 보여준다.

REFERENCE MATERIALS
- paper path
  http://discovery.ucl.ac.uk/10045895/1/agz_unformatted_nature.pdf
- 참고 자료
  https://www.youtube.com/watch?v=CgOGKChwWrw&list=PLpRS2w0xWHTfnWmr95LtIu4v4HbVxqTlM&index=5&t=1431s 

Leave a Reply

Your email address will not be published. Required fields are marked *