蒙特卡洛樹搜索實驗設計

摘要：蒙特卡洛樹搜索是實現智能博弈程序的關鍵技術，是人工智能課程的重要內容。本文面向人工智能課程實踐教學，針對現有教材偏重理論介紹缺乏實踐引導的問題，設計了以黑白棋為例的蒙特卡洛樹搜索實驗，幫助學生理解蒙特卡洛樹搜索的主要流程與設計原理。本文首先運用圖解方式直觀展示蒙特卡洛樹的創建與擴展過程；其次引入算法的模塊化實現方法；最后，將蒙特卡洛樹搜索應用于智能黑白棋程序設計，通過圖形界面展示搜索結果，實現交互式人機對弈。教學實踐表明，通過動手實現基于蒙特卡洛樹搜索的智能黑白棋程序，能夠加深學生對算法的理解，提升學生創新實踐能力。

關鍵詞：人工智能；蒙特卡洛樹搜索；黑白棋；AlphaGo

中圖分類號：TP391.4

蒙特卡洛樹搜索（MonteCarloTreeSearch，MCTS）是一種用于決策過程的搜索算法，其基本目標是給定問題的一個狀態，選擇該狀態下一個最優的行動方案。蒙特卡洛書搜索結合了隨機模擬和樹搜索的優點，通過模擬來評估不同的狀態的優劣，從而找到最優的行動方案。蒙特卡洛樹搜索于2006年被提出［1］，初始應用于圍棋游戲。隨后，谷歌公司DeepMind團隊將其與深度學習技術結合，開發了智能系統AlphaGo［2］，戰勝了頂尖職業圍棋選手，成為人工智能領域里程碑事件之一。蒙特卡洛樹搜索是一個應用非常廣泛的博弈算法，除了用于雙人零和博弈問題（例如圍棋、象棋），也應用于路徑規劃等重要任務［3］。

蒙特卡洛樹搜索是人工智能課程的重要內容，對學生掌握智能程序設計方法具有十分重要的作用［4-6］。然而，現有的大部分人工智能教材依然將早期的博弈搜索技術（極小極大搜索）作為課程的教學重點，缺乏對蒙特卡洛樹搜索等新型博弈搜索技術的講解。部分教材即使涉及蒙特卡洛樹搜索，也只是蜻蜓點水，對算法原理的描述不夠詳細，同時缺乏教學案例與實驗案例支撐。本文的主要目的是實現人工智能課程博弈搜索知識點的教學重點從早期的極小極大搜索到目前主流的蒙特卡洛樹搜索的轉移，隨時代發展更新人工智能課程教學內容，探討如何設計可視化的蒙特卡洛樹搜索實驗，促進學生對算法的理解，提升智能程序設計水平，提升實踐教學效果。

本文的主要內容和結構安排如下：第1節主要介紹蒙特卡洛樹搜索的基本流程與原理；第2節設計基于黑白棋的蒙特卡洛樹搜索實驗；第3節對實驗結果進行展示；第4節對本文進行總結。

1蒙特卡洛樹搜索理論基礎

1997年，IBM公司設計的深藍程序戰勝當時的國際象棋世界冠軍加里·卡斯帕洛夫，成為計算機智能博弈程序的標志性事件之一。深藍用到的主要技術包括極小極大搜索，每秒能夠探查2億個位置，使用了非常復雜的評估函數和一些未公開的方法將某些搜索分支延伸至40層［7］。自此之后，極小極大搜索成為人工智能課程博弈搜索部分的重要知識點。極小極大搜索是基于博弈樹的搜索算法，它使用博弈樹表示一個游戲。博弈樹中每個結點都代表一個狀態，根結e5c1d78284320fe2a70c5d099b4908963712c82cd7db9063336cda788aeebe2c點表示初始狀態，葉子結點表示終止狀態。從一個結點移動一步，將會到達它的子結點，一個結點包含子結點的數目稱為分支因子。極小極大搜索并未顯式構造整棵博弈樹，而是通過遞歸的方式計算根結點的每個子結點的收益，從而選擇最佳行動方案。對于具有很大分支因子的游戲，博弈樹非常巨大，無法有效進行搜索。此時，極小極大搜索需要限定搜索深度。我們無法保證在指定深度處的結點都是終止結點，因此需要一個函數來評估非終止狀態的局勢。然而，評估函數設計非常困難，通常需要借助領域專家經驗。

與極小極大搜索相同，蒙特卡洛樹搜索也是基于博弈樹的搜索算法，不同點在于蒙特卡洛樹搜索顯式存儲博弈樹。蒙特卡洛樹搜索采用迭代構建的思想，從單個根結點開始，不斷擴充博弈樹，直至用完限定的搜索時間，再根據構建的博弈樹制訂當前最佳的行動方案。對于非葉子結點，蒙特卡洛樹搜索不依賴于評估函數計算結點收益，而是通過多次模擬博弈，根據模擬結果估算結點收益。以圍棋為例，在某個特定盤面s情況下，進行n次對局，如果統計出黑棋贏得多，說明盤面s對黑棋比較有利。通過模擬對弈的方式評估結點收益，計算量大，評估次數有限。因此，蒙特卡洛樹搜索提供了一種選擇機制，盡量選擇博弈樹中比較有潛力的結點進行模擬，從而使得博弈樹在“較好”的策略上“生長”。

蒙特卡洛樹搜索每一輪迭代都是從根結點出發，順序執行“選擇”—“擴展”—“模擬”—“反向傳播”四個步驟，不斷擴充博弈樹。圖1展示了蒙特卡洛樹搜索一輪迭代的執行示例，接下來詳細介紹每一個步驟。

1.1選擇

從根結點出發，自上而下迭代執行子結點選擇策略，直至到達一個可擴展的結點。一個結點是可擴展的，當且僅當其所包含的狀態是非終止狀態，且還有未擴展的子結點。選擇策略的基本思想是讓博弈樹向最優的方向擴展，也就是要選擇一個盡量“有潛力”的樹結點。有潛力的結點可以由兩方面因素進行評估，一個是勝率高，另一個是被考察的次數少。勝率高的結點意味著最后贏棋的概率較大，應該多花精力分析其后續走法。被考察次數少意味著該結點尚未經過充分研究，有成為黑馬的可能。下表綜合兩個方面的因素總結了結點的潛力。

假設當前所在樹結點為S0，S0具有b個子結點，分別記為S1，S2，…，Sb。蒙特卡洛樹通常用上置信區間（UpperConfidenceBound，UCB）公式對每個子結點的潛力進行量化評估，從而計算結點的“潛力”。第i個子結點Si的“潛力”具體計算公式如下：

UCB（Si）=tini+clnNni

其中，ti表示從子結點Si所含狀態出發后續取勝的次數（或者收益），ni表示結點Si的訪問次數，c是一個維護探索與利用平衡的參數，在實際應用中憑經驗進行選擇，N表示當前結點S0的訪問次數，等于所有ni之和。公式等號右側第一項代表了結點的勝率指標，第二項代表了結點的訪問次數指標，參數c數值越大，擴展過程越照顧訪問次數較少的結點。

1.2擴展

根據當前可執行的行動（可能的落子方法），向選定的結點上添加一個子結點擴展搜索樹，同時選擇該子結點。

1.3模擬

以新擴展的子結點作為模擬的根結點開始模擬博弈，不斷地交替隨機落子直至棋局結束，并根據結束時的勝負狀態來確定結點的收益，這一步驟又稱為Rollout。Rollout過程中采用的走子策略執行速度需要足夠快，以便仿真能夠快速完成，這樣才能得到盡量多的仿真結果，使統計結果逼近真實的勝率。蒙特卡洛樹搜索一般采用隨機策略，實際應用中也可以采用一些“有經驗”的策略，或者兩者的結合。所謂有經驗的策略就像一個有一定水平的棋手，可以下出一些比較好的走法。此外，我們可以在仿真的某個階段采用棋手的走法，另外一些階段采用隨機走法。

1.4反向傳播

模擬完成之后，需要將模擬結果反向傳播回當前博弈樹的根結點，更新從模擬結點到根結點的路徑上的結點信息。更新的結點信息包含兩個部分，一個是結點訪問次數，另一個是結點收益。

1.5制訂行動方案

蒙特卡洛樹搜索終止條件一般設定為到達指定的運行時間。當給定時間用完時，算法終止。搜索結束時，我們需要根據構建出的博弈樹選擇行動方案。以根結點為基，選擇行動方案的方式有三種：（1）選擇具有最大收益的子結點；（2）選擇具有最多訪問次數的子結點；（3）選擇最大化UCB數值的子結點。

1.6蒙特卡洛樹搜索的優缺點

相較于極小極大搜索，蒙特卡洛樹搜索的優點包括：（1）無須設計評估函數，不要求設計者具有問題領域相關的知識，可以在只知道博弈游戲規則的情況下進行搜索，可以應用于不同的博弈問題，是一種通用方法；（2）博弈樹構建是一種非對稱擴展過程，選擇策略會更頻繁地訪問更有希望取勝的結點，并聚焦搜索時間在這些結點上，避免大的分支因子帶來的搜索空間爆炸問題；（3）算法任意時間可輸出，搜索可以在任何時間終止，并返回當前估計的最佳走棋，構造出來的搜索樹可供后續搜索重用。蒙特卡洛樹搜索的主要缺點是需要足夠多的迭代才能收斂到一個很好的行動方案上，例如針對圍棋可能需要百萬次的模擬交戰才能得到專家級的行動方案。

2基于蒙特卡洛樹搜索的智能黑白棋程序

2.1實驗設計的主要目的

蒙特卡洛樹搜索的流程較為復雜，僅通過課堂講解難以令學生對算法流程具有深刻認識，因此需要輔助實驗。通過編碼實現算法的每一個步驟，可以加深對算法的理解。一種實驗方式是將完整算法代碼提供給學生，學生參照代碼復現一次，這種方式缺乏挑戰度，難以激發學生學習興趣。另一種方式是從零構建代碼框架，實現每一個步驟，這種方式的缺點是難度過大，學生容易將精力花費在圖形界面編程而不是算法核心步驟上。因此，實驗采用一種折中的方式，為學生提供完整的代碼框架，將核心函數挖空，要求學生在充分理解算法步驟的前提下完善挖空的核心函數。學生不用分心于如何實現博弈游戲的圖形界面，可以將精力集中在算法核心步驟的實現，提升教學效果。

2.2智能黑白棋程序

實驗將蒙特卡洛樹搜索應用于黑白棋游戲，選擇黑白棋的主要原因包含兩個方面：（1）黑白棋游戲規則簡單，容易上手，即使從未接觸過棋類游戲也可以在幾分鐘內掌握，適應學生學情；（2）黑白棋棋盤為8×8的網格，對應的博弈樹規模適中，既不會太小使得可以通過極小極大搜索遍歷整棵博弈樹，也不會太大導致需要百萬次模擬才能得到較好的行動方案。學生可以在個人計算機上運行蒙特卡洛樹搜索獲得不錯的智能黑白棋程序，完成實驗的時間可以靈活設置。

2.3代碼模塊

實驗提供了智能黑白棋程序的主體框架，框架使用Python語言實現。圖2展示了代碼整體結構，分為game、draw、board和player四個模塊。下面是四個模塊的簡單介紹。

（1）game模塊是主程序模塊，實現了GraphicGame類，負責參數初始化與基本邏輯控制，包含主循環。

（2）draw模塊負責圖形界面繪制，包含了繪制棋盤與棋子的函數。

（3）board模塊包含了棋盤類Board，負責記錄棋盤信息以及進行游戲規則判定，包含is_over、get_winner、get_legal_moves以及make_move方法，分別用于判斷棋局是否結束、勝者是哪一方、獲取當前玩家合法落子位置以及執行落子并更新棋盤。

（4）player模塊包含了不同類型的玩家類，分別為隨機玩家RandomPlayer、策略玩家RoxannePlayer、人類玩家HumanPlayer以及智能體玩家AIPlayer。玩家類包含一個主要方法get_move，輸入一個棋盤類對象，輸出在該棋盤局面下采取的行動方案。RandomPlayer在合法位置隨機落子，RoxannePlayer依據Roxanne策略選擇落子點，HumanPlayer根據鼠標點擊位置確定落子點，AIPlayer采用蒙特卡洛樹搜索的結果選擇落子點。

蒙特卡洛樹搜索算法在AIPlayer類中實現，由MCTS、select、expand、simulate與back_prop五個方法共同組成，MCTS方法包含算法迭代主體，調用剩余四個方法。剩余四個方法分別對應蒙特卡洛樹搜索的四個基本步驟，即選擇、擴展、模擬與反向傳播。學生無須對draw、game和board模塊進行修改，只須完成player模塊中的基于蒙特卡洛樹搜索的智能體AIPlayer。這四個方法主體部分為空，學生需要按要求編寫完成四個方法，實現過程中可以對UCB公式中的參數c、rollout中使用的落子策略、棋局結束時的收益以及搜索時間進行靈活調整，這些參數的調整留給學生自由探索。學生完成編碼后即可運行黑白棋游戲，檢驗實現效果。

3實驗結果與教學反饋

3.1運行結果

進入游戲之后，人類玩家可以選擇先手黑棋或后手白棋，電腦玩家自動選擇另一方。隨機選擇上課班級中的一名學生與智能黑白棋程序進行對弈。圖3展示了人類玩家先手和后手的最終博弈情況，結果均為AIPlayer勝，說明基于蒙特卡洛樹搜索的程序具有較高的智能，能夠有效應對分支因子大的復雜博弈游戲。

3.2教學反饋

在課堂上系統講解蒙特卡洛樹搜索的基本步驟及應用場景之后，引入智能黑白棋程序設計實驗，要求學生利用已學知識實現基于蒙特卡洛樹搜索的智能黑白棋程序。學生在接觸實驗后，學習興趣與課堂參與度明顯提升，在實驗中遇到難題主動尋找解決方案，增強了實踐創新能力。調查問卷反饋結果表示，95%的學生認為實驗提升了他們對蒙特卡洛樹搜索的興趣，在興趣驅使下對算法原理與步驟的掌握更為深刻。90%的學生設計出了能夠戰勝自己的智能黑白棋程序，這一結果體現了基于蒙特卡洛樹搜索的智能黑白棋程序設計實驗能夠提高學生解決實際問題能力。

結語

蒙特卡洛樹搜索是當前主流的博弈搜索技術，適用于復雜的分枝因子較大的博弈游戲，具有重要的應用價值。為了推進人工智能教材知識點更新，實現博弈搜索知識重點從極小極大搜索技術到蒙特卡洛樹搜索技術的轉變，本文詳細介紹了蒙特卡洛樹搜索的基本步驟，設計了智能黑白棋程序實驗。實驗為學生提供了基本的程序框架，將算法核心步驟留空，要求學生在深入理解蒙特卡洛樹搜索步驟的前提下，根據代碼框架提供的信息，完成核心函數的編寫。課堂實踐結果表明，運用智能黑白棋程序實驗可以增強學生的學習興趣，提升課堂參與度，幫助學生更好地掌握算法原理，進一步激發學生創新實踐能力。

參考文獻：

［1］CoulomR.EfficientselectivityandbackupoperatorsinMonte-Carlotreesearch［C］//Internationalconferenceoncomputersandgames.Berlin，Heidelberg：SpringerBerlinHeidelberg，2006：72-83.

［2］SilverD，HuangA，MaddisonCJ，etal.MasteringthegameofGowithdeepneuralnetworksandtreesearch［J］.nature，2016，529（7587）：484-489.

［3］BrowneCB，PowleyE，WhitehouseD，etal.Asurveyofmontecarlo treesearchmethods［J］.IEEETransactionsonComputationalIntelligenceandAIingames，2012，4（1）：1-43.

［4］朱福喜.人工智能［M］.3版.北京：清華大學出版社，2017.

［5］吳飛.人工智能導論：模型與算法［M］.北京：高等教育出版社，2020.

［6］S.Russell，P.Norvig.ArtificialIntelligence：AModernApproach（FourthEdition）［M］.London：Pearson，2020.

［7］CampbellM，HoaneJrAJ，HsuF.Deepblue［J］.Artificialintelligence，2002，134（1-2）：57-83.

基金項目：2022年廣東省研究生教育創新計劃項目“《人工智能》高水平課程及教材建設”（2022SFKC080）；2022年度東莞理工學院質量工程項目“產教融合和多學科交叉背景下人工智能的教學改革與實踐”（202202013）；2020年度東莞理工學院質量工程項目“離散數學”（202002063）；2022年度廣東省本科高校教學質量與教學改革工程項目“以學生為中心的《離散數學》課程教學改革與實踐”

作者簡介：張宇輝（1990—），男，廣東梅州人，博士，東莞理工學院計算機科學與技術學院講師，研究方向：群體智能與進化計算；潘曉衡（1983—），男，湖南衡陽人，碩士，東莞理工學院計算機科學與技術學院高級工程師，研究方向：云計算及人工智能。

*通訊作者：李青青（1991—），女，河南平輿人，博士，東莞理工學院計算機科學與技術學院講師，研究方向：統計學及人工智能。