몬테카를로 트리 탐색

소온 이명식 | d4soft2002@naver.com | 입력 2017-11-10 11:59:36
  • 글자크기
  • -
  • +
  • 인쇄

[K스포츠장기= 소온 이명식]

몬테카를로 트리 탐색 – 딥러닝을 가미하여 알파고 개발

 

몬테카를로 방법(Monte-Carlo method)은 난수를 이용하여 함수의 값을 확률적으로 계산하는 방법이다. 계산하려는 값이 수학적 형식으로 표현되지 않거나 아주 복잡한 경우에 근사적인 값을 계산하기 위하여 사용된다.

 

▲몬테카를로 트리 탐색

 

특히 인공지능 게임분야에 있어 성공적인 결과를 보였으며, 현재는 바둑에 몬테카를로 트리 탐색(MCTS: Monte-Carlo Tree Search)을 적용하여 놀라운 성과를 내고 있다.

한 예로 MCTS를 삼목(Tic-Tac-Toe)에 적용하게 되면, 위의 표에서 보듯이 중앙 첫 착점의 승리 확률이 50.6%가 됨을 10만 번의 시뮬레이션을 통해 알 수 있다. 즉 첫 착점으로 중앙이 가장 좋고, 그 다음은 귀가 되며, 변은 제일 나쁜 착점이 된다.

 

이렇게 몬테카를로 트리를 이용하는 것은 수많은 대국을 통해 얻은 확률을 기초로 하여 승률이 높은 확률의 착점을 고르도록 하는 것이다. 이 방식은 기존의 가지치기 방식과 비교하면 장점도 있고 단점도 있다. 정확도는 가지치기 방식에 비해 떨어지지만 반대로 짧은 시간 안에 최선의 수 또는 차선의 수를 골라낼 수 있다는 것이다.

 

​바둑이나 장기에는 시간 제한(초읽기)이 있어 무한정 사고할 수 있는 게 아니기 때문에 몬테카롤로 방식은 바둑 장기 같은 보드게임에서 상당한 위력을 발휘하는 것이다. 이번에 구글에서 개발하여 바둑 프로 이세돌과 겨룬 알파고도 물론 몬테카를로 방식을 사용한다. 그러나 이 알파고에는 또 다른 알고리즘인 딥러닝(Deep Learning)을 추가하였다. 딥러닝은 기계 학습의 핵심 기능이고 이를 통해 바둑을 학습시킴으로써 비로서 알파고를 인공지능이라 부를 수 있는 것이다.

 

 

컴퓨터 바둑 프로그램

 

이러한 몬테카를로 방식을 이용한 바둑 프로그램은 결코 알파고만 있는게 아니다.

비록 언론에서 큰 스포트라이트를 받지는 못했지만 한국의 임재범 씨가 개발한 “돌바람” 이라는 게 있다.

 

매년 세계컴퓨터바둑토너먼트라는 대회가 열리는데 여기에는 컴퓨터 바둑 프로그램들이 참가하여 서로 실력을 겨룬다. 즉 컴퓨터끼리 바둑 실력을 겨루는 것이다. 2015년 11월에는 중국에서 열렸는데 한국을 비롯해 중국, 일본, 대만, 미국, 프랑스, 체코 등 7개국 9개 팀이 참가한 이 대회에서 ‘돌바람’은 결승에서 일본의 강호 ‘젠(zen)’을 꺾고 우승컵을 거머쥐었다.

 

그동안 일본의 ‘젠’이 세계 최고 수준의 프로그램으로 평가되어 왔고 강력한 우승후보였는데 ‘돌바람’이 ‘젠’을 꺾고 우승한 것이다. ‘돌바람’은 UEC 대회 후 조치훈 9단과 4점 접바둑으로 승리했다. 제한 시간은 30분에 초읽기 30초였다. ‘돌바람’은 몬테카를로 방식이라는 알고리즘을 채용했는데 이것은 수많은 모의대국의 결과물에 기초해 더 나은 착수를 얻어내는 방식이다.

 

북한도 ‘은별’이라는 프로그램이 있다. 제1회 UEC 대회에서 우승을 차지했었다. 한국에 상업화된 프로그램 시디가 출시된 적도 있었는데 세계대회에 출전하는 프로그램과는 실력 차이가 많이 난다.

 

 

[저작권자ⓒ K스포츠장기. 무단전재-재배포 금지]

  • 카카오톡 보내기
  • 카카오스토리 보내기
  • 글자크기
  • +
  • -
  • 인쇄
  • 내용복사

[기사댓글]

헤드라인

묘수의세계

인문학으로 읽는 장기의 역사

more

많이본 기사

최신기보

more

장기칼럼

more

아카데미

more