寫在前面：
蒙特卡羅這個(gè)詞本身是賭城，而蒙特卡洛方法中確實(shí)體現(xiàn)出了賭博的隨機(jī)性、不確定性。筆者在這想討論的是基于蒙特卡羅的樹搜索方法，該方法可被應(yīng)用于圍棋、五子棋等博弈類游戲，通俗地解釋，蒙特卡羅樹搜索是一種
隨機(jī)算法，在有限時(shí)間里，只能說(shuō)是盡可能地去逼近最優(yōu)解，但不一定能找到。
知乎上有個(gè)例子說(shuō)是：假如筐里有100個(gè)蘋果，讓我每次閉眼拿1個(gè)，挑出最大的。于是我隨機(jī)拿1個(gè)，再隨機(jī)拿1個(gè)跟它比，留下大的，再隨機(jī)拿1個(gè)……我每拿一次，留下的蘋果都至少不比上次的小。拿的次數(shù)越多，挑出的蘋果就越大，但我除非拿100次，否則無(wú)法肯定挑出了最大的。這個(gè)挑蘋果的算法，就屬于蒙特卡羅算法——盡量找好的，但不保證是最好的。
正文：
????還是先拿老虎機(jī)的例子來(lái)說(shuō)事，假設(shè)你面前有兩臺(tái)老虎機(jī)，告訴你兩臺(tái)的勝率分別是0.8、0.6，哪一臺(tái)的勝率比較高呢？
????再假設(shè)兩臺(tái)老虎機(jī)各試驗(yàn)了5次后，并發(fā)現(xiàn)5次內(nèi)第一臺(tái)的的勝率是0.8、第二臺(tái)是0.6，可是此時(shí)就作出第一臺(tái)老虎機(jī)勝率高的判斷是不正確的，在試驗(yàn)次數(shù)太少（只有5次）的情況下，無(wú)法斷定哪臺(tái)的老虎機(jī)勝率高，而當(dāng)試驗(yàn)次數(shù)足夠多時(shí)，才能夠做出準(zhǔn)確的判斷，但同時(shí)也付出了相應(yīng)的時(shí)間代價(jià)。
????接著，我們把情景移交到五子棋上邊來(lái)，我們拿下面的圖來(lái)做分析：
????圖中，每一個(gè)節(jié)點(diǎn)代表某種棋局情況，圈里的斜杠左邊的數(shù)字代表電腦在該節(jié)點(diǎn)下勝利的次數(shù)，斜杠右邊的數(shù)字代表該節(jié)點(diǎn)被訪問的次數(shù)。如12/21表示該節(jié)點(diǎn)下勝利了12次，總共訪問過21次。
????按照流程圖，該蒙特卡羅樹搜索有4個(gè)步驟：
-
選擇（Selection）：從根節(jié)點(diǎn)走起，由于第二行已經(jīng)沒有可拓展的節(jié)點(diǎn)（如有則需要把當(dāng)前可拓展的點(diǎn)窮盡完），所以根據(jù)UCT（上限置信區(qū)間算法）如下圖，
????其中x是當(dāng)前結(jié)點(diǎn)的勝率估計(jì)，N是節(jié)點(diǎn)的訪問次數(shù)，C是一個(gè)常數(shù)。C大就偏向于BFS，C小就偏向于DFS。此外，由于是子節(jié)點(diǎn)的訪問次數(shù)作分母，所以當(dāng)該子節(jié)點(diǎn)的訪問次數(shù)較小時(shí)，反而會(huì)得到更大的score（即訪問次數(shù)少的更值得探索）
????逐步代入公式，得出：
????7/10的score為0.7+0.55C
????5/8的score為0.625+0.62C
????0/3的score為0+1.00C
????以此類推，最終選擇了第4行的3/3節(jié)點(diǎn)，由于該節(jié)點(diǎn)已經(jīng)沒有了子節(jié)點(diǎn)，但同時(shí)五子棋游戲還沒結(jié)束（即不是終止節(jié)點(diǎn)），所以進(jìn)入步驟2。 拓展（Expansion）：在Selection步驟中我們已經(jīng)選擇了3/3節(jié)點(diǎn)，現(xiàn)在要做的就是在3/3節(jié)點(diǎn)下再生成一個(gè)子節(jié)點(diǎn)，暫且命名為0/0，代表著一個(gè)新的，沒有試過的下法，或者說(shuō)一個(gè)棋局局面。
模擬（Simulation）：在這步，我們需要判定這個(gè)節(jié)點(diǎn)是好的還是壞的，可是由于此時(shí)還沒到終局，所以我們需要一種快速判定的方法。這篇文章的方法是隨機(jī)下子（夠快吧?。。醋笥译S機(jī)下子互博，一直到終局，以此判定該節(jié)點(diǎn)的好壞。這樣的話，評(píng)估的準(zhǔn)確性理所當(dāng)然就會(huì)降低（畢竟是隨機(jī)下出來(lái)的），但勝在快，當(dāng)次數(shù)足夠多的時(shí)候，模擬結(jié)果也會(huì)慢慢變得可靠。（不知道算不算是暴力窮舉算法巧用的一種）
讀者可以作如下思考：即使一開始計(jì)算機(jī)把一個(gè)不好的走子誤以為是好的走法，隨著它對(duì)這種走法的慢慢挖掘，這種走法的評(píng)估也會(huì)慢慢變壞，最后計(jì)算機(jī)就會(huì)放棄這種走法，從而讓自己能夠選擇其他更好的走法。
4.回溯（Backpropagation）：在這步，由于有新的節(jié)點(diǎn)信息加入進(jìn)來(lái)，所以需要更新我們現(xiàn)有的博弈樹。這里我們假設(shè)上步的結(jié)果是輸，所以0/0更新為0/1，并在該節(jié)點(diǎn)的基礎(chǔ)上，一步一步向上更新其他節(jié)點(diǎn)。這里還有一個(gè)小細(xì)節(jié)就是博弈游戲都是你走一步我走一步，所以回溯的時(shí)候應(yīng)該把勝率變?yōu)樨?fù)數(shù)，這樣的話，當(dāng)切換走子方時(shí)，對(duì)方的勝率的負(fù)值就可以看作是自己的勝率，越接近零就越大。
偽代碼圖：
寫在最后：
????emmmmmm，到這里也算是我對(duì)蒙特卡羅樹搜索的一個(gè)復(fù)習(xí)了，借鑒了一些網(wǎng)上現(xiàn)有的教程，但主要都是自己的話及理解，如果讀者結(jié)合解釋來(lái)看偽代碼的話也是不難懂的，至于真代碼。。。?？次沂裁磿r(shí)候有空就用C++寫一個(gè)五子棋程序及實(shí)現(xiàn)蒙特卡羅算法咯。。。。記得一開始自己用Alpha-Beta剪枝算法來(lái)寫五子棋AI，結(jié)果由于評(píng)估那個(gè)環(huán)節(jié)做的不好，所以最后的AI蠻zz的。不管啦不管啦，如果說(shuō)蒙特卡羅有哪里好的話，也是沒有評(píng)估這個(gè)環(huán)節(jié)（因?yàn)樗约涸u(píng)估了），以及能夠限定它的思考時(shí)間，這點(diǎn)在限時(shí)博弈里還是很好的。
