蒙特卡洛樹搜索實驗設計

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

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

中圖分類號：TP391.4

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

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

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

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

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

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

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

1.1選擇

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

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

UCB（Si）=tini+clnNni

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

1.2擴展

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

1.3模擬

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

1.4反向傳播

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

1.5制訂行動方案

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

1.6蒙特卡洛樹搜索的優(yōu)缺點

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

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

2.1實驗設計的主要目的

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

2.2智能黑白棋程序

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

2.3代碼模塊

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

（1）game模塊是主程序模塊，實現(xiàn)了GraphicGame類，負責參數(shù)初始化與基本邏輯控制，包含主循環(huán)。

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

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

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

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

3實驗結(jié)果與教學反饋

3.1運行結(jié)果

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

3.2教學反饋

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

結(jié)語

蒙特卡洛樹搜索是當前主流的博弈搜索技術，適用于復雜的分枝因子較大的博弈游戲，具有重要的應用價值。為了推進人工智能教材知識點更新，實現(xiàn)博弈搜索知識重點從極小極大搜索技術到蒙特卡洛樹搜索技術的轉(zhuǎn)變，本文詳細介紹了蒙特卡洛樹搜索的基本步驟，設計了智能黑白棋程序?qū)嶒灐嶒灋閷W生提供了基本的程序框架，將算法核心步驟留空，要求學生在深入理解蒙特卡洛樹搜索步驟的前提下，根據(jù)代碼框架提供的信息，完成核心函數(shù)的編寫。課堂實踐結(jié)果表明，運用智能黑白棋程序?qū)嶒灴梢栽鰪妼W生的學習興趣，提升課堂參與度，幫助學生更好地掌握算法原理，進一步激發(fā)學生創(chuàng)新實踐能力。

參考文獻：

［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年廣東省研究生教育創(chuàng)新計劃項目“《人工智能》高水平課程及教材建設”（2022SFKC080）；2022年度東莞理工學院質(zhì)量工程項目“產(chǎn)教融合和多學科交叉背景下人工智能的教學改革與實踐”（202202013）；2020年度東莞理工學院質(zhì)量工程項目“離散數(shù)學”（202002063）；2022年度廣東省本科高校教學質(zhì)量與教學改革工程項目“以學生為中心的《離散數(shù)學》課程教學改革與實踐”

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

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