ModelOff攻略 － 問題篇（3）

　　以下要分析的是2014年第1輪的題目 －Snakes and Ladders。

命題目的

　　本題的目的在於利用簡單的遊戲與競賽來練習蒙地卡羅模擬法（Monte Carlo Simulation）的模型建立。由於蒙地卡羅方法（Monte Carlo Method）是一種以機率統計理論（隨機數）來解決數值計算的重要技巧，該方法在財務工程、總體經濟學及統計物理學上皆有廣泛的應用，在上述領域的工作者應該都要能夠敏銳的判斷出何時以及如何將問題轉換成以蒙地卡羅方法描述。

　　因此，本題主要希望作答者能夠在解題的過程中理解如何將一個機率問題敘述以隨機數表示，找出能夠代表其特徵的模式，並掌握從該模式遞迴求出結果的方法。

　　另外，雖然蒙地卡羅方法的優點是對於計算過於複雜而難以得到解析解或者根本沒有解析解的問題，該方法能夠有效的求出數值解，但其缺點是計算成本高，以本題為例，其時間複雜度應為O(n^2)。

題目資訊

　　題目描述如下，作答者模擬一場遊戲，在35格的棋盤上進行，起點為0，終點為34，遊戲規則以骰子點數為步數並依數字順序前進，在停止的格子上，若遇到樓梯底端則爬升至頂端，若遇到蛇頭則下滑至蛇尾。

　　遊戲分為單人或雙人進行，在雙人參與遊戲的情境下，Player 1設定為先手，Player 2設定為後手。再者，題目要求作答者以模擬5000回遊戲的結果來回答問題，並重複進行幾次該5000回的模擬以減少因誤差造成的誤判，因此可以觀察出答案應該都是由統計該結果的分布模式而得到。

　　另外，由問題的敘述可明顯看出此遊戲先手具有優勢，並可觀察到改變規則將影響遊戲參與者的勝率。

　　延伸： 除了學術上的應用外，以蒙地卡羅方法應該也能夠模擬或預測其他棋類遊戲的競賽結果，例如圍棋先手的勝率。不知道深藍（Deep Blue）模擬西洋棋遊戲的棋譜時還要再配合哪些演算法?

　　分享兩則有趣的文章：

• The Electronic Holy War
• 電腦進軍圍棋界