안녕하세요.
이번에 알파고가 많이 이야기가 되면서 AI 알고리즘들에 대해 얘기가 많아 뻘글 하나 작성해봅니다.
기존에 바둑 AI 프로그램들 뿐만 아니라 이번 알파고에서도 사용되고 있는 몬테 카를로 (Monte Carlo) 라는 녀석에 대해 한번 알아볼까 합니다.
어떤 확률에 기반한 문제가 있을 경우, 이를 해결하기 위해 확률 모델이라는 것을 설계를 하고 문제를 해결합니다. 확률 모델을 설계 할 때 고려되어야 할 사항이 모델을 설계할때 들어갈 변수들 간의 관계가 확실하여 예측을 정확하게 할 수 있어 해를 찾을 수 있는 경우가 있는 반면에 변수간의 관계가 불명확하여 해를 찾기 힘들어 해에 근접한 수를 찾는 경우가 있습니다.
예를들어 바둑의 경우, 내가 어떤 수를 놓으려고 할 때, 다음 상대방의 수에 따라 그 다음 자신의 수를 계산하는 방식이기 때문에 위의 확률 모델 종류의 후자라고 할 수 있습니다.
보통 후자의 경우, 수치적 난수를 이용하여 시뮬레이션을 통해 특정 수에서 수렴이 되는 수를 찾는 방식을 사용합니다. 이런 확률 모델의 시뮬레이션에서 일반적으로 사용되는 방식이 몬테 카를로 시뮬레이션 입니다.
몬테 카를로 방식을 이용하여 원주율 (파이)를 구하는 예를 들어 봄으로써 몬테 카를로의 동작 원리를 이해해보도록 하겠습니다. XD
우리가 처음에 원주율을 구하는 방식을 배울 때 원 지름에 대한 원의 둘레의 길이로 배웁니다. 하지만 여기서는 몬테카를로를 이용하여 확률적으로 원주율을 구하려고 합니다.
다음과 같이 한 변의 길이가 1인 정사각형과 그 안에 반지름이 0.5인 원이 있다고 가정합니다.
정사각형의 넓이 = 1 * 1 = 1
원 넓이 = (1 / 2) * (1 / 2) * 원주율 = 원주율 / 4
원 넓이 / 정사각형 넓이 = (원주율 / 4) / 1
따라서, 원주율 = (원 넓이 * 4) / 정사각형 넓이 가 됩니다.
우리가 하려고 하는것은 이 안에 점을 무작위 하게 막 찍습니다. 중요한것은 무작위성의 높을 수록 연산 결과를 더욱 정확해 집니다. :D
확률적인 방식에 의해 찍인 원 안에 있는 점의 수와 정사각형 안에 있는 점의 수 (이는 전체 점 의 수와 같습니다) 로 위의 원주율을 다음과 같이 계산할 수 있습니다.
원주율 = (원 넓이 * 4) / 정사각형 넓이 ≒ (원 안의 점의 수 * 4) / 정사각형 안의 점의 수
아래는 python으로 만든 몬테 카를로 기법을 이용한 원주율 계산 시뮬레이션 코드 입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | import random radius = 1 / 2 cnt_circle = 0 cnt_square = 0 idx = 0 cnt_iter = 10000000 while idx < cnt_iter: rnd_x = random.random() rnd_y = random.random() if (rnd_x - radius)**2 + (rnd_y - radius)**2 < (radius*2)**2: cnt_circle += 1 cnt_square += 1 idx += 1 print "The circle count is : %d" % (cnt_circle) print "The square count is : %d" % (cnt_square) print "The ratio of (4 * circle) / square = pie : %f" % ( (4.0 *cnt_circle) / cnt_square ) | cs |
결과는 다음과 같습니다.
100개의 무작위한 점을 찍는 경우, The ratio of (4 * circle) / square = pie : 2.920000
1000개의 무작위한 점을 찍는 경우, The ratio of (4 * circle) / square = pie : 3.176000
10000개의 무작위한 점을 찍는 경우, The ratio of (4 * circle) / square = pie : 3.152800
100000개의 무작위한 점을 찍는 경우, The ratio of (4 * circle) / square = pie : 3.136080
1000000개의 무작위한 점을 찍는 경우, The ratio of (4 * circle) / square = pie : 3.141328
10000000개의 무작위한 점을 찍는 경우, The ratio of (4 * circle) / square = pie : 3.141556
짜잔! 이런식으로 확률적인 방법을 통해 원주율을 계산을 할 수 있습니다.
더욱 정확히 계산을 원한다면 특정 소수점 밑으로 수렴될때까지 반복을 더 하시면 됩니다. 위에서도 썻지만 결과는 랜덤성에 굉장히 의존을 하고 있기 때문에 좋은 랜덤 함수를 사용해야 합니다 :)
여기까지 몬테 카를로 기법을 이용하여 확률적으로 원주율을 계산하는 방법을 알아봣습니다.
추가적으로 제가 예전에 해킹 대회 문제로 풀었던 것 중에 몬테 카를로 시뮬레이션을 사용했던 적이 있었는데, 그 때의 문제는 블랙잭 이였습니다.
"I'm playing heads up blackjack. I'm dealt Ace-2 and the dealer has 3 showing. What's the probably of winning if: 1) I stand or 2) I kept playing."
이라는 문제였는데, 블랙잭을 할 때 제 손패가 Ace와 2를 갖고 있고 딜러가 3이 펼쳐져 있고 한장은 안보이는 게임일 때 내가 바로 stop 할 경우 이길 확률과 계속 패를 받는 경우 이길 확률을 계산하여 어떤 전략이 더 이길 확률이 높은지 찾는 문제였습니다.
즐거운 주말 되세요 ^^
창작글
글쓰기