The Journal of The Institute of Internet, Broadcasting and Communication (IIBC) Vol. 17, No. 5, pp.119-124, Oct. 31, 2017. pissn 2289-0238, eissn 2289-0246 https://doi.org/10.7236/jiibc.2017.17.5.119 JIIBC 2017-5-16 딥퍼플 : 딥러닝을이용한체스엔진 DeepPurple : Chess Engine using Deep Learning 김성환 *, 김영웅 ** Sung-Hwan Yun *, Young-Ung Kim ** 요약 1997년 IBM의딥블루가세계체스챔피언인카스파로프를이기고, 최근구글의알파고가중국의커제에게완승을거두면서딥러닝에대한관심이급증하였다. 본논문은딥러닝에기반을둔인고지능체스엔진인딥퍼플 (DeepPurple) 개발에대해기술한다. 딥퍼플체스엔진은크게몬테카를로트리탐색과컨볼루션신경망으로구현된정책망및가치망으로구성되어있다. 딥러닝을통해구축된정책망을통해다음수를예측하고, 가치망을통해주어진상황에서의판세를계산한후, 몬테카를로트리탐색을통해가장유리한수를선택하는것이기본원리이다. 학습결과, 정책망의경우정확도 43%, 손실함수비용 1,9로나타났으며, 가치망의경우정확도 50%, 손실함수비용 1점대에서진동하는것으로나타났다. Abstract In 1997, IBM's DeepBlue won the world chess championship, Garry Kasparov, and recently, Google's AlphaGo won all three games against Ke Jie, who was ranked 1st among all human Baduk players worldwide, interest in deep running has increased rapidly. DeepPurple, proposed in this paper, is a AI chess engine based on deep learning. DeepPurple Chess Engine consists largely of Monte Carlo Tree Search and policy network and value network, which are implemented by convolution neural networks. Through the policy network, the next move is predicted and the given situation is calculated through the value network. To select the most beneficial next move Monte Carlo Tree Search is used. The results show that the accuracy and the loss function cost of the policy network is 43% and 1.9. In the case of the value network, the accuracy is 50% and the loss function cost is 1, respectively. Key Words : Deep Learning, Chess Engine, Policy Network, Value Network, Monte Carlo Tree Search Ⅰ. 서론 1997년, IBM에서체스의모든경우의수를컴퓨터로계산한체스프로그램인딥블루가러시아체스챔피언이카스파로프에게승리했다. 2016년구글딥마인드가딥러닝을이용한바둑인공지능프로그램알파고로세계바둑챔피언인이세돌 9단과중국바둑기사커제와의대국 * 준회원, 한성대학교컴퓨터공학과 ** 정회원, 한성대학교컴퓨터공학부 ( 교신저자 ) 접수일자 : 2017 년 8 월 16 일, 수정완료 : 2017 년 9 월 15 일게재확정일자 : 2017 년 10 월 13 일 을승리함으써딥러닝에대한관심을집중시켰다. 본논문은구글딥마인드의알파고의원리를바탕으로딥러닝을이용한인공지능체스엔진인딥퍼플에대해기술한다. 딥퍼플체스엔진은크게몬테카를로트리탐색과컨볼루션신경망 Convolutional Neural Network: CNN) [1] 구조를갖는정책망, 가치망으로구성되어있다. 정책망 (Policy Network) 은주어진체스판에서체스판 Received: 16 August, 2017 / Revised: 15 September, 2017 / Accepted: 13 October, 2017 ** Corresponding Author: yukim@hansung.ac.kr Dept. of Computer Engineering, Hansung University, Korea - 119 -
DeepPurple : Chess Engine using Deep Learning 에배치된말들의상태가압력으로주어지면, 가능한수들과함께그수를선택할확률을계산하여가장확률이높은수를예측하는모델이다. 가치망 (Value Network) 은체스판의상황이입력으로주어지면결과값으로백승과흑승그리고무승부가될확률을반환하여누가얼마나유리한상황인지를예측하는모델이다. 가치망은정책망과달리승과패에대한결과를학습에반영함으로써정책망으로부터예측받은수가실제로유리한수인지를판단하는기준이된다. 정책망과가치망을완성하면, 이두개의모델만으로도어느정도의패턴을파악한결과를알수있지만, 딥퍼플의경우충분한성능을확보하기위해몬테카를로트리탐색 (Montecarlo tree search: MCTS) 알고리즘 [2] 을사용한다. MCTS 의기본원리는동일한상황에서수많은시뮬레이션을반복함으로써결과적으로가장좋은선택을찾는것이다. 이기본원리를바탕으로딥퍼플의시뮬레이션은트리탐색방법으로서선택 (selection), 확장 (expansion), 시뮬레이션, 역전달 (back propagation) 총 4 단계를통해이루어진다. 통계적으로유의한횟수만큼의시뮬레이션을통해루트노드에서선택가능한수들중에서가장가치가높은자식노드를최종선택한다. 본논문의구성은다음과같다. 제 2장에서는관련연구에대해기술하고, 제 3장에서는본논문의중심이되는딥퍼플체스엔진의시스템및소프트웨어구조에대해기술한다. 제 4장에서는딥퍼플의구현환경과정책망과가치망의학습결과에대해기술하고, 끝으로제 5장에서결론및향후연구과제에대해기술한다. II. 관련연구기존에딥러닝에사용한대표적인체스엔진으로는 CNN을사용한 ConvChess [3] 와완전연결신경망을사용한 Giraffe [4] 가있다. ConvChess에서는어떤종류의말이움직이는것이좋은지선택하는 CNN과, 앞에서선택된말이어디로움직이는지좋은지에대한점수를측정하는 CNN으로구성되며, 이두 CNN을이용해서체스게임에서최적의수를예측한다. ConvChess에서사용한데이터로는 Elo rating [5] 이 2000점이상인상대들과 2만게임을하면서 245,000개의 체스말이동을통해 CNN을학습시켰다. ConvChess의최적의말을선택하는 CNN 모델의가장높은정확도는 38.3% 이며, 선택된말의최적의이동할위치를선택하는 CNN 모델의정확도는말의종류에따라 27% ~ 56% 범위의정확도를가진다. Giraffe 엔진의특징은수정된 TD-Leaf(λ) [6] 알고리즘과확률에기반을둔탐색 (probability-based search) 을이용하여체스엔진의성능을높이는데있다. 매학습반복중학습데이터에서무작위로 256의체스상황을추출하여, 스스로 12번순서대로다음수를두고, 12번모두의움직임에대한체스상황에대한점수변화를저장하여, 모든점수변화를축적하면서탐색시작점에추가함으로써, 평가함수를학습시킬때, 장기적인결과에대한패턴을모델화하였다. 또한, Giraffe는 minimax 를수행할때확률한계탐색 (probability-limited search) 이깊이한계탐색 (depth-limited search) 보다더정확하다고판단하여, 확률한계탐색을이용한트리탐색을제안하였으며, 주어진체스게임상황에서, 미리수를내다보지않고, 최적의수가되는말의움직임에대한각각의개연성에대해서점수를측정하였다. Giraffe는대략 FIDE 세계랭킹 [7] 국제마스터레벨의체스실력을갖추고있다. III. 딥퍼플시스템구조 1. 시스템구조그림 1은딥퍼플시스템구조도를보여준다. 딥퍼플의전체시스템구조는 GUI 부분으로이루어진언리얼엔진 (Unreal Engine) [8] 부분과파이썬체스엔진부분으로구성되어있다. 언리얼엔진은그래픽과블루프린트언어로체스의기본로직을구성한다. 블루프린트체스로직과파이썬으로구성된딥퍼플체스엔진과통신은 8자리정수로이루어지며앞의 4자리는명령어를의미하고, 뒤의 4자리정수는말의시작좌표와도착좌표를의미한다. 게임모드는인간 vs 체스엔진, 체스엔진 vs 체스엔진의 2가지모드가제공되며, 언리얼엔진과파이썬체스엔진각각현재체스판을가지고있다. 게임의실질적인로직은파이썬체스엔진을통해진행되고, 그래픽으로보여주는현재체스판의상황은블루프린트체스프로그램안에있다. - 120 -
The Journal of The Institute of Internet, Broadcasting and Communication (IIBC) Vol. 17, No. 5, pp.119-124, Oct. 31, 2017. pissn 2289-0238, eissn 2289-0246 그림 1. 딥퍼플시스템구조도 Fig. 1. Deep Purple System Architecture 파이썬체스엔진에서시시각각변화하는현재의체스판을몬테카를로트리탐색모듈로넘겨주면, 현재의체스판을 0과 1로구성된특징들로변환하여입력데이터를만들고, 이전에먼저학습된가중치값들을텐서플로의 saver 를통해불러온다. 입력데이터와불러온가중치값을이용해비동기적으로정책망과가치망으로부터값을전달받아몬테카를로트리탐색을진행하고, 기존에미리정해놓은트리탐색의깊이, 시뮬레이션횟수에따라시뮬레이션을진행한다. 모든시뮬레이션완료되면루트노드의자식노드중가장높은방문횟수를가진노드를가장좋은다음수로판단해해당노드가가진체스명령어를다음수로선택한다. 선택된다음수는체스엔진과에블루프린트체스프로그램에전달되어현재체스상황에적용시킨다. 이후위와같은과정을반복하여게임을진행한다. 정책망은현재주어진체스판에서이동가능한모든경우의수인 4096개의실수배열로결과를반환한다. 이때 4096개의실수배열은각각의경우의수를 softmax 를이용해 0~1사이의확률값을가지며, 각요소를모두합치면 1이된다. 가치망은현재주어진체스판에대해서체스판의가치를판단한다. 이때의가치는주어진체스판에서승리할확률을의미한다. 가치망은주어진데이터들의결과로승, 무, 패를학습하고, 주어진상황에대해서정책망과마찬가지로 softmax 함수를이용해승, 무, 패의확률을예측한다. 그림 2. Py_ChessGame 클래스구조도 Fig. 2. Py_ChessGame Class Architecture Py_ChessGame은기존에학습된정책망과가치망을바탕으로게임을진행하는부분으로 ChessGame 클래스를통해게임이진행된다. ChessAI의 ask() 함수를호출하면 Monte 클래스에서탐색깊이와횟수인 select_depth, simulation_num을통해 predict() 메서드를호출하고, MCTS 의과정인탐색, 선택, 확장, 역전달의메서드가호출되어탐색을진행한다. 마지막에 choice() 메서드를통해 Tree 클래스 root_node의자식노드중에서가장높은방문횟수를가진노드를선택한다. Tree 클래스는 MCTS 를진행하면서만들어지는트리를관리하는클래스이다. 트리는 Node 클래스로구성되어있으며, Node 클래스는부모노드, 자식노드, 승 / 무 / 패횟수, 색상, 점수들의정보를가진다. GetMovesAndScores 클래스는정책망과가치망의점수를비동기적으로얻기위해사용하는클래스로 get_pn_model(), get_vn_model() 메서드를통해각각의텐서플로의그래프를생성하고 makescores() 와 makemoves() 메서드를통해정책망, 가치망의결과값을얻는다. 2. Py-ChessGame 구조 그림 2는 Py_ChessGame의클래스구조도를나타낸다. - 121 -
DeepPurple : Chess Engine using Deep Learning 그림 3. Data Processing 클래스구조도 Fig. 3. Data Processing Class Architecture 그림 4. 정책망클래스구조도 Fig. 4. Policy Network Class Architecture 3. Data Processing 구조그림 3은데이터를전처리하기위한 Data Processing 클래스구조도를나타낸다. 체스기보데이터는 King Base 사이트 [9] 에서 pgn 기보형식으로되어있다. 데이터를학습시키는과정에서 pgn 기보데이터를일일이입력데이터로변환하여학습시킨다. 이때데이터를불러오는시간을절약하기위해, 한줄의정보로모든체스대국의정보를가질수있는 Forsyth Edwards Notation(FEN) 기보방식 [10] 을이용해저장한다. FenMaker.py 모듈에서 pgn_reader 클래스이용해 pgn 기보파일을읽는다. 전처리과정에서 FEN 기보, 다음수, 게임결과를콜론으로구분하여데이터를 [FEN기보 ] : [ 다음수 ] : [ 게임결과 ] 의형식으로저장한다. fenmake() 메서드에서변수를조정함으로써원하는개수의기보데이터를추출할수있다. 전처리과정에서파이썬 pickle API를이용해객체를파일로저장하고불러올수있는기능을사용하기위해입력데이터를변환하는 Board2Array 클래스와 One-Hot 인코딩으로생성된결과값을얻을수있는 OneHotEncoding 클래스를이용한다. 4. 정책망클래스구조그림 4는정책망클래스구조도를나타낸다. 정책망은다음과같은방법으로학습시킨다. FenLoad 클래스의 getbatchsizedata() 메서드를통해지정한경로에서원하는배치사이즈의데이터를불러온다. Board2Array 클래스와 OneHotEncoding 클래스를이용해입력데이터와결과데이터를받아낸다. Board2Array 클래스는넘겨받은체스판을 board2array() 메서드를이용해입력데이터로변환한다. 각각의체스판은 8x8의크기에 0과 1로구성되어있다. 학습모델에필요한입력데이터는다음과같다. white(), black(): 각색상을판단 piece(): 체스판위에말의존재유무판단 slidingpiece(): 주어진체스판의각좌표에서말이이동할수있는좌표유무판단 pin(): 체스상황에서 pin에해당하는말을판단 check(): 주어진체스판에서킹의위치판단 turn(): 체스판에서흑 / 백턴판단 castling(): 현재체스판에서캐슬링권한을가지고있는경우해당말을판단가치망의경우정책망과전체구조는같으며, 결과값에대해서 One-Hot 인코딩의개수가 3개로사용되고, 같은입력데이터에대해출력데이터를승, 무, 패세가지경우에대해서 One-Hot 인코딩으로변환해학습을진행한다. - 122 -
The Journal of The Institute of Internet, Broadcasting and Communication (IIBC) Vol. 17, No. 5, pp.119-124, Oct. 31, 2017. pissn 2289-0238, eissn 2289-0246 IV. 딥퍼플구현환경및학습결과 딥퍼플은 Windows10 운영체제에서딥러닝구현에필요한라이브러리로텐서플로우를이용하였다. Elo 점수 2000대이상의체스선수들의기보를이용하여체스기보데이터를전처리하여텐서플로우를통해서데이터를학습시켜유효한수를내놓는모델과각각의체스판에서이길확률을측정하는모델을구현하였다. 체스로직은 python-chess api를이용하였으며, 텐서플로우와 python-chess api의개발언어는파이썬을사용하였으며, 체스엔진에서사용하는사용자인터페이스는언리얼엔진4를사용하여구현하였다. 그림 5는 CNN 모델을통해정책망과가치망을학습시킨결과를보여준다. 정책망의경우 1천만개의기보를 epoch( 반복학습횟수 )=5, batch size=10000으로학습을진행한결과, 43% 의정확도를보이며, 손실함수 cost는 1.9를보였다. 출력값이 19x19개인, CNN을이용한알파고의정확도가 50~60% 사이의정확도를보이고본연구에서의정책망은 4096개의출력값에대하여 43% 의정확도를보이므로결과를제대로학습이제대로진행되었음을알수있다. 초기화에사용한방법은 Xavier initializer를사용하였고초기 cost가 8.3 정도로형성되어, 초기화가잘되었는지확인하는공식 ln(1/4096) = 8.31776616672와비교해보았을때적절하게되었음을확인할수있다. 모델에대한실험은 layer 개수를 3, 5, 13로진행하였고, 1천만개의데이터에대해서는정확도와손실함수 cost가비슷하게나타난다. 더오래학습을진행한 13개의 layer 가 cost 값이가장낮으므로선택하여야하나, 몬테카를로트리탐색을보다빠르게진행하기위해서는 layer 의개수가작은모델을사용하여학습하였다. 가치망의경우일반적으로주어진체스판에대해서승, 무, 패의 3가지경우의수가고르게분포되어있어손실함수 cost가진동하면서줄어들지만안정화되지않은모습을보여준다. 그림에서보는바와같이조금씩감소하는양상을보이지만 1점대에서계속진동한다. 기존의 CNN을이용한체스엔진의경우 1억만개의데이터를사용하고, 알파고또한 3천만개의데이터를가지고 3주간학습을진행한것과비교해볼때, 본연구에서는 1천만개의데이터를사용하였으므로, 데이터의개수를증가시키고더오랜시간학습을진행한다면개선의여지가남아있다. 그림 5. 정책망및가치망정확도및비용그래프 Fig. 5. Accuracy and Cost Graph of Policy/Value Network Ⅴ. 결론 본논문은딥러닝을이용한인공지능체스엔진인딥퍼플에대해기술하였다. 딥퍼플체스엔진은크게몬테카를로트리탐색과 CNN구조로구성된정책망, 가치망으로구성되어있다. 정책망은주어진체스판상황에대하여모든말들의위치를파악함으로써최적의다음수를예측하는모델이며, 가치망은주어진체스상황이누구에게얼마나유리한상황인지를예측하여주는모델이다. 딥러닝을통해구축된모델인정책망과가치망으로부터산출된값을이용하여몬테카를로트리탐색방식의시뮬레이션을진행한후결과를분석하여가장좋은수를결정하도록구현하였다. CNN 모델을통해정책망과가치망을학습시킨결과, 정책망의경우 43% 의정확도와 1.9의손실함수 Cost를보였으며, 가치망의경우승, 무, 패의 3가지경우의수가고르게분포되어있어손실함수 cost가진동하면서줄어들지만 1점대에서계속진동하는결과를보였다. 향후연구과제로는딥퍼플의더많은데이터를사용하여학습을진행하는일과, 성능개선을위해정책망과가치망의알고리즘을개선시키는연구가진행될예정이다. References [1] Clark, Christopher and Storkey, Amos. Teaching deep convolutional neural networks to play Go, - 123 -
DeepPurple : Chess Engine using Deep Learning arxiv preprint arxiv:1412.3409, 2014. [2] Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P.,Tavener, S., Perez, D., Samothrakis, S., & Colton, S. A survey of Monte Carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 4 No. 1, pp.1-43, 2012. DOI: https://doi.org/10.1109/tciaig.2012.2186810 [3] Barak Oshri and Nishith Khandwala, Predicting Moves in Chess using Convolution Neural Networks, http://github.com/barakoshiri/convchess [4] Matthew Lai., Giraffe: Using Deep Reinforcement Learning to Play Chess, arxiv:1509.01549v2, 2015. [5] https://en.wikipedia.org/wiki/elo_rating_system [6] Jonathan Baxter, Andrew Tridgell, and Lex Weaver TDLeaf(λ) Combining Temporal Difference Learning with Game-Tree Search Australian Journal of Intelligent Information Processing Systems, 1998. [7] https://en.wikipedia.org/wiki/fide_world_ Rankings. [8] https://www.unrealengine.com/ko/what-isunreal-engine-4. [9] http://www.kingbase-chess.net/ [10] https://en.wikipedia.org/wiki/forsyth_edwards _Notation 김성환 ( 준회원 ) 김영웅 ( 정회원 ) 저자소개 2014 년 ~ 현재한성대학교컴퓨터공학과 < 주관심분야 : 모바일시스템, 딥러닝 > 1993 년 KAIST 전산학과박사 1984 ~ 1997 년 KT 통신망연구소 1997 년 ~ 현재한성대학교컴퓨터공학부교수 < 주관심분야 : 데이터모델링, 소프트웨어신뢰도, 소프트웨어설계 > 본연구는한성대학교교내연구비지원과제임. - 124 -