3. AlphaGo의 게임 탐색 알고리즘 – 몬테카를로 트리 탐색
□ 바둑 게임의 특성과 인공지능
○ 바둑은 상대방 바둑돌을 많이 포위할수록 승리한다는 간단한 규칙 때문에 자유도가 매우 높으나 “정석”이 존재
-고대 중국에서부터 시작된 바둑은 상대에게 승리할 수 있는 여러 가지 방법이 축적되어 왔음
*바둑의 첫 수는 귀의 화점에 두는 것이 일반적
-바둑기사처럼 바둑을 두는 인공지능 프로그램을 개발하기 위해서는 바둑기사들의 패턴을 학습하는 것이 중요한 요소
*예를 들어, 빈 바둑판에 둘 수 있는 경우의 수는 361가지이나 바둑기사들 이 착수하는 지점은 한정되어 있음
○ 바둑기사들은 “수읽기”를 통해 경기의 진행이 유리하도록 착수를 결정
-이 과정은 앞서 설명한 게임 트리의 탐색과 유사
*착수 가능한 여러 지점에서 다양한 전개과정이 도출되므로, 제한된 시간 안에 최대한 많은 수읽기를 하는 것이 필요
-지역적인 형세판단을 통해 전체적인 게임의 승산을 판단
○ 프로 바둑기사들은 직관적인 판단을 통해 착수를 결정
-바둑의 경우의 수가 거의 무한대에 가까운 점은 사람에게도 마찬가지이므로 경험을 바탕으로 한 착수가 가능
-프로 바둑기사는 묘수를 개발하여 다른 기사들이 사용하지 않은 새로운 전략을 제시 ○ 바둑은 초읽기라는 규칙이 있기 때문에 인공지능 프로그램은 제한된 시간 안에 프로 바둑기사와 같이 수읽기와 형세판단을 하여 최적의 수를 예측해야 함
□ MCTS(Monte Calro Tree Search - 몬테카를로 트리 탐색) : 바둑에서 가장 널리 사용되는 인공지능 알고리즘
○ MCTS는 최소-최대 알고리즘의 성능을 개선한 것으로, 모든 경로를 탐색하 는 것이 불가능 할 때 효율적
○ [그림 7]는 MCTS의 일반적인 구조를 나타내고, 이를 바둑 인공지능 관점에 서 해석해보면 <표 4>와 같음
○ MCTS는 게임 트리 탐색에서 두 가지 핵심요소가 있음. <표 5>
-바둑에서 정책은 전문가의 전략이 될 수도 있고, 과거 기보 데이터에서 많은 프로 기사들이 선호한 패턴이 될 수도 있음 (선호되는 방향을 정의)
-가치는 바둑 국면의 형세판단을 근사하여 수치화한 것으로 볼 수 있음. 정확한 값은 모든 경우의 수를 계산하여 게임 종료 시점까지 가봐야 하 기 때문에 계산이 어려움
○ MCTS에서 정책은 정확한 가치를 추정하는데 중요한 역할을 함. 정책은 게 임의 미래 상태를 예측하기 때문에 게임의 특성과 경험을 반영
-만약 정책이 최적화(optimize)하는 방향으로 수렴(converge)한다면, 가치 역시 최적의 값으로 수렴한다고 볼 수 있음 (i.e. 다음 착수가 가장 최적 화된 방향이라면 경기에 승리할 확률이 높아짐)
□ AlphaGo의 MCTS는 더 효율적인 정책과 가치를 구현하여 성능을 프로수 준으로 끌어올림
○ 프로기사의 기보를 바탕으로 정책과 가치를 제안
-전문 바둑기사의 관점으로 탐색의 폭과 깊이를 결정하기 때문에, AlphaGo의 기보를 분석한 많은 전문가들은 사람과 매우 유사한 수를 둔 다고 평함
○ 또한, 스스로 대국하는 학습기법을 통해 정책과 가치의 성능을 향상시킴
출처 : 소프트웨어정책연구소
'인공지능' 카테고리의 다른 글
AlphaGo의 인공지능 알고리즘 분석 6 (0) | 2016.07.28 |
---|---|
AlphaGo의 인공지능 알고리즘 분석 5 (0) | 2016.07.28 |
AlphaGo의 인공지능 알고리즘 분석 3 (0) | 2016.06.24 |
AlphaGo의 인공지능 알고리즘 분석 2 (0) | 2016.06.20 |
AlphaGo의 인공지능 알고리즘 분석 1 (0) | 2016.06.20 |