前言

昨天介紹完使用動態規劃，計算價值函數的方法，今天我們要進入使用蒙地卡羅，計算價值函數的方法。

蒙地卡羅

介紹

蒙地卡羅 是一個很漂亮的地方 是一種使用大量模擬測試，逼近數值的方法。相較於用在估計價值函數，蒙地卡羅更常見的應用是找「」或 「積分」。以下我們將說明估計 的流程，說明蒙地卡羅方法的思路，在進入估計價值函數的部份。

估計

我們都知道 的定義是「圓周與直徑的比率」，但我們不知道圓周，因此要求這個數值需要一些其他技巧，例如估計面積：

• 估計面積思路
  想像我們現在有一個直徑兩公分圓，並把圓放在一個邊長兩公分的正方形內，如下圖所示：
  

  然後我們隨機在正方形中產生一個點，看這個點在圓的內部，還是圓的外部。
  or

  接著，只要我們重複觀察點在圓內還是圓外，就可以推估圓佔整個正方形面積的比率。由於我們知道正方形的面積，因此可以透過比率得知圓的面積。

  透過圓面積公式： Area 即可得知 。

• 估計實作
  在實作上為了方便，我們只計算 1/4 圓，在將結果乘上 4 倍即可。首先，產生隨機的點

  def GenDataPair():
    '''
    To generate the data pair (x,y) with the value between 0 and 1.
     Output
      -dta: The data pair (x, y)
    '''
    dta = [random.uniform(0,1), random.uniform(0,1)]
    return dta
  

  接著，重複判斷點落在圓內還是圓外，直到抵達中止條件。

  def SimProc(times):
    '''
    This function use to simulate whether data pair (x, y) is inside the circle with radius is 1.
     Input
      -times: Executing times in one simulation.
     Output
      -count: Counting how many data pair (x, y) is inside the circle.
    '''
    count = 0
    now = 0
    while now<times:
        x, y = GenDataPair()
        if (pow(x,2)+pow(y,2)) < 1:
            count = count+1
        now = now+1
    return count
  

  最後，我們就可以產生估計的

  def SimPI(scale, order):
    '''
    This function is used to estimate the value of pi
     Input
      -scale & order: The parameter of executing times
     Output
      -est_pi: The estimated value of pi
    '''
    times = scale*pow(10, order)+1
    count = SimProc(times)
    est_pi = (count/times)*4
    return est_pi
  

  根據個人測試，重複一千萬次，得到的估計值為：3.1414828858517114

除了讓產生的點位增加，增進單次估計的結果。也可以考慮多做幾次估計，取估計的平均值來增進估計結果，有興趣可以參考 GitHub 。
至此，我想大家可以稍微明白蒙地卡羅中，「大量模擬測試」的意思是什麼了。明天會介紹使用蒙地卡羅估計價值函數。