안녕하세요. <div><br></div> <div>이번에 알파고가 많이 이야기가 되면서 AI 알고리즘들에 대해 얘기가 많아 뻘글 하나 작성해봅니다.</div> <div><br></div> <div>기존에 바둑 AI 프로그램들 뿐만 아니라 이번 알파고에서도 사용되고 있는 몬테 카를로 (Monte Carlo) 라는 녀석에 대해 한번 알아볼까 합니다. </div> <div><br></div> <div>어떤 확률에 기반한 문제가 있을 경우, 이를 해결하기 위해 확률 모델이라는 것을 설계를 하고 문제를 해결합니다. 확률 모델을 설계 할 때 고려되어야 할 사항이 모델을 설계할때 들어갈 변수들 간의 관계가 확실하여 예측을 정확하게 할 수 있어 해를 찾을 수 있는 경우가 있는 반면에 변수간의 관계가 불명확하여 해를 찾기 힘들어 해에 근접한 수를 찾는 경우가 있습니다.</div> <div><br></div> <div>예를들어 바둑의 경우, 내가 어떤 수를 놓으려고 할 때, 다음 상대방의 수에 따라 그 다음 자신의 수를 계산하는 방식이기 때문에 위의 확률 모델 종류의 후자라고 할 수 있습니다. </div> <div><br></div> <div>보통 후자의 경우, 수치적 난수를 이용하여 시뮬레이션을 통해 특정 수에서 수렴이 되는 수를 찾는 방식을 사용합니다. 이런 확률 모델의 시뮬레이션에서 일반적으로 사용되는 방식이 몬테 카를로 시뮬레이션 입니다.</div> <div><br></div> <div>몬테 카를로 방식을 이용하여 원주율 (파이)를 구하는 예를 들어 봄으로써 몬테 카를로의 동작 원리를 이해해보도록 하겠습니다. XD</div> <div><br></div> <div>우리가 처음에 원주율을 구하는 방식을 배울 때 원 지름에 대한 원의 둘레의 길이로 배웁니다. 하지만 여기서는 몬테카를로를 이용하여 확률적으로 원주율을 구하려고 합니다.</div> <div><br></div> <div>다음과 같이 한 변의 길이가 1인 정사각형과 그 안에 반지름이 0.5인 원이 있다고 가정합니다.</div> <div><br></div> <div><div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201603/1458306141mWjYnvAtBOUdSJ.png" width="394" height="359" alt="example.png" style="border:none;"></div><br></div> <div><br></div> <div>정사각형의 넓이 = 1 * 1 = 1</div> <div>원 넓이 = (1 / 2) * (1 / 2) * 원주율 = 원주율 / 4</div> <div><br></div> <div>원 넓이 / 정사각형 넓이 = (원주율 / 4) / 1</div> <div><br></div> <div>따라서, 원주율 = (원 넓이 * 4) / 정사각형 넓이 가 됩니다.</div> <div><br></div> <div>우리가 하려고 하는것은 이 안에 점을 무작위 하게 막 찍습니다. 중요한것은 무작위성의 높을 수록 연산 결과를 더욱 정확해 집니다. :D</div> <div><br></div> <div>확률적인 방식에 의해 찍인 원 안에 있는 점의 수와 정사각형 안에 있는 점의 수 (이는 전체 점 의 수와 같습니다) 로 위의 원주율을 다음과 같이 계산할 수 있습니다.</div> <div><br></div> <div>원주율 = (원 넓이 * 4) / 정사각형 넓이 <span style="color:#252525;font-family:sans-serif;font-size:14px;line-height:22.4px;">≒</span><span style="font-size:9pt;line-height:1.5;"> (원 안의 점의 수 * 4) / 정사각형 안의 점의 수</span></div> <div><br></div> <div>아래는 python으로 만든 몬테 카를로 기법을 이용한 원주율 계산 시뮬레이션 코드 입니다.</div> <div><br></div> <div><div class="colorscripter-code" style="color:#010101;overflow:auto;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> <table class="colorscripter-code-table" style="margin:0px;padding:0px;border:none;background-color:#fafafa;" cellspacing="0" cellpadding="0"><tbody><tr><td style="padding:6px;border-right-width:2px;border-right-style:solid;border-right-color:#e5e5e5;"> <div style="margin:0px;padding:0px;text-align:right;color:#666666;line-height:130%;"> <div style="line-height:130%;">1</div> <div style="line-height:130%;">2</div> <div style="line-height:130%;">3</div> <div style="line-height:130%;">4</div> <div style="line-height:130%;">5</div> <div style="line-height:130%;">6</div> <div style="line-height:130%;">7</div> <div style="line-height:130%;">8</div> <div style="line-height:130%;">9</div> <div style="line-height:130%;">10</div> <div style="line-height:130%;">11</div> <div style="line-height:130%;">12</div> <div style="line-height:130%;">13</div> <div style="line-height:130%;">14</div> <div style="line-height:130%;">15</div> <div style="line-height:130%;">16</div> <div style="line-height:130%;">17</div> <div style="line-height:130%;">18</div> <div style="line-height:130%;">19</div> <div style="line-height:130%;">20</div> <div style="line-height:130%;">21</div> <div style="line-height:130%;">22</div></div></td> <td style="padding:6px 0px;"> <div style="margin:0px;padding:0px;color:#010101;line-height:130%;"> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#a71d5d;">import</span> random</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"> </div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">radius         <span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">1 / 2</span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">cnt_circle     <span style="color:#0086b3;"></span><span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">0</span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">cnt_square     <span style="color:#0086b3;"></span><span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">0</span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"> </div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">idx          <span style="color:#0086b3;"></span><span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">0</span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">cnt_iter     <span style="color:#0086b3;"></span><span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">10000000</span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"> </div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#a71d5d;">while</span> idx <span style="color:#0086b3;"></span><span style="color:#a71d5d;"><</span> cnt_iter:</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    rnd_x <span style="color:#0086b3;"></span><span style="color:#a71d5d;">=</span> random.random()</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    rnd_y <span style="color:#0086b3;"></span><span style="color:#a71d5d;">=</span> random.random()</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"> </div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    <span style="color:#a71d5d;">if</span> (rnd_x <span style="color:#0086b3;"></span><span style="color:#a71d5d;">-</span> radius)<span style="color:#0086b3;"></span><span style="color:#a71d5d;">*</span><span style="color:#0086b3;"></span><span style="color:#a71d5d;">*</span><span style="color:#0099cc;">2</span> <span style="color:#0086b3;"></span><span style="color:#a71d5d;">+</span> (rnd_y <span style="color:#0086b3;"></span><span style="color:#a71d5d;">-</span> radius)<span style="color:#0086b3;"></span><span style="color:#a71d5d;">*</span><span style="color:#0086b3;"></span><span style="color:#a71d5d;">*</span><span style="color:#0099cc;">2</span> <span style="color:#0086b3;"></span><span style="color:#a71d5d;"><</span> (radius<span style="line-height:15.6px;color:#a71d5d;">*</span><span style="line-height:15.6px;color:#0099cc;">2</span>)<span style="color:#a71d5d;">*</span><span style="color:#0086b3;"></span><span style="color:#a71d5d;">*</span><span style="color:#0099cc;">2</span>:</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">        cnt_circle <span style="color:#0086b3;"></span><span style="color:#a71d5d;">+</span><span style="color:#0086b3;"></span><span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">1</span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"> </div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    cnt_square <span style="color:#0086b3;"></span><span style="color:#a71d5d;">+</span><span style="color:#0086b3;"></span><span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">1</span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;">    idx <span style="color:#0086b3;"></span><span style="color:#a71d5d;">+</span><span style="color:#0086b3;"></span><span style="color:#a71d5d;">=</span> <span style="color:#0099cc;">1</span></div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"> </div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#066de2;">print</span> <span style="color:#63a35c;">"The circle count is : %d"</span> % (cnt_circle)</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#066de2;">print</span> <span style="color:#63a35c;">"The square count is : %d"</span> % (cnt_square)</div> <div style="padding:0px 6px;white-space:pre;line-height:130%;"><span style="color:#066de2;">print</span> <span style="color:#63a35c;">"The ratio of (4 * circle) / square = pie : %f"</span> % ( (<span style="color:#0099cc;">4.</span><span style="color:#0099cc;">0</span> <span style="color:#0086b3;"></span><span style="color:#a71d5d;">*</span>cnt_circle) <span style="color:#0086b3;"></span><span style="color:#a71d5d;">/</span> cnt_square )</div></div></td> <td style="vertical-align:bottom;padding:0px 2px 4px 0px;"><a target="_blank" href="http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:#ffffff;"><span style="font-size:9px;padding:1px;background-color:#e5e5e5;">cs</span></a></td></tr></tbody></table></div></div> <div><br></div> <div>결과는 다음과 같습니다.</div> <div><br></div> <div>       100개의 무작위한 점을 찍는 경우, The ratio of (4 * circle) / square = pie : 2.920000</div> <div>     1000개의 무작위한 점을 찍는 경우, The ratio of (4 * circle) / square = pie : 3.176000</div> <div>   10000개의 무작위한 점을 찍는 경우, The ratio of (4 * circle) / square = pie : 3.152800</div> <div>  100000개의 무작위한 점을 찍는 경우, The ratio of (4 * circle) / square = pie : 3.136080</div> <div> 1000000개의 무작위한 점을 찍는 경우, The ratio of (4 * circle) / square = pie : 3.141328</div> <div>10000000개의 무작위한 점을 찍는 경우, The ratio of (4 * circle) / square = pie : 3.141556</div> <div><br></div> <div>짜잔! 이런식으로 확률적인 방법을 통해 원주율을 계산을 할 수 있습니다.</div> <div><br></div> <div>더욱 정확히 계산을 원한다면 특정 소수점 밑으로 수렴될때까지 반복을 더 하시면 됩니다. 위에서도 썻지만 결과는 랜덤성에 굉장히 의존을 하고 있기 때문에 좋은 랜덤 함수를 사용해야 합니다 :)</div> <div><br></div> <div>여기까지 몬테 카를로 기법을 이용하여 확률적으로 원주율을 계산하는 방법을 알아봣습니다. </div> <div><br></div> <div>추가적으로 제가 예전에 해킹 대회 문제로 풀었던 것 중에 몬테 카를로 시뮬레이션을 사용했던 적이 있었는데, 그 때의 문제는 블랙잭 이였습니다.</div> <div><br></div> <div>"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." </div> <div><br></div> <div>이라는 문제였는데, 블랙잭을 할 때 제 손패가 Ace와 2를 갖고 있고 딜러가 3이 펼쳐져 있고 한장은 안보이는 게임일 때 내가 바로 stop 할 경우 이길 확률과 계속 패를 받는 경우 이길 확률을 계산하여 어떤 전략이 더 이길 확률이 높은지 찾는 문제였습니다.</div> <div><br></div> <div>이 경우에도 몬테 카를로 기법을 사용하여 해결 했는데, 관련 내용과 소스 코드는 제 블로그에 올려 두었으니 관심 있으신분은 한번 보시면 좋을것 같습니다. ( <a target="_blank" href="http://hackability.kr/entry/2015TrendMicroCTF-Programming-500-BlackJack" target="_blank">http://hackability.kr/entry/2015TrendMicroCTF-Programming-500-BlackJack</a> )</div> <div><br></div> <div><span style="font-size:9pt;line-height:1.5;">즐거운 주말 되세요 ^^</span></div>