寫(xiě)在前面：
蒙特卡羅這個(gè)詞本身是賭城鳖敷，而蒙特卡洛方法中確實(shí)體現(xiàn)出了賭博的隨機(jī)性政恍、不確定性敬辣。筆者在這想討論的是基于蒙特卡羅的樹(shù)搜索方法渊抽，該方法可被應(yīng)用于圍棋蟆豫、五子棋等博弈類游戲，通俗地解釋懒闷，蒙特卡羅樹(shù)搜索是一種
隨機(jī)算法十减，在有限時(shí)間里栈幸，只能說(shuō)是盡可能地去逼近最優(yōu)解，但不一定能找到帮辟。
知乎上有個(gè)例子說(shuō)是：假如筐里有100個(gè)蘋(píng)果速址，讓我每次閉眼拿1個(gè)，挑出最大的由驹。于是我隨機(jī)拿1個(gè)壳繁，再隨機(jī)拿1個(gè)跟它比，留下大的荔棉，再隨機(jī)拿1個(gè)……我每拿一次闹炉，留下的蘋(píng)果都至少不比上次的小。拿的次數(shù)越多润樱，挑出的蘋(píng)果就越大渣触，但我除非拿100次，否則無(wú)法肯定挑出了最大的壹若。這個(gè)挑蘋(píng)果的算法嗅钻，就屬于蒙特卡羅算法——盡量找好的，但不保證是最好的店展。
正文：
????還是先拿老虎機(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)被訪問(wèn)的次數(shù)。如12/21表示該節(jié)點(diǎn)下勝利了12次醋火，總共訪問(wèn)過(guò)21次悠汽。
????按照流程圖箱吕，該蒙特卡羅樹(shù)搜索有4個(gè)步驟：
-
選擇（Selection）：從根節(jié)點(diǎn)走起，由于第二行已經(jīng)沒(méi)有可拓展的節(jié)點(diǎn)（如有則需要把當(dāng)前可拓展的點(diǎn)窮盡完）柿冲，所以根據(jù)UCT（上限置信區(qū)間算法）如下圖茬高，
????其中x是當(dāng)前結(jié)點(diǎn)的勝率估計(jì)，N是節(jié)點(diǎn)的訪問(wèn)次數(shù)假抄，C是一個(gè)常數(shù)怎栽。C大就偏向于BFS，C小就偏向于DFS宿饱。此外熏瞄，由于是子節(jié)點(diǎn)的訪問(wèn)次數(shù)作分母，所以當(dāng)該子節(jié)點(diǎn)的訪問(wèn)次數(shù)較小時(shí)谬以，反而會(huì)得到更大的score（即訪問(wèn)次數(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)沒(méi)有了子節(jié)點(diǎn)邮丰，但同時(shí)五子棋游戲還沒(méi)結(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è)新的斗蒋，沒(méi)有試過(guò)的下法，或者說(shuō)一個(gè)棋局局面捧书。
模擬（Simulation）：在這步吹泡，我們需要判定這個(gè)節(jié)點(diǎn)是好的還是壞的骤星，可是由于此時(shí)還沒(méi)到終局经瓷，所以我們需要一種快速判定的方法。這篇文章的方法是隨機(jī)下子（夠快吧６茨选Ｓ咚薄），即左右隨機(jī)下子互博队贱，一直到終局色冀，以此判定該節(jié)點(diǎn)的好壞。這樣的話柱嫌，評(píng)估的準(zhǔn)確性理所當(dāng)然就會(huì)降低（畢竟是隨機(jī)下出來(lái)的）锋恬，但勝在快，當(dāng)次數(shù)足夠多的時(shí)候编丘，模擬結(jié)果也會(huì)慢慢變得可靠与学。（不知道算不算是暴力窮舉算法巧用的一種）
讀者可以作如下思考：即使一開(kāi)始計(jì)算機(jī)把一個(gè)不好的走子誤以為是好的走法彤悔，隨著它對(duì)這種走法的慢慢挖掘，這種走法的評(píng)估也會(huì)慢慢變壞索守，最后計(jì)算機(jī)就會(huì)放棄這種走法晕窑，從而讓自己能夠選擇其他更好的走法。
4.回溯（Backpropagation）：在這步卵佛，由于有新的節(jié)點(diǎn)信息加入進(jìn)來(lái)杨赤，所以需要更新我們現(xiàn)有的博弈樹(shù)。這里我們假設(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ù)值就可以看作是自己的勝率，越接近零就越大枫匾。
偽代碼圖：
寫(xiě)在最后：
????emmmmmm架诞，到這里也算是我對(duì)蒙特卡羅樹(shù)搜索的一個(gè)復(fù)習(xí)了，借鑒了一些網(wǎng)上現(xiàn)有的教程干茉，但主要都是自己的話及理解谴忧，如果讀者結(jié)合解釋來(lái)看偽代碼的話也是不難懂的，至于真代碼角虫。沾谓。。戳鹅【唬看我什么時(shí)候有空就用C++寫(xiě)一個(gè)五子棋程序及實(shí)現(xiàn)蒙特卡羅算法咯。枫虏。妇穴。。記得一開(kāi)始自己用Alpha-Beta剪枝算法來(lái)寫(xiě)五子棋AI隶债，結(jié)果由于評(píng)估那個(gè)環(huán)節(jié)做的不好腾它，所以最后的AI蠻zz的。不管啦不管啦死讹，如果說(shuō)蒙特卡羅有哪里好的話瞒滴，也是沒(méi)有評(píng)估這個(gè)環(huán)節(jié)（因?yàn)樗约涸u(píng)估了），以及能夠限定它的思考時(shí)間赞警，這點(diǎn)在限時(shí)博弈里還是很好的妓忍。
