Day15 Monte Carlo Method
===
## Monte Carlo Method
Monte Carlo Method（蒙地卡羅方法）是一種基於隨機取樣的統計技術，通常用來解決複雜的數學或計算問題，尤其是在模擬和優化問題中應用廣泛。
採用隨機抽樣的方式，以隨機事件出現的頻率估計其機率，當樣本數愈大結果會愈準確。因為電腦的出現，可以幫我們實現大量且快速的隨機抽樣或模擬，藉此我們可以得到問題的近似解。

### 圓周率
以計算圓周率π為例，讓電腦隨機生成n個在X軸座標且Y軸座標皆在0~1之間的點，將落在如圖2-1中紅色扇形範圍裡點的數量設為m。**假設這些點分布的夠均勻的話那m與n的比例應該會接近於扇形與方形的面積比例。**


圖片來自維基百科

### 面試題目
有個我非常喜歡的youtuber：[Joma Tech](https://www.youtube.com/@jomakaze) 雖然他一年多沒更新影片了，估計是沒了。
我覺得他是被資工耽誤的演員，很多影片都蠻好笑的，打發時間可以去看看，其中有一部是[Can you solve my favorite interview question? (math + cs)](https://youtu.be/pvimAM_SLic?si=pVRen6Ch9euNU_5e)，剛好介紹到了Monte Carlo Method，沒想到居然還能被出成一道面試題。

> 題目：
> 給你一個隨機數生成器（random function），這個隨機數生成器會產生從0到1之間的數字，然後......請計算圓周率。

沒有學過的人應該聽到都是一愣，我到底聽了什麼?
乍聽之下有點像是什麼一隻雞有兩隻腳、一隻牛有四隻腳，現在有三隻雞跟兩隻牛，請問...一隻豬賣多少錢的這種鬼問題。
這邊我就不寫了，大家可以自行嘗試實作看看，如果哪天真的面試被問到就賺到了，畢竟Joma之前是Google員工，說不定這是什麼大廠的面試題也說不定。

## 電腦對局中的應用
因為主題是電腦對局，所以其他領域的應用我就不提了，在 Day6 的 Evaluation Function 中提到，設計審局函數的一個常見方法就是**模擬法**，即通過大量模擬對局來評估盤面狀況，這就非常適合使用 Monte Carlo Method，以下我們就來看一些實例。

### Monte Carlo Tree Search
Monte Carlo Method應用於對局樹上，就是非常有名的Monte Carlo Tree Search，這邊內容比較多，會拆成兩篇留到明後天介紹。

### 圍棋
有個圍棋知名的開源軟體[Sabaki](https://sabaki.yichuanshen.de/)，用Monte Carlo Method來判斷棋盤上的死棋，他通過模擬到棋局結束(預設模擬100次)，來評估棋盤上的棋子是死的還是活的。
就是統計這100次模擬中，每個點最終是屬於黑多一點還是白多一點。
但是他有地方寫錯了，判斷眼位的邏輯有點問題，我兩年半前有發issue給他，但他好像沒有想改。
如下圖，右下角的白棋只有一眼，是死棋才對，但可以看到其他地方的黑白領地與死棋都評估的還蠻不錯的。


### 蜜月橋牌
不懂橋牌的人可以先看一下[橋牌規則](https://zh.wikipedia.org/zh-tw/%E6%A9%8B%E7%89%8C)，蜜月橋牌其實也差不多。
在蜜月橋牌的叫牌階段，要評估自己的手牌能喊到什麼線位，可以把所有牌型組合展開去評估自身牌力，一開始得到13張牌後，對手可能的牌型是由剩下的39張選出13張的組合，這樣是${C\ }_{13}^{39}$共8122425444種組合。
如果能把所有情況一一列舉出來，分別用黑桃、紅心、方塊、梅花當作王牌，去計算每種情況能夠得到多少磴，這樣就能得到目前手牌的牌力平均值，這個分數會落在0~13之間。
顯然我們在有限的時間內沒辦法列舉所有的可能，所以使用Monte Carlo Method抽樣去做模擬，**比起展開8122425444種組合，其實用100次的模擬就能得到很不錯的評估值了。**

## Reference
* [蒙地卡羅法](https://zh.wikipedia.org/zh-tw/%E8%92%99%E5%9C%B0%E5%8D%A1%E7%BE%85%E6%96%B9%E6%B3%95)
* [蜜月橋牌程式開發及殘局庫的建立](https://etds.lib.ntnu.edu.tw/thesis/detail/fd5112c14f57aff625d2fa6e1b1b95ab/)