BETTER COMPUTER GO PLAYER WITH NEURAL NETWORK AND LONG-TERM PREDICTION 1부

다음은 http://arxiv.org/pdf/1511.06410v2.pdf 이 논문을 2부에 나눠 번역한 것이다.

Long-Term Prediction과 인공 신경망을 적용시킨 더 발전된 컴퓨터 바둑기사

(BETTER COMPUTER GO PLAYER WITH NEURAL NETWORK AND LONG-TERM PREDICTION)

저자 : Yuandon Tian, Yan Zhu

초록

오래된 고전게임인 바둑에서 프로기사와 대결하는 것이 AI의 장기목표였습니다. 바둑의 분기계수(한마디로 각 위치에서의 다음수의 개수? 혹은 전체 자식노드의 최대개수? 를 말하는듯.. DeepMind에서 발표한 영상에서는 이게 200개가 된다고 함)는 심지어 독보적인 하드웨어에서 조차 기존의 전통적인 탐색기술들을 무력화시킵니다. 바둑의 평가함수는 한돌이 바뀔때 급격하게 바뀔수 있습니다. 최근의 연구[Maddison et al. (2015); Clark & Storkey (2015)]들은 기계바둑기사들에게 탐색기술이 반드시 필요한것이 아니라는걸 보여줍니다. Pachi [Baudis & Gailly (2012)] 같은 Monte Carlo Tree Search(MCTS)기반의 오픈소스 바둑 엔진뿐만 아니라, 다음 움직임을 예측하는 Deep Convolutional Neural Network에 기반한 하나의 순수 패턴일치 접근은 만약 search budget이 제한되었을때 사용할 수 있습니다. 우리는 이 생각을 장기예측들을 위해 고안된 DCNN에 기반한 우리의 darkforest라는 봇에게 확장시켰습니다. Darkforest는 MCTS 기반의 접근에 비해 패턴 일치 접근에 대한 승률을 향상시켰습니다. 인간상대로 최신 버전인 darkfores2는 순위에 든 기계로써 KGS 바둑 서버에 안정적인 3d level을 달성 했습니다. 이는 다른 기계 기사들이 Clark & Storkey (2015)에서 발표한 대국에 기초한 DCNN에 대한 4K~5K 평가순위에 비하면 상당한 향상입니다. darkforees2에 MCT를 추가하는 것은 drakfmcts3라는 더 강력한 기사를 만들었습니다. 5000개의 rollout(자료를 말하는듯...)으로 이것은 10000개의 rollout을 학습한 Pachi를 250경기 모두 이겼다. 75k의 rollout들을 학습한 drakfmcts3는 예술의 경지인 Go AIs (e.g., Zen, DolBaram, CrazyStone)와 동등한 안정적인 5d 레벨을 KGS server에서 획득하였습니다. 110k개의 rollouts를 학습한 이것은 1월달에 있던 KGS Go Tournament에서 3위에 입상하였습니다.

1. 서론

오랫동안, 바둑 컴퓨터는 인공지능에서 거대한 도전으로 받아들여져 왔습니다. Fig.1 은 바둑의 단순한 그림을 보여 줍니다. 두명의 플레이어, 흑과 백, 는 1919의 바둑판에 번갈아 가며 교차점에 돌을 놓습니다. 흑돌은 빈 바둑판에 먼저 둡니다. 4개의 같은 돌로 연결된 부분을 대마(group)이라고 부릅니다. 한 집의 공배(liberty,liberties)은 이웃하는 빈 교차점들의 갯수입니다 (Fig. 1(b)). 한 대마는 공배가 없을때 잡아먹힙니다. 이 게임의 목표는 상대보다 더 많은 영역을 장악하는 것입니다. (바둑용어에 관한 사이트, http://www.aistudy.com/game/baduk_english.htm) (Fig. 1(c)). Fig. 1(d))는 kyu 레벨(입문자에서 괜찮은 아마추어 , 30k~ 1k) 부터 dan 레벨 (상급아마추어, 1d~7d) 그리고 professional 레벨(프로, 1p~9p)의 바둑의 평가시스템을 보여줍니다 [Silver (2009)].

바둑은 이것의 높은 가지계수때문에 어렵습니다. (전형적으로 1919 바둑판에 대략 100개) 그리고 작은 변화에 민감한 미묘한 바둑판 상황 (1개의 돌을 더하느냐 빼느냐에 따라 돌의 큰 대마의 사활(살거나 죽거나)이 바뀔 수 있고 따라서 마지막 스코어가 완전히 변합니다.) 흑과 백의 하나의 조합(여러 경우의 대국중 하나의 대국)을 찾을 유일한 해결책이 최신 하드웨어로도 얻을 수 없는 상당히 많은 양의 자월들이 요구되는 방대한 탐색뿐 이라는 것을 암시합니다.

운이 좋게도, 바둑 컴퓨터에서 최근의 연구들 [Maddison et al. (2015); Clark & Storkey (2015)] 은 바둑판 상황이 Deep Convolutional Neural Network(DCNN)으로 해독될수 있다는 것을 시사했습니다. 최근 연구들은 그 시기(다음에 두는 턴)에 55.2% 정확도로 한 기사가 다음에 둘 수를 예측할 수 있다고 합니다. 그러나, 이 정확도가 강력한 바둑 AI로 이끌지는 미지수 입니다. DCNN이 지역 패턴들의 연관성을 보는 것으로 정확하게 가장 일반적인 대국을 예측하지만 한수 혹은 두수의 움직임을 예측하는데 여전히 실패하여 게임을 진다는 것이 가능합니다. 사실상, 한 DCNN기반의 컴퓨터 기사는 상업적인 부분을 제외하더라도, Monte-Carlo Tree Search(MCTS)기반의 전통적 오픈소스 기반 엔진과 비교해 여전히 뒤쳐저 있습니다[Browne et al. (2012); Kocsis & Szepesvari (2006)].

이 논문에서, 적절히 훈련만 된다면, 우리는 DCNN기반의 수 예측이 GO AI에 힘을 줄것이라는걸 보일 것입니다. 특히 저희는 조심스럽게 훈련 과정을 설계하고 변화신호를 풍부하게 하기위해 바로 다음 수를 예측하기 보다는 다음 k 개의 수(다음수의 시나리오를 여러개 만들었다는건가? 아님 다음수에 그 다음수 ... k번째 다음수까지 예측한다는 건가..)를 예측하는것으로 결정했습니다. 우리의 예측이 단지 수 예측의 정확도에 2%의 상승만을 얻음에도 불구하고, 100k rollouts같이 무거운 탐색 시나리오들에서 오픈소스 엔진 (e.g., Pachi and Fuego)들과의 대결에서 현 예술의 경지에 있는 DCNN 기반 기사[Maddison et al. (2015)]보다 승률이 6배나 높게 나왔습니다.(Pachi: 11.0% vs 72.6%, Fuego: 12.5% vs 89.7%). 덧붙여, 우리의 덜 탐색적인 로봇 darkfores2 는 KGS Go 서버에서 랭킹 게임을 했고 안정적인 3d 레벨을 달성했습니다. 이는 MCTS 기반 GO 엔진들과 한 게임들로부터 측정된 4~5 kyu의 레벨을 가진 Clark & Storkey (2015)가 제안한 AI 기반 인공신경망 보다 훨씬더 더 나은 역할입니다. 

우리의 봇은 또한 지역 전략들에서 DCNN 기반의 방법들의 일반적 약점을 공유합니다. DCNN과 MCTS를 묶은 우리의 하이브리드 봇인 darkfmcts3 는 이러한 문제들을 다룹니다. 5000개의 rollouts를 학습한 이것은 10k rollout을 학습한 Pachi를 250경기 모두 이겼습니다 (승률 100%). 또한 75k 개의 rollouts를 학습한 darkfmcts3는 안정적인 5d 수준을 KGS Go server에서 달성했고 예술의 경지인 Go AI들s (e.g., Zen, DolBaram, CrazyStone)과 어깨를 나란히 했습니다. 110k의 rollouts를 학습한 이것은 1월에 열린 KGS Go Tournament에서 3위에 입상했습니다.

2. 방법

바둑의 다음수를 예측하기 위해 패턴 부합법과 함수 근사법으로써 신경망을 쓰는 것은 오래된 생각입니다.  [Sutskever & Nair (2008); Richards et al. (1998); Schraudolph et al. (1994); Enzenberger (1996)]. 최근의 약진은 Deep Convolutional Neural Network(DCNN)을 수 예측에 사용하고 이전 게임들로 부터 추출된 간단한 패턴들 또는 수작업으로 고안된 피쳐들에 기반한 선형함수 approximators들 또는 shallow networks을 뛰어 넘는 상당한 성능향상을 보입니다. [Silver (2009)].

이 논문에서, 우리는 현재의 바둑판 형세를 Input으로써 가정하고, 다음 k개의 움직임들을 예측하는 DCNN을 훈련시켰습니다. 우리는 1919 바둑판을  다수의 channel이 있는 1919 이미지로써 다루겠습니다. 각각의 channel은 방대한 정보의 다른 측면을 암호화시킵니다 ,e.g., liberties (Fig. 1(b)). 이전 연구들과 비교해, 우리는 하나의 더 압축된 피쳐셋을 사용하고 long-term한 수를 예측합니다. (아까 1~k 번째 다음수까지 예측한다는 말이 맞는듯, 길게 본다니까) 그리고 오픈소스 엔진들과 대국한 승률의 측면에서 상당한 성능향상으로 이어진 것으로 보입니다.

Table1은 현재 바둑판 상황으로부터 뽑아낸 feature들을 보여줍니다. 각각의 피쳐는 과거의 정보와 위치 mask를 제외한 0 아니면 1인 실수로 된 하나의 이진  1919 맵입니다. 과거는 as exp(−t ∗ 0.1)로 입력되었습니다. 여기서 t는 얼마나 오랫동안 그 돌이 놓여져 있었냐는 의미입니다. The exponential temporal decay는 최근의 전투에 그 네트워크가 집중할 수 있게 한다는 의미입니다. 위치 표시는 로 정의 됩니다. 는 바둑반의 중심까지의 L2거리의 제곱입니다. 각 교차점의 상대적 위치를 입력하는데 사용됩니다.

Maddison et al. (2015)에서의 피쳐와 우리가 도출한 피쳐사이에는 2가지 차이점이 있습니다. 첫째로, 우리는 거의 모든 피쳐들에 relative coding(우리/적)을 사용합니다. 이와 대조적으로, Maddison et al의 피쳐들은 대체로 player-agnostic(어느 플레이어가 하든 상관없다는말) 합니다. 둘째로, 우리의 피쳐셋은 더 간단하고 압축되었습니다 (25 vs. 36 input planes). 특히 우리의 피쳐셋은 앞선한수의(앞으로 벌어질) 상황으로부터 자유롭습니다. 대조적으로 Maddison et al. (2015)은 수를 둔후의 공배(liberties) 혹은 다음 수에서의 포획(바둑에서 그냥 잡아먹는다 하나?)등 이같은 피쳐를 사용합니다. 저희는 Maddison et al. (2015)에서 9개의 층(plane)들에서 rank(?)를 입력하는 방법과 유사합니다. 즉 모든 kyu 플레이어들은 모든 9개의 층(plane)이 0이 되게 합니다.(binary map 이므로) 1d 플레이어들은 그들의 첫 plane을 모두 1로 두고, 2d 플레이어들은 그들의 2번째 plane을 모두 1로 두고, 이런식으로 9d 플레이어들 과 프로기사들은 모든(1~9)plane들을 1로 채웁니다.

2.2 NETWORK ARCHITECTURE

Fig. 3 은 저희의 최고의 모델에 대한 신경망 구조를 보여줍니다. 저희는 12층(d=12)의 full convolutional network를 사용했습니다. 각각의 콘볼루션 층은 ReLU 비선형성을 따릅니다 (활성함수가 ReLU라는 말). 처음 층을 제외하고, 모든 층들은 같은 width(w=384)를 사용합니다. 가중치공유는 하지 않습니다. 저희는 pooing이 성능에 부정적인 영향을 미치기 때문에, pooling을 사용하지 않습니다. 흑과 백돌의 움직임을 예측하기 위해 2개의 softmax 출력들을 사용하는 대신 [Maddison et al. (2015)],저희는 단지 다음 수를 예측하기 위해 파라미터들의 수를 줄여, 한개의 softmax 층만 사용을 했습니다.

2.3 LONG TERM PLANNING

바로 다음 수만(한수앞만) 예측하는 것은 더 낮은 층들에 의해 입수된 정보를 제한 합니다.(그냥 내가 잘 모르지만 왠지 마르코프-체인의 한계와 비슷한거 같다.) 대신에 , 저희는 다음 k수들을 현재 바둑판의 상황으로부터 예측합니다(저희와 적을 번갈아 가며). 각 움직임은 분리된 softmax 출력입니다. 그 유도(motivation)은 2중입니다.

 첫째로, 저희는 저희의 신경망이 바로 다음수보다는 하나의 전략적인 계획에 초점을 맞추기를 원합니다. 둘째로 다중 softmax 출력으로, 저희는 신경망을 훈련 시키기 위해 더 많은 통제를 가질 것을 기대합니다. Table2에서는 각각의 convolutional layer에서 1 step과 3 step 사이의 예측들 사이의 평균 기울기 L2 기준의 비율(the ratio of average gradient L2 norm)(첫 9 epoch에 대해서, 첫 1000 mini-batch들을 제거함)을 계산합니다. 예상했듯이, 상위 층(softmax에 가까운 층들)의 기울기 크기는 3-step prediction에서 보다 높다. 그러나 , 짐작컨데 훈련에 오직 가장 중요한 기울기만 남기는 것으로 3-step prediction에서 낮은 기울기값들을 제거하는것을 보여주어, 하위층들의 기울기의 크기들은 대략 같다. 경험적으로, 3 steps로 훈련된 DCNN은 1 step으로 훈련한 DCNN보다 높은 승률을 준다.

 

2.4 TRAINING

훈련시에는, 저희는 16CPU 쓰레드를 minibatch를 준비하기 위해 사용했습니다. 각각의 CPU tread마다 데이터 셋으로 부터 300개의 랜덤선택되어 simulating을 합니다. 각 쓰레드에 대한 각 minibatch에서 임의적으로 300개 게임중에서 한게임을 선택하고, 대국기록에 따라 한단계 시뮬레이션을 하고, 피쳐들과 다음 k개의 수들을 input/output 쌍으로써 batch에서 뽑아 냅니다. 만약 그 게임이 끝나면 (남은 k개의 수들(예측)보다 적은 수에서 끝나면), 저희는 임의적으로 훈련셋으로부터 이 게임을 대체할 것을 고른후 속개합니다. 이 batch 크기는 256입니다. 저희는 90도 간격 로테이션과 수평/수직 뒤집기로 data augmentation을 사용합니다.(이 방법으로 새로운 데이터 만든다는 말). data augmentation(데이터 생성한다는 말인가?, 직역하면 데이터 증가인데...)은 8가지 다른 상황들을 만들어 낼 수 있습니다.

훈련전에, 저희는 임의적으로 게임들을 다른 단계들로 초기화시켰습니다. 이것은 각각의 batch가 게임들의 다른 단계에 부합하는 상황들을 포함한다는걸 확신시켜줍니다. 이것 없이는 , 신경망은 빠르게 과적합될것이고, 좋지않은 지역최소점문제에 갇이게 될것입니다.

저희의 훈련방식 때문에, 훈련셋이 철저하게 한번에 처리가 되는지는 이것이 명확하지 않습니다. 그러므로, 저희는 10,000개의 mini-batch들로써 한 epoch를 정의합니다. 비동기식 SGD(Stochastic Gradient Descent)를 사용한 Maddison et al. (2015)과는 다르게, 저희는 전체 신경망을 훈련하기 위해 Vanilla SGD를 한개의 기계에서4개의 NVida K40m GPU를 사용했다. (몇몇 모델들에 대해서 저희는 255개의 batch 크기로 3개의 GPU를 사용합니다.) 각각의 epoch는 5~6시간을 지속합니다. 초기학습률은 0.05로 정하고 수렴이 안될때 5로 나눕니다. 전형적으로, 이 모델은 한 epoch안에서 수렴하기 시작하고 50~60 epoch후 (약 2주)에는 좋은 성능을 보입니다.

가장 단순한 DCNN 모델을 제외하고, 저희는 또한 최근 이미지분류에서 예술의 경지의 성능을 보여준 ResNet [He et al. (2015)]으로 훈련을 시도했습니다. 저희는 또한 현재 바둑판의 형세를 고려한 끝형국의 모양을 예측하는것과 같은 부가적인 목표들을 사용하려 시도했습니다. 둘다 더 빨리 수렴을 했습니다. Recurrent Neural Network또한 시도를 해보았으나 성능이 더 나빴습니다.

2.5 MONTE CARLO TREE SEARCH

위 실험들로 부터, 저희는 명백히 탐색의 부족 때문에 DCNN이 전략적으로 약하다는것을 보여주었습니다. 탐색은 현 바둑판의 상황을 조건으로 solution space를 탐색하고 그 게임에 대해 non-parametric local model을 설립하는 하나의 방법입니다. 그 local model은 방대한 훈련 데이터로부터 훈련된 global model보다 더 유연하고 현 대국의 상황에 더 잘 적합되었습니다. (local model과 global model의 차이점이 뭐지?, 전체데이터를 학습하냐 일부데이터만 학습하냐의 차이인가?) 바둑 컴퓨터에서 이 예술의 경지의 접근법이 Monte-Carlo Tree Search(MCTS)입니다. Fig. 4 는 이것의 기본적인 요소들을 보여줍니다.

DCNN과 MCTS를 결합하는 것은 중대한 공학적 노력들이 필요하다. 왜냐하면 MCTS의 각 rollout은 DCNN 평가보다 훨씬 더 빠르기 때문이다. 그러므로, 이 두 가지는 빈번한 소통과 함께,병렬로 실행되어야만 합니다. 전형적으로 DCNN이 4개의 GPU들로 128크기의 한 batch의 바둑판 평가를 주는데 0.2초가 걸리는 반면, 저희의 기본적인 MCT의 실행은 (Intel Xeon CPU E5-2680 v2 at 2.80GHz가 장착된 한 기계에 16개의 쓰레드에게) 초당 16k rollout을 주었습니다.

이 문제를 다루는데에는 2가지 방법이 있습니다. Maddison et al. (2015)에서 사용된 비동기식 실행에서, MCTS는 새롭게 확장된 노드를 DCNN으로 보냈습니다. 그러나 DCNN평가에 의해 막혔습니다. MCTS는 DCNN evaluation이 마칠때까지 이것 자신만의 tree policy를 사용할 것입니다. 이것은 높은 rollout 률을 주나, DCNN 평가가 효과를 갖는데에는 시간차가 있고 얼마나 많은 바둑판 상황들이 주어진 MCTS rollouts의 숫자에 대해 평가 될지는 명확하지는 않습니다. 비동기식 실행에서 MCTS는 DCNN이 잎노드의 바둑판 상황을 평가할때까지 기다릴 것입니다. 그 다음에 잎을 확장할 것입니다. 기본정책은 DCNN 평가 전/후에 실행될 수 있습니다. 이것은 훨씬더 느리지만 각 노드가 DCNN에 의해 나온 제안된 수들에 따라서 각 노드가 확장되는걸 보장합니다.

저희의 실험들에서, 저희는 동기화된 케이스를 평가합니다. 이 케이스는 1000개의 rollouts들의 Raw DCNN 플레이어와 대결해 84.8%의 승률을 성취했습니다. 저희의 실험은 100k rollouts으로 86.7%를 성취한 Maddison et al. (2015)에서의 비동기화 버전과 직접적으로는 비교할 수 없다는것을 주의하기 바랍니다. 

1부 끝

해석이 틀리거나 내용이 틀린것은 댓글로 남겨주시면 감사하겠습니다~