基于蒙特卡洛樹搜索的仿真足球防守策略研究*

柴偉凡，梁志偉，夏晨曦

(南京郵電大學(xué) 自動化學(xué)院，江蘇 南京 210023)

基于蒙特卡洛樹搜索的仿真足球防守策略研究*

柴偉凡，梁志偉，夏晨曦

(南京郵電大學(xué) 自動化學(xué)院，江蘇 南京 210023)

針對Robocup仿真足球比賽中本位點(diǎn)區(qū)域化跑位的局限性，在三角剖分的陣型設(shè)計基礎(chǔ)上將蒙特卡洛樹搜索算法引入2D仿真中，將球員智能體在球場上的狀態(tài)定義為博弈樹節(jié)點(diǎn)，將雙方球員的動作選擇視為節(jié)點(diǎn)間的狀態(tài)轉(zhuǎn)移，對于球隊的防守任務(wù)建立蒙特卡洛樹模型。利用極坐標(biāo)方式對球場進(jìn)行區(qū)域分割，結(jié)合Q學(xué)習(xí)與蒙特卡洛樹搜索中的信心上限樹算法(Upper Confidence Bound Apply to Tree of Monte Carlo)進(jìn)行球隊訓(xùn)練，將訓(xùn)練結(jié)果的動作評估值用于優(yōu)化比賽代碼，使得球隊的防守能力得到了較大程度的提升。

robocup2D仿真；蒙特卡洛樹搜索算法；Q學(xué)習(xí)；動作選擇

0 引言

Robocup2D仿真比賽平臺是一套能夠讓由不同語言編寫的自主球員程序進(jìn)行足球比賽的仿真平臺。服務(wù)器端程序Soccer Server提供了一個虛擬場地并且模擬包括球和球員在內(nèi)的所有物體移動。在仿真2D足球機(jī)器人這一對抗環(huán)境中，日本Helios球隊使用樹搜索算法優(yōu)化了球隊動作鏈[1]。這種方式在小區(qū)域策略中起到了很好的作用，對于仿真足球是很好的啟發(fā)。

基于Delaunay三角剖分的陣型設(shè)計是南郵Apollo2D球隊之前的工作重點(diǎn)[2],如圖1所示，將球場分割成三角網(wǎng)模型，以此實現(xiàn)球員的站位。這套陣型由于本位點(diǎn)區(qū)域化的跑位在本質(zhì)上很不靈活且有一定的局限性，本文在三角剖分的陣型基礎(chǔ)上引入蒙特卡洛樹搜索算法[3]改善球隊的防守策略，分組大量實驗獲取動作在不同區(qū)域的評估值編入比賽代碼，在此基礎(chǔ)上增加球隊動作選擇的科學(xué)性與靈活性。

圖1 Robocup2D球場圖及三角剖分的陣型設(shè)計

1 仿真足球的蒙特卡洛樹模型

蒙特卡洛樹搜索算法是機(jī)器學(xué)習(xí)中的一種博弈樹搜索算法，它是博弈樹搜索算法以及蒙特卡洛模擬方法的結(jié)合，該算法屬于一個純粹的數(shù)學(xué)模型，在多領(lǐng)域具有很好的通用性。將通過2D仿真介紹這一算法。蒙特卡洛樹搜索算法一般分為4個階段：選擇階段、擴(kuò)展階段、模擬階段和回溯更新階段。算法會重復(fù)地執(zhí)行這4個階段，直到滿足場上的某一個特定情況為止。在2D仿真中，這種情況包括我方犯規(guī)、我方攔截成功、敵方進(jìn)球等，整個模擬過程如圖2所示。

圖2 蒙特卡洛樹的建立

圖2中，長方形模塊代表根節(jié)點(diǎn)，樹的建立由根節(jié)點(diǎn)向下擴(kuò)展。該節(jié)點(diǎn)的狀態(tài)一般是指敵方持球進(jìn)攻且進(jìn)入我方半場。另外，當(dāng)發(fā)生敵方獲得定位球等使游戲中斷的狀態(tài)時，此狀態(tài)也將成為下一次防守任務(wù)該博弈樹的根節(jié)點(diǎn)。

橢圓形模塊表示子節(jié)點(diǎn)，子節(jié)點(diǎn)是游戲中發(fā)生狀態(tài)轉(zhuǎn)移的一般節(jié)點(diǎn)，當(dāng)我方智能體選擇動作時產(chǎn)生節(jié)點(diǎn)之間的轉(zhuǎn)移，該節(jié)點(diǎn)保存著我方球員智能體時間以及空間上的狀態(tài)量，即在某一段時間采取什么樣的防守策略。

三角形模塊代表葉子節(jié)點(diǎn)，代表搜索樹到達(dá)了游戲的邊界或者不確定環(huán)境，該節(jié)點(diǎn)狀態(tài)為敵方進(jìn)球、我方斷球等上述情況中的一種，或遍歷到了評估值低于標(biāo)準(zhǔn)值的節(jié)點(diǎn)。

n/N代表著通過該節(jié)點(diǎn)達(dá)到任務(wù)成功的次數(shù)與該節(jié)點(diǎn)被遍歷的總次數(shù)的比值。

選擇階段：從樹的根節(jié)點(diǎn)開始，搜索遍歷整個樹，遞歸地選擇當(dāng)前節(jié)點(diǎn)下評價最高的那個子節(jié)點(diǎn)。當(dāng)遍歷達(dá)到葉子節(jié)點(diǎn)時結(jié)束該階段。

擴(kuò)展階段：添加一個子節(jié)點(diǎn)進(jìn)入博弈樹結(jié)構(gòu)中。簡單地說就是，當(dāng)遇到評估值較低的節(jié)點(diǎn)時，從添加的一系列可采取的防守動作策略中選取新的動作策略進(jìn)入模擬。

模擬階段：利用擴(kuò)展階段所描述的方式進(jìn)行游戲，最后基于模擬的結(jié)果建立新節(jié)點(diǎn)的評估值。即采取某一個新的防守動作或策略，并以此方式直到防守任務(wù)結(jié)束，根據(jù)反饋的比賽結(jié)果評估采取的動作策略。

更新回溯階段：當(dāng)該路徑的遍歷結(jié)束后，沿著樹的逆路徑更新這條路徑上所有節(jié)點(diǎn)的評估值。即根據(jù)防守任務(wù)達(dá)到的成效對之前所采取動作的每一個節(jié)點(diǎn)進(jìn)行評價，改變節(jié)點(diǎn)中收益比值，此階段只更新參與了本次任務(wù)動作的值。

2 動作選擇策略

蒙特卡洛樹模型搭建完成后，模型中各節(jié)點(diǎn)的動作選擇所形成的節(jié)點(diǎn)間的轉(zhuǎn)移過程決定了算法在仿真足球比賽中的適用性。本節(jié)根據(jù)球所在區(qū)域帶來的威脅對球場進(jìn)行區(qū)域劃分，利用Q學(xué)習(xí)算法對各區(qū)域內(nèi)的動作選擇進(jìn)行評估，結(jié)合蒙特卡洛樹搜索的UCT[4]算法更新該動作下整個路徑中的評價值，分小組對各個區(qū)域進(jìn)行實驗獲取每個區(qū)域內(nèi)最合理的參數(shù)值，建立了一個科學(xué)且具有靈活性的動作選擇策略。

2.1 區(qū)域劃分

首先，如圖3所示，通過比賽經(jīng)驗將尺寸為52×68的我方半場不等分地剖分為4塊區(qū)域，根據(jù)敵方帶球隊員所在區(qū)域訓(xùn)練球隊對于禁區(qū)內(nèi)部、邊線進(jìn)攻、中路進(jìn)攻以及外圍傳球的防守能力。

圖3 球場剖分

以球門的正中心點(diǎn)O為極點(diǎn)，由O指向球場中圈的圓心P的射線為極軸建立極坐標(biāo)系。再由O點(diǎn)出發(fā)，與射線OP呈60°作一條射線，并用圓弧將1/4球場分為4份(實線為區(qū)域邊界線，1號區(qū)域由于離球門較近屬于禁區(qū)范圍故不參與分割，所以分割線用虛線表示)，便可以根據(jù)球所在區(qū)域與球門的距離和所呈角度定位敵方球員區(qū)域，設(shè)置參數(shù)數(shù)據(jù)化敵方威脅系數(shù)。

2.2 基于Q學(xué)習(xí)的區(qū)域動作評估

Q學(xué)習(xí)作為強(qiáng)化學(xué)習(xí)的一個主流算法，由Watkins在1989年提出[5]。Q學(xué)習(xí)的核心思想是定義Q(st,at)表，其代表了狀態(tài)st下執(zhí)行動作at并在進(jìn)行多次循環(huán)執(zhí)行所得到的累計回報值，當(dāng)多次重復(fù)實驗達(dá)到收斂后，便可將最優(yōu)策略表示為：

(1)

Q函數(shù)的更新等式如下：

(2)

(3)

算法的優(yōu)勢在于智能體在不需要前瞻性搜索也不需要通過接下來的狀態(tài)進(jìn)行判定就可以獲得最優(yōu)動作。這一優(yōu)勢對于通過多次模擬訓(xùn)練來獲取當(dāng)前區(qū)域內(nèi)的最優(yōu)動作來說非常適用[6]。

由于仿真足球環(huán)境的復(fù)雜性，本文根據(jù)區(qū)域劃分設(shè)立了一套當(dāng)前動作獲得的實時收益的評估機(jī)制，該機(jī)制可以由下式進(jìn)行簡單的表述：

(4)

其中，S(s,dis)代表訓(xùn)練中出現(xiàn)敵方射門情況時的射門結(jié)果和射門距離，當(dāng)敵方進(jìn)球，S(s,dis)取0；η代表敵方球員在我方隊友采取動作s時所在區(qū)域的危險系數(shù)(2.1節(jié)中所劃分的區(qū)域每一塊均設(shè)置了其危險系數(shù))；Q*代表了動作產(chǎn)生的一些直接回報值，例如鏟斷成功、犯規(guī)獲得黃牌等。在此基礎(chǔ)上，便可以在每個區(qū)域動作的訓(xùn)練過程中獲得一個及時的評價值來對動作進(jìn)行優(yōu)化。

2.3 基于UCT算法的動作評估

在仿真足球比賽中，防守的目的便是阻止對方球員進(jìn)攻得分。因此，根據(jù)最終結(jié)果返回區(qū)域動作一個評價值這一延遲獎勵機(jī)制是必不可少的。本小節(jié)將蒙特卡洛樹搜索中的UCT算法引入仿真環(huán)境，對整個動作樹評估機(jī)制進(jìn)行優(yōu)化設(shè)計。

UCT算法雛形來自于多臂匪徒問題[7]，在沒有先驗知識的情況下，算法提出了一個能夠快速收斂且高效的策略。這個算法關(guān)鍵在于很多時候它不僅選擇最好的動作，還同時兼顧探索一些通常的動作，這樣做是通過對每個被訪問的低勢候選動作的勝率增加一個數(shù)來實現(xiàn)的。但是這個數(shù)每次在父節(jié)點(diǎn)被訪問或是其他走法被選擇時會同時升高一點(diǎn)。這一思想可以用信心上界索引公式表示：

(5)

仿真足球環(huán)境中的UCT算法流程在2.1節(jié)中已進(jìn)行介紹，這里不再做過多闡述。它的優(yōu)勢為在保證探索更好的路徑的基礎(chǔ)上具有很好的方向性與自主學(xué)習(xí)能力。

2.4 動作訓(xùn)練

訓(xùn)練過程中，將Q學(xué)習(xí)與UCT算法相結(jié)合，在保證探索性和盡量保證選取最優(yōu)動作的前提下通過調(diào)節(jié)參數(shù)獲得一個較為科學(xué)的評價機(jī)制，公式表述如下：

Vt=aQ(st,at)+I(at)

(6)

其中，UCT算法起主導(dǎo)作用，用于探索未采用的節(jié)點(diǎn)并通過將最終結(jié)果回溯更新動作評價值的方式影響動作的評估值；Q學(xué)習(xí)得到的當(dāng)前區(qū)域動作收益值起到調(diào)整修正總評估值Vt的作用且保證了隨著加權(quán)系數(shù)C的調(diào)整，該實驗的收斂速度。實驗中的算法流程如下：

初始化Q表：

(1)獲取球場信息，創(chuàng)建根節(jié)點(diǎn)N(st)；

(2)將下一步可以采取的動作作為子節(jié)點(diǎn)N′(st)；

(3)由Vt選取動作；

(4)由式(2)得到Q(st,vt)；

(5)N′(s1)訪問下一層子節(jié)點(diǎn)直至終局，回溯更新遍歷的所有子節(jié)點(diǎn)，更新Vt；

(6)轉(zhuǎn)步驟(2)，直至Vt收斂。

在Linux14.04操作系統(tǒng)，rcssserver15.2.2比賽平臺下，使用trainer訓(xùn)練器進(jìn)行場景模擬，分為中路進(jìn)攻、邊路進(jìn)攻的6V5防守場景，以及模擬快速反擊的中路3V2防守場景。對剖分的4塊區(qū)域進(jìn)行分組動作模擬，訓(xùn)練周期為50周期，每個區(qū)域訓(xùn)練次數(shù)為500，根據(jù)收集得到的結(jié)果，繪制折線圖，本小節(jié)以快速反擊情況下2區(qū)域內(nèi)的動作選擇為例，得到的數(shù)據(jù)如圖4所示。

圖4 訓(xùn)練數(shù)據(jù)統(tǒng)計圖

圖4中，橫坐標(biāo)代表訓(xùn)練次數(shù)，縱坐標(biāo)代表動作被選取的百分比?？梢姡?dāng)訓(xùn)練次數(shù)達(dá)到400次左右時，評估函數(shù)已經(jīng)基本收斂。

2.5 比賽應(yīng)用

在Robocup2D仿真比賽中，將模擬訓(xùn)練所得到的數(shù)據(jù)錄入Apollo2016比賽源碼中，得到了一套較為合理的動作選擇策略。而在比賽中，為了避免代碼的復(fù)雜性造成智能體接收信息出現(xiàn)障礙等情況，本文對Apollo2016比賽代碼在Q學(xué)習(xí)策略上進(jìn)行了一定刪除，其中采取蒙特卡洛樹搜索的動作選擇策略偽碼如下：

functionUCTSelect;

while處于比賽狀態(tài)do

ApolloPolicy(s)

//球隊根據(jù)訓(xùn)練數(shù)據(jù)定義的初始策略

returun a(bestaction(s))

functionApolloPolicy(s)

利用a=bestaction(s)進(jìn)行比賽

//初始定義的評估值最高的動作

while返回評估值<定義評估值do

vn← 擴(kuò)展階段(v)

Δ←模擬階段(s)

回溯更新階段(v，Δ)

//s代表當(dāng)前狀態(tài)，v代表當(dāng)前節(jié)點(diǎn)

else

return狀態(tài)s收益

function擴(kuò)展階段(v)

選擇行動a∈其他評估較高的可選擇動作

為v添加子節(jié)點(diǎn)v’，令s(v’)=f(s(v),a),a(v’)=a

returnv’

function模擬階段(s)

whiles非終止?fàn)顟B(tài)do：

繼續(xù)按照apollopolicy策略行動

s←f(s,a)

return狀態(tài)s的收益

function回溯更新階段(v，Δ)

whilev≠Nulldo:

n(v)=n(v)+1;

//更新該條路徑上的訪問次數(shù)

V*(v)=V*+Δ;

//更新所訪問路徑的收益值

functionbestaction(v)

3 比賽結(jié)果分析

本節(jié)將基于蒙特卡洛樹搜索算法的防守策略應(yīng)用于南郵Apollo2016球隊，通過實例分析和比賽數(shù)據(jù)兩方面對球隊進(jìn)行分析，實驗結(jié)果如下。

3.1 實例分析

本小節(jié)以2015年、2016年兩屆Robocup中國賽中南郵Apollo球隊的比賽為例，通過分析對相同情況的不同處理方式論證算法的合理性。

圖5(a)是2015年國賽Apollo2015對陣Yushan2015(2015年國賽亞軍)場景，圖5(b)是2016年國賽Apollo2016對陣Yushan(2016年國賽冠軍)場景。均為敵方智能體斷球后進(jìn)行快速反擊，帶球壓迫至禁區(qū)的情形。

圖5(a)為依賴于Delaunay三角剖分陣型設(shè)計的防守

圖5 比賽實例分析

體系，該體系面對敵方智能體進(jìn)攻時有較好的針對性，不容易出現(xiàn)漏人等情況。但受限于本位點(diǎn)盯防的區(qū)域化限制，在面對反擊時的表現(xiàn)則顯得較為死板。圖中，敵方斷球快速反擊，由9號智能體帶球進(jìn)入禁區(qū)，由于陣型設(shè)計根據(jù)球的位置規(guī)定了球員的防守站位區(qū)域，我方智能體便選擇了區(qū)域協(xié)防策略。然而對方球員在大禁區(qū)位置直接選擇射門，導(dǎo)致球隊失球。圖5(b)為建立在三角剖分陣型基礎(chǔ)上，運(yùn)用基于蒙特卡洛樹搜索的防守策略優(yōu)化后的球隊。由于在之前的訓(xùn)練調(diào)試過程中，出現(xiàn)過多次這樣的丟球情況，根據(jù)反饋評估值，當(dāng)智能體再次面臨這種情況時，就不再使用評估較低的協(xié)防策略，而選擇了4號智能體后撤協(xié)防，3號智能體直接搶斷的動作，這一具有高風(fēng)險高回報的動作最終成功完成防守。

3.2 比賽數(shù)據(jù)分析

本小節(jié)以2016年國賽南郵Apollo2016隊面對前八球隊的詳細(xì)防守數(shù)據(jù)為例，并添加賽后進(jìn)行的Apollo2015、2016對相同對手50次防守實驗和10次比賽實驗比較，數(shù)據(jù)如表1。

表1 球隊防守成功率表 (%)

定義敵方獲得射門機(jī)會以及獲得前場任意球為防守失敗。觀察表1中的數(shù)據(jù)可以清楚地發(fā)現(xiàn)，基于蒙特卡洛樹搜索的防守策略擁有更好的防守效果。本文提出的策略在比賽中擁有更好的靈活性和適用性。

4 結(jié)束語

為了增加球隊防守的全面性與靈活性，本文在三角剖分的陣型設(shè)計上引入基于蒙特卡洛樹搜索算法的防守策略使得球隊動作的執(zhí)行不再更多地依賴于區(qū)域劃分，而是更多地基于場上的形勢，使得Apollo2D球隊獲得了國賽第三這一近年來最好的成績。但是當(dāng)面對沒有交手記錄的強(qiáng)隊時，需要一定時間在比賽中進(jìn)行節(jié)點(diǎn)評估與模擬，這會增加一定的危險性，仍需要其他的保護(hù)策略來優(yōu)化球隊防守能力。

[1] AKIYAMA H, NAKASHIMA T, ARAMAKI S. Online cooperative behavior planning using a tree search method in the robocup soccer simulation[C]. Proceedings of 4th IEEE International Conference on Intelligent Networking and Collaborative Systems (INCoS-2012),2012:170-177.

[2] Xu Xiaoxing, Liang Zhiwei. Team formation design using Delaunay triangulation in Robocup 2D simulation competition[C].Proceedings of 27th Control and Decision Conference (CCDC), Qingdao, China, 2015: 4335-4340.

[3] BRADBERRY J. Introduction to Monte Carlo tree search[EB/OL].(2015-09-07)[2016-08-15]. https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/.

[4] GELLY S, WANG Y. Exploration exploitation in go: UCT for Monte-Carlo go[C]. In: Advances in Neural Information Processing Systems 19 (NIPS),2006.

[5] WATKINS C. Q-Learning[J]. Machine Learning, 1992, 8(3): 279-292.

[6] 申時全. Linux多線程編程技術(shù)在擲骰子游戲模擬程序中的應(yīng)用[J]. 微型機(jī)與應(yīng)用,2016,35(9):85-88.

[7] AUER P. Using confidence bounds for exploitation-exploration trade-offs[J]. the Journal of Machine Learning Research, 2003(3): 397-422.

Research on simulated soccer defensive strategy based on Monte Carlo tree search algorithm

Chai Weifan, Liang Zhiwei, Xia Chenxi

(College of Automation, Nanjing University of Post and Telecommunications, Nanjing 210023, China)

Aiming at the limitation of regionalization of standard point in RoboCup simulating, in this dissertation, Monte Carlo exploring method is introduced to 2D stimulation at the basic of Delaunay triangulation, and it uses player agent to define nodal point of game tree, and players’ choices of movement are regarded as transition among nodes. For defensive works, it builds the Monte Carlo tree model. It utilizes polar coordinates system to make region segmentation, also makes combination of Q learning and Upper Confidence Bound Apply to Tree of Monte Carlo exploring method to train the team players. While using the evaluated value of the training results as optimizedcompetition codes, and team’s defensive ability has been improved enormously in this way.

robocup2D simulation; Monte Carlo tree search; Q-learning; action selection

TP391

A

10.19358/j.issn.1674- 7720.2017.23.015

柴偉凡，梁志偉，夏晨曦.基于蒙特卡洛樹搜索的仿真足球防守策略研究[J].微型機(jī)與應(yīng)用，2017,36(23)：50-53,57.

江蘇省自然科學(xué)基金(BK2012832)

2017-05-01)

柴偉凡(1991-)，通信作者，男，碩士，主要研究方向：智能機(jī)器人理論與技術(shù)。E-mail:chaiwb911@sina.com。

梁志偉(1980-)，男，博士，副教授，主要研究方向：智能機(jī)器人理論與技術(shù)。

夏晨曦(1995-)，男，學(xué)士，主要研究方向：信息安全。