AlphaGo의 인공지능 알고리즘 분석 4

3. AlphaGo의 게임 탐색 알고리즘 – 몬테카를로 트리 탐색

□ 바둑 게임의 특성과 인공지능

 ￮ 바둑은 상대방 바둑돌을 많이 포위할수록 승리한다는 간단한 규칙 때문에 자유도가 매우 높으나 “정석”이 존재

 －고대 중국에서부터 시작된 바둑은 상대에게 승리할 수 있는 여러 가지 방법이 축적되어 왔음

 ＊바둑의 첫 수는 귀의 화점에 두는 것이 일반적

 －바둑기사처럼 바둑을 두는 인공지능 프로그램을 개발하기 위해서는 바둑기사들의 패턴을 학습하는 것이 중요한 요소

 ＊예를 들어, 빈 바둑판에 둘 수 있는 경우의 수는 361가지이나 바둑기사들 이 착수하는 지점은 한정되어 있음

 ￮ 바둑기사들은 “수읽기”를 통해 경기의 진행이 유리하도록 착수를 결정

 －이 과정은 앞서 설명한 게임 트리의 탐색과 유사

 ＊착수 가능한 여러 지점에서 다양한 전개과정이 도출되므로, 제한된 시간 안에 최대한 많은 수읽기를 하는 것이 필요

 －지역적인 형세판단을 통해 전체적인 게임의 승산을 판단

 ￮ 프로 바둑기사들은 직관적인 판단을 통해 착수를 결정

 －바둑의 경우의 수가 거의 무한대에 가까운 점은 사람에게도 마찬가지이므로 경험을 바탕으로 한 착수가 가능

 －프로 바둑기사는 묘수를 개발하여 다른 기사들이 사용하지 않은 새로운 전략을 제시  ￮ 바둑은 초읽기라는 규칙이 있기 때문에 인공지능 프로그램은 제한된 시간 안에 프로 바둑기사와 같이 수읽기와 형세판단을 하여 최적의 수를 예측해야 함

□ MCTS(Monte Calro Tree Search - 몬테카를로 트리 탐색) : 바둑에서 가장 널리 사용되는 인공지능 알고리즘

 ￮ MCTS는 최소-최대 알고리즘의 성능을 개선한 것으로, 모든 경로를 탐색하 는 것이 불가능 할 때 효율적

 ￮ [그림 7]는 MCTS의 일반적인 구조를 나타내고, 이를 바둑 인공지능 관점에 서 해석해보면 <표 4>와 같음

￮ MCTS는 게임 트리 탐색에서 두 가지 핵심요소가 있음. <표 5>

 －바둑에서 정책은 전문가의 전략이 될 수도 있고, 과거 기보 데이터에서 많은 프로 기사들이 선호한 패턴이 될 수도 있음 (선호되는 방향을 정의)

 －가치는 바둑 국면의 형세판단을 근사하여 수치화한 것으로 볼 수 있음. 정확한 값은 모든 경우의 수를 계산하여 게임 종료 시점까지 가봐야 하 기 때문에 계산이 어려움

 ￮ MCTS에서 정책은 정확한 가치를 추정하는데 중요한 역할을 함. 정책은 게 임의 미래 상태를 예측하기 때문에 게임의 특성과 경험을 반영

 －만약 정책이 최적화(optimize)하는 방향으로 수렴(converge)한다면, 가치 역시 최적의 값으로 수렴한다고 볼 수 있음 (i.e. 다음 착수가 가장 최적 화된 방향이라면 경기에 승리할 확률이 높아짐)

□ AlphaGo의 MCTS는 더 효율적인 정책과 가치를 구현하여 성능을 프로수 준으로 끌어올림

 ￮ 프로기사의 기보를 바탕으로 정책과 가치를 제안

 －전문 바둑기사의 관점으로 탐색의 폭과 깊이를 결정하기 때문에, AlphaGo의 기보를 분석한 많은 전문가들은 사람과 매우 유사한 수를 둔 다고 평함

 ￮ 또한, 스스로 대국하는 학습기법을 통해 정책과 가치의 성능을 향상시킴

출처 : 소프트웨어정책연구소