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

2. 게임 트리 탐색 알고리즘

□ 게임 트리 탐색은 인공지능 게임 프로그램을 구현하기 위해 사용

￮ 체스나 장기, tic-tac-toe 와 같이 두 플레이어가 번갈아가며 수를 두는 게 임은 일반적으로 트리 형태로 표현

￮ 바둑에서의 게임 트리는 [그림 1]과 같이 표현되고, 두 플레이어가 번갈아 가면서 수를 두면 트리가 확장

－특정 게임 상태에서 다음 수를 예측하기 위해서는 수읽기를 통해 가장 승리할 확률이 높은 곳을 결정

－이 과정이 트리의 탐색이고, 이론적으로는 현재 상태에서 가능한 모든결과를 미리 알 경우 가장 승률이 높은 수를 선택

＊세계 체스챔피온을 꺾은 IBM의 딥블루는 가능한 모든 결과를 탐색한 예

￮ 트리탐색기법(트리순회 : Tree traversal)은 트리 구조에서 각각의 노드를 한번씩, 체계적인 방법으로 방문하는 과정

－트리탐색 기법에는 탐색 순서에 따라 전･중･후위 및 레벨 순서 순회기 법이 있음

－이중 전위순회(preorder)는 깊이우선의 탐색(depth-first search: DFS) 이 라고도 하며, 이후 설명할 MinMax 알고리즘의 탐색방법

－트리의 깊이우선 탐색 과정 [그림 4]

□ 최소-최대(Minimax, MM) 알고리즘 : 게임에서 한 플레이어에게 유리한 수 는 상대 플레이어에게는 불리한 수

￮ 상대의 승산을 최소화하고 자신의 승산을 최대화 하는 것이 게임에서 승리하 는 방법이기 때문에, 이 경로를 찾는 것이 인공지능 게임 프로그램의 핵심

￮ [그림 5]는 깊이가 4수로 제한된 게임의 MinMax 알고리즘의 탐색 결과 예시

－[그림 5]의 MinMax 알고리즘의 트리 탐색 과정은 [그림 4]와 동일한 깊 이 우선 탐색을 수행

－각 서브트리의 탐색이 끝나면 기존 탐색된 노드들을 역으로 거슬러 올 라가면서 상위노드로 평가 값을 반영

＊이때, 최대값과 최소값을 교대로 비교하여 최종 서브트리를 선택

□ 게임 트리 탐색의 효율성이 인공지능 프로그램의 성능을 좌우

￮ 최소-최대 알고리즘의 경우 트리의 모든 노드를 탐색해야하기 때문에, 게임 의 복잡도가 클 경우 트리를 전부 확장하여 탐색하는 것이 현실적으로 불 가능

￮ 알파-베타 가지치기 알고리즘은 최소-최대 알고리즘에서 더 이상 계산할 필요가 없는 경로를 제거하는 기법으로 계산량을 대폭 절감

－상대가 현재 위치 이후의 어떤 지점에서 더 유리한 결과를 얻을 경우, 현재위치를 만드는 수는 나에게 무조건 불리

＊나에게 불리한 수가 만들어지는 지점부터 트리의 가지를 침(Pluning)

－가지치기 판단을 위해서는 게임트리 검색의 매 순간마다 Player1(나)에 게 유리한 현재 최선의 값(Alpha)과 Player2(상대)에게 유리한 현재 최선 의 값(Beta)을 기억

＊Alpha 는 maximizing player(Player1)가 보장하는 최소의 값(초기값은 -∞) (나에게 유리한 상황의 최소값)

＊Beta 는 minimizing player(Player2)가 보장하는 최대의 값(초기값은 +∞) (나에게 불리한 상황의 최대값)

－가지치기는 Alpha cut-off(αPruning) 와 Beta cut-off(βPruning) 가 있음

＊Alpha cut-off는 어떤 경우가 Player1(나)이 Player2(상대)보다 불리하여 그 경우를 선택하지 않을 때 수행

＊Beta cut-off는 어떤 경우가 Player1(나)이 Player2(상대)보다 유리하여 상 대가 그 경우를 선택하지 않을 때 수행

￮ 바둑은 앞서 기술한바와 같이 게임의 복잡도가 매우 크기 때문에, 인공지능 바둑 프로그램은 막대한 계산량을 최소화하고 게임 예측성능을 높이는 것 이 목표

－바둑을 트리로 표현하면 250^150의 노드를 갖게 되므로, 알파-베타 가지치 기는 바둑 인공지능 구현에 매우 비효율적

－모든 노드를 탐색하는 것이 사실상 불가능하므로, 트리 탐색의 폭과 깊 이를 적절하게 제한하는 방법이 필요함

＊이 방법이 AlphaGo에서 사용된 것으로 자세한 내용은 다음 장에서 다룸

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