알파고는 어떻게 이세돌 9단을 이겼나

여러 가지 이유가 있겠지만, 이 글에서는 그중에 하나인 몬테카를로 트리 서치에 대해 이야기해보고자 한다.

1. 왜 사람들은 알파고의 승리에 그토록 놀랐을까?

그것은 아마도 바둑이라는 경기가 지닌 특수성 때문일 것이다. 그동안 우리가 바둑에서 컴퓨터가 사람에게 이길 수 없다고 생각한 이유는 너무 많은 경우의 수였다. 그러나 알파고는 기보에서 학습된 사례를 기반으로 몬테카를로 트리 서치(MCTS : Monte Carlo Tree Search) 라는 알고리즘을 통해 의미 있게 돌이 놓이는 위치만을 선택해서 확률을 계산한다.

 

2. 몬테카를로 트리 서치는?

몬테크를로 트리 서치라는 이름은 모나코의 몬테카를로라는 도박으로 유명한 도시에서 따왔다고 한다

컴퓨터 과학에서 몬테카를로 트리 탐색(Monte Carlo tree search, MCTS)은 모종의 의사 결정을 위한 체험적 탐색 알고리즘으로, 난수(특정한 순서나 규칙을 가지지 않는 수, 무작위 숫자)를 이용하여 확률 현상을 수치를 통한 실험으로 관찰하는 방법이다.

처음에는 핵반응에 사용되는 기법이었으나 컴퓨터의 보급과 발전으로 공학, 물리학 등 여러 분야에 널리 적용되었다. 2006년 컴퓨터에 바둑을 위해 도입되었고 체스, 포커와 같은 보드게임이나 다른 전략 게임에서도 사용되었다.

몬테카를로 트리 탐색을 줄여서 MCTS라고도 하는데, MCTS의 목적은 가장 최선의 움직임을 분석하는 데에 있으며, 무작위로 이동하면서 샘플을 얻은 것으로 트리를 확장한다.

즉, 도박처럼 난수(랜덤)을 이용하여 확률적으로 계산하는 방법이다.

 

3. 난수를 이용해서 확률로 원의 넓이 구해보기

목표 : 확률을 이용해 원의 넓이를 구해보자.

1. 정사각형 안에 사각형의 변과 같은 지름을 가진 원을 그린다. 
2. 정사각형 안에 임의의 점을 그린다. 
3. 그린 점 중에 원 안에 있는 점의 개수를 구해서 점이 원 안에 들어갈 확률을 구한다. 
4. 위에서 구한 확률을 통해 원의 넓이를 구해보자!

 

3. 1 정사각형과 원 그리기

먼저 정사각형과 정사각형의 변의 길이와 같은 지름을 가지는 원을 그려준다.

import numpy as np
import matplotlib.pyplot as plt

# 원을 만들어주는 함수
def make_circle(c, r):
    theta = np.linspace(0, 2 * np.pi, 256)
    x = r * np.cos(theta)
    y = r * np.sin(theta)    
    return np.vstack((x, y)).T + c

c = np.array([0.5, 0.5]) # 원의 중심점
r = 0.5 # 반지름

circle = make_circle(c, r)

plt.figure(figsize = (10,10))
# 원 그리기
plt.plot(circle[:,0], circle[:, 1], 'b-')
# 사각형 그리기
plt.plot([0,1], [1, 1], 'r-')
plt.plot([1,1], [0, 1], 'r-')
plt.plot([0,1], [0, 0], 'r-')
plt.plot([0,0], [0, 1], 'r-')

plt.grid()
plt.xlim(-0.25,1.25)
plt.ylim(-0.25,1.25)
plt.show()

한 변의 길이가 1인 정사각형과 지름이 1인 원을 그렸다.

정사각형의 넓이는 1, 그리고 원의 넓이는 0.785이다.

 

3. 2 정사각형 안에 임의의 점 100개 뿌리기

0부터 1까지 랜덤하게 생성한 두 개의 실수를 사각형 안에 그려준다.

# 0부터 1까지 랜덤한 두 개의 실수를 생성한다.
dot = np.random.rand(100, 2) # 임의의 수 100개 만들기

# 원을 만들어주는 함수
def make_circle(c, r):
    theta = np.linspace(0, 2 * np.pi, 256)
    x = r * np.cos(theta)
    y = r * np.sin(theta)    
    return np.vstack((x, y)).T + c

c = np.array([0.5, 0.5]) # 원의 중심점
r = 0.5 # 반지름

circle = make_circle(c, r)

plt.figure(figsize = (10,10))
# 원 그리기
plt.plot(circle[:,0], circle[:, 1], 'b-')
# 사각형 그리기
plt.plot([0,1], [1, 1], 'r-')
plt.plot([1,1], [0, 1], 'r-')
plt.plot([0,1], [0, 0], 'r-')
plt.plot([0,0], [0, 1], 'r-')
# 랜덤한 점 그리기
plt.scatter(dot[:, 0], dot[:, 1]) # 100개

plt.grid()
plt.xlim(-0.25,1.25)
plt.ylim(-0.25,1.25)
plt.show()

 

3. 3 원 안의 점의 개수 세주기

피타고라스 공식을 이용해 원의 중심점과 점 사이의 거리를 구하여 원 안의 점의 개수를 파악한다.

# 먼저 중심점과 점 사이의 거리 구하기
# 중심점과 0.5(반지름) 이내에 있어야 원 안에 있는 점이다.
point = np.array([0.5, 0.5]) # 중심점
point

# 피타고라스의 공식을 이용해서 점과 점 사이의 거리를 구해준다.
a = point[0] - dot[0, 0] # x 좌표의 거리
b = point[1] - dot[0, 1] # y 좌표의 거리

import math
dis = math.sqrt((a * a) + (b * b)) # 중심점과 점과의 거리


# 거리를 사용해 원 안의 임의의 점들의 개수 구하기
count = 0 # 점의 개수 카운트

for i in range(100):
    a = point[0] - dot[i, 0]
    b = point[1] - dot[i, 1]
    dis = math.sqrt(a * a + b * b) # 거리
    
    if dis <= 0.5: # 중심점과의 거리가 0.5 이하인 점
        count += 1
count

 

임의의 100개의 점 중 76개의 점이 원 안에 들어있다. 즉, 76%의 확률로 점이 원 안에 들어간다는 말과 같다.

그럼 사각형의 면적에 원 안에 점이 들어갈 확률을 곱하면 0.76이라는 원의 면적을 구할 수 있다. 원주율을 이용해서 계산한 원의 면적 0.785와 조금 차이가 있다. 

점의 개수를 늘려서 다시 한번 계산해보자.

 

3. 4 점의 개수 늘려보기

1,000개

원의 넓이 : 0.778

 

10,000개

원의 넓이 : 0.788

 

100,000개

원의 넓이 : 0.786

확실히 점의 개수를 늘릴 때마다 원의 넓이에 가까워졌다. 코드를 실행할 때마다 점의 개수가 달라지면서 원의 넓이가 변하지만 점의 개수를 늘렸을 때 조금 더 실제 원의 넓이와 비슷한 원의 넓이를 구할 수 있었다. 이처럼 몬테카를로 트리 탐색은 함수와 같은 수식으로 해를 찾기가 쉽지 않을 때 적용할 수 있다.

 

4. 마치며

난수를 이용해 확률로 답을 찾아가는 시뮬레이션을 파이썬으로 구현해보면 어떨까라는 생각을 시작으로 직접 만들어보게 됐다. 만들어보면서 생각처럼 쉽지 않은 것도 있었다(원을 그리는 거라던지, 또 원을 만드는 것, 마지막으로 원을..). 그래도 실제 나오는 값들을 보면서 굉장히 흥미로웠고 직접 코드를 치며 내가 원하는 것을 만들어가는 과정 또한 정말 즐거웠다.

이 정말 작고 여린 나만의 코드를 짜 보면서 자신감을 얻었다는 것에 대해 좋은 소득이었다고 생각이 든다. 다음에는 겨우내 묵혀뒀던 도토리 프로젝트를 시작해볼까 한다.

 

참고자료 연구소

블로그) 경인교육대학교 미래인재연구소 & 인공지능교육 연구소

Monte Carlo Tree Search(몬테카를로 트리 탐색)

유튜브) 알파고에도 사용된 몬테카를로 방법