張小川，唐艷，梁寧寧

(重慶理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，重慶400054)

近年來人工智能是信息科學(xué)中重要的熱點(diǎn)研究領(lǐng)域之一，其相關(guān)算法、技術(shù)及研究成果正被廣泛運(yùn)用于各行業(yè)，如軍事、心理學(xué)、智能機(jī)器、商業(yè)智能等.機(jī)器博弈是人工智能研究的重要分支，而圍棋機(jī)器博弈是機(jī)器博弈的熱點(diǎn)問題之一，其龐大的搜索空間和較高的復(fù)雜度，使其在機(jī)器博弈中有著重要的研究價值.

目前，圍棋機(jī)器博弈中常采用的博弈算法有α-β剪枝搜索算法［1］、模式匹配［2-3］和 UCT 算法［4］等.圍棋機(jī)器博弈相對于六子棋、象棋等其他棋類博弈擁有更大的搜索空間和更高的復(fù)雜度，當(dāng)采用α-β等傳統(tǒng)搜索算法時，會在時間有限情況下無法搜索到目標(biāo)解.因此，本文嘗試將時間差分法引入至圍棋機(jī)器博弈，將博弈系統(tǒng)看成一個具有自我學(xué)習(xí)能力的圍棋人工生命體或圍棋智能體，它能在不斷的博弈過程中提高自己的博弈能力.借助計算機(jī)C語言，實現(xiàn)了該圍棋機(jī)器博弈系統(tǒng)，并且通過博弈實戰(zhàn)驗證了該方法的有效性和可行性.

1 時間差分算法

1.1 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)(reinforcement learning，RL)較其他常用的機(jī)器學(xué)習(xí)算法，如神經(jīng)網(wǎng)絡(luò)、決策樹等，在博弈系統(tǒng)中有著獨(dú)特優(yōu)勢.該方法通過不斷的試探與環(huán)境進(jìn)行交互，根據(jù)試探所得到的反饋來決定下一動作選取，不同于傳統(tǒng)的監(jiān)督學(xué)習(xí).監(jiān)督學(xué)習(xí)需要一個教師信號來告訴智能體怎樣選取動作，并給出好壞程度的評價標(biāo)準(zhǔn)，而強(qiáng)化學(xué)習(xí)則是通過環(huán)境反饋來評價采取某動作的好壞［5-7］.圖1簡單描述了強(qiáng)化學(xué)習(xí)中智能體與環(huán)境的交互過程(其中s為智能體當(dāng)前所處的環(huán)境狀態(tài)).

圖1 強(qiáng)化學(xué)習(xí)中智能體與環(huán)境交互過程Fig.1 The agent and the environment interactionprocess in reinforcement learning

如果將強(qiáng)化學(xué)習(xí)應(yīng)用到圍棋機(jī)器博弈中，博弈程序變成具有一定智能的決策者，而圍棋棋盤就被看作博弈環(huán)境.當(dāng)博弈雙方產(chǎn)生新著法時，圍棋棋盤的狀態(tài)就發(fā)生了改變，博弈環(huán)境的狀態(tài)也隨著發(fā)生轉(zhuǎn)移.同時在博弈進(jìn)程中，從博弈開始到博弈結(jié)束，其整個過程包含系列的博弈著法，即博弈著法的集合;因此利用強(qiáng)化學(xué)習(xí)解決圍棋博弈問題的核心，就是要建立一種合適的內(nèi)部獎勵機(jī)制，使得博弈程序或圍棋人工生命體能執(zhí)行最大化內(nèi)部獎勵的局部動作，從而學(xué)會發(fā)現(xiàn)一個最佳的著法序列，并提高博弈水平.

1.2 時間差分算法

時間差分算法(temporal difference)是強(qiáng)化學(xué)習(xí)的一種重要算法［7］，其利用探索所得到的下一狀態(tài)的價值和獎勵來更新當(dāng)前狀態(tài)的價值［8］.本文經(jīng)過研究分析，構(gòu)造了博弈狀態(tài)轉(zhuǎn)移特征方法，利用該方法獲得的特征信息(特別是激勵性信息)反饋于當(dāng)前博弈狀態(tài)，并更新當(dāng)前博弈狀態(tài)，引導(dǎo)博弈系統(tǒng)的價值取向，這就是本文引入時間差分算法的機(jī)器博弈的基本思路.

在實際應(yīng)用中，通常采用成對的狀態(tài)－動作值Q(st，at)來表示當(dāng)處于狀態(tài)st時執(zhí)行動作at的價值.在簡單的確定的情況下，任意一對狀態(tài)－動作只有1個獎勵和可能的下一狀態(tài)，根據(jù)Bellman公式，可得如式(1)的簡化公式［9］:

由此可以看出 Q^(st+1，at+1)是更新后的值，具有更高的正確概率.將式(2)引入，以減小當(dāng)前Q值與一個時間步驟之后的估計值之間的誤差，則有式(3):

式中:η為更新因子，隨時間的增加逐漸減小;γ為折扣率，0≤γ＜1，保證返回的獎勵為有限的.

對于動作的選取，在知識量少的初期，可以在所有動作中隨機(jī)選取，可看作“探索”.但也不希望一直探索下去，故探索到一定時，需利用當(dāng)前所學(xué)知識.為此采用一個溫度變量T來實現(xiàn)從探索到利用知識的轉(zhuǎn)移，下面給出加入溫度變量時選擇動作a的概率［10］:

當(dāng)T很大時，所有概率趨近于相等，此時進(jìn)行隨機(jī)探索;當(dāng)T很小時，價值更大的動作被選取的可能性較大，則實現(xiàn)對知識的利用.所以在學(xué)習(xí)的過程中以一個較大的T值開始，不斷地縮小T值，完成探索直至利用知識.

2 基于時間差分算法的圍棋機(jī)器博弈模型

當(dāng)求解問題的狀態(tài)空間較大時，會使強(qiáng)化學(xué)習(xí)算法的收斂效率降低，這就要求增加實驗次數(shù)，但降低了算法的實時性［11］.而在圍棋機(jī)器博弈中，若搜索超時則直接判負(fù).并且當(dāng)處于中局時，棋盤狀態(tài)復(fù)雜度增加，若把每個可下點(diǎn)看作一個動作，則算法的狀態(tài)與動作數(shù)量大幅度增長.故需采用其他策略減少問題狀態(tài)空間，以增強(qiáng)算法的實時性.為此，采用將靜態(tài)估值與時間差分算法相結(jié)合的策略，在產(chǎn)生可下節(jié)點(diǎn)時，選取靜態(tài)估值較大的點(diǎn)，再在此點(diǎn)上利用時間差分算法完成動作的選取.

2.1 系統(tǒng)狀態(tài)

在博弈過程中，圍棋棋盤狀態(tài)作為環(huán)境因素直接影響博弈智能體作出的決策，如開局時擺棋形、博弈過程中己方受威脅棋子、對方受威脅棋子等.本文選取環(huán)境因素中對博弈智能體的決策影響較大的因素作為系統(tǒng)問題狀態(tài).該狀態(tài)集形式化描述如式(5):

式中:Sn為當(dāng)前棋盤上己方棋子總數(shù)，Se為當(dāng)前棋盤上己方眼總數(shù)，Sl為當(dāng)前棋盤上己方氣總數(shù)，On為當(dāng)前棋盤上對方棋子總數(shù)，Oe為當(dāng)前棋盤上對方眼總數(shù)，Ol為當(dāng)前棋盤上對方氣總數(shù).其中，Sn與On直接關(guān)系到當(dāng)前博弈雙方對弈的局勢;Se與Oe直接關(guān)系到某串棋是否為活棋，如當(dāng)某串棋有2個眼，則被提掉的可能性減小至0;Sl與Ol則直接關(guān)系到棋子被提的可能性和地盤的占有率.

2.2 系統(tǒng)動作

圍棋每走一步都有相應(yīng)的說法，即術(shù)語，而常用的圍棋術(shù)語有很多，如“拆”、“飛”、“長”、“立”、“尖”、“扳”、“接”、“斷”、“挖”、“夾”、“托”、“虎”和“刺”等［12］.若將每一種下法作為一種動作，則系統(tǒng)動作數(shù)量會過大而使算法失去實用性.這需要將術(shù)語歸類，也就是劃分基本動作.下面以“扳”和“挖”為例說明其歸為哪一基本動作，如圖2所示，未標(biāo)號棋子為已下棋子，標(biāo)號棋子為欲下棋子.

圖2 圍棋的一些著法Fig.2 Some actions in Go

由圖2可知，“扳”和“挖”均可看作在己方棋子的“尖”或“跳”位置上下棋，若選取“扳”和“挖”中離棋子1位置最近的己方棋子則為“尖”.采用此歸類方法，選取如下四大類下法作為基本動作:“拆”、“飛”、“尖”和“長”，如圖3所示.

圖3 四大基本動作Fig.3 4 Basic actions

由此可得到動作的形式化描述集A，具體形式如下:

式中:動作集A由動作類型和方向參數(shù)2個參數(shù)組成.動作類型有 6種，分別為“拆 1”、“拆 2”、“飛1”、“飛2”、“尖”和“長”.“拆 1”、“拆 2”、“尖”和“長”的方向參數(shù)為上下左右4個，“飛1”和“飛2”的方向參數(shù)為上下左右和右上、右下、左上、左下8個.6種動作組合一起，共32個動作.將時間差分算法應(yīng)用在圍棋機(jī)器博弈中，則此時需解決的問題轉(zhuǎn)化為求合適的＜類型，方向＞動作.

2.3 動作獎勵

當(dāng)嘗試動作a時，系統(tǒng)會獲得一個獎勵ra，并且在圍棋機(jī)器博弈中這樣的獎勵是確定的.在實際的博弈過程中，獎勵跟下棋后棋盤位置的靜態(tài)值、己方棋子總數(shù)與對方棋子總數(shù)、是否吃子與被吃、氣微薄的數(shù)目等信息有關(guān).例如，當(dāng)落下某棋子時，使得某串棋的氣數(shù)減少(甚至為1)，這樣很有可能在對方下一手棋或后幾手的時候提掉整個串，這樣的下子動作將會得到較少的獎勵(甚至為負(fù)).基于這樣的情況，下面給出動作獎勵規(guī)則:

式中:Sv為棋盤棋子位置的靜態(tài)分值，Sn為己方棋子總數(shù)與對方棋子總數(shù)的差值，Ln為吃子與被吃子數(shù)的差值，S1為對方氣為1的棋子數(shù)目與己方氣為1的棋子數(shù)目的差值.

3 實驗

3.1 生成訓(xùn)練集

當(dāng)Q(st，at)值(即狀態(tài)－動作值)很大時，用表格等手段存儲，則表格的尺寸會非常大，這使得搜索空間也增大.為此，在基于時間差分算法的圍棋機(jī)器博弈系統(tǒng)中，采用人工神經(jīng)網(wǎng)絡(luò)作為回歸器，此時以st、at作為網(wǎng)路輸入，Q(st，at)值為網(wǎng)絡(luò)輸出，如圖 4所示.

圖4 采用神經(jīng)網(wǎng)絡(luò)的時間差分算法Fig.4 The flow chart of the application of temporal difference using neural networks

由于人工神經(jīng)網(wǎng)絡(luò)為監(jiān)督學(xué)習(xí)方法，因此需要訓(xùn)練集TS.故本文首先將棋譜文件導(dǎo)入至博弈系統(tǒng)中，按照棋譜文件下棋，根據(jù)式(3)計算Q(st，at)值，式(3)中需要用到的獎勵ra則由式(6)得到，再將 st、at、Q(st，at)存儲至系統(tǒng)中得到樣本集 TS(表 1給出樣本集TS中10個訓(xùn)練樣本).其中折扣率γ取0.5，η 取 0.4，η 隨時間逐漸減小，每次減小0.001 2.需注意的是，由于圍棋博弈空間巨大，故訓(xùn)練時需要相當(dāng)數(shù)量的樣本才能達(dá)到訓(xùn)練效果，本文選取的樣本數(shù)為4 000.

表1 TS樣本集中的10個樣本Table 1 10 samples of TS sample set

3.2 仿真Q(st，at)值與選取動作

本文采用BP神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)輸入層有9個節(jié)點(diǎn)，由系統(tǒng)狀態(tài)集 S={Sn，Se，Sl，On，Oe，Ol}、表示動作位置的x和y，以及用哈希值存儲的整個棋盤表示s組成，隱藏層4個節(jié)點(diǎn)，輸出層1個節(jié)點(diǎn).初始訓(xùn)練時網(wǎng)絡(luò)權(quán)值隨機(jī)賦值，學(xué)習(xí)率α取0.5，學(xué)習(xí)精度θ取0.000 1.BP神經(jīng)網(wǎng)絡(luò)根據(jù)前向傳播輸出原理，利用誤差反向傳播修改權(quán)值和閾值.在學(xué)習(xí)過程中，可將每一個或一定數(shù)量的棋譜文件視為學(xué)習(xí)的一個停頓.訓(xùn)練好神經(jīng)網(wǎng)絡(luò)后，保留修改好的權(quán)值和閾值等參數(shù).

訓(xùn)練結(jié)束后，就可進(jìn)行對弈.在博弈時將提取到的棋盤狀態(tài)st和搜索到的所有合法動作at，輸入至9×4×1的 BP神經(jīng)網(wǎng)絡(luò)中，得到 Q(st，at)值.然后把當(dāng)前所有合法動作at所對應(yīng)的Q(sl，at)值都求出來，之后便采用式(4)的方法選取動作at.其中式(4)中溫度變量T的初值為500，在博弈過程中逐漸減小(每次減小1)，從而達(dá)到從知識的探索過渡到知識的利用.當(dāng)T值減小到一定程度時則實現(xiàn)知識利用，P(a|s)值大的動作更容易被選取到.此時本文采用輪盤賭的方式，生成一個p(0＜p＜1)，判斷p值落在哪2個動作的P(a|s)值之間，便可判斷選取哪個動作at.

3.3 實驗結(jié)果

在實驗初期，由于采用零知識學(xué)習(xí)，未給予任何其他相關(guān)輔助知識，如眼的識別判斷、活棋的判斷等;故此時該博弈系統(tǒng)并沒有體現(xiàn)其優(yōu)勢，常走出壞招死招.當(dāng)加入知識判斷時，系統(tǒng)的博弈能力明顯提高.并且通過實驗發(fā)現(xiàn)，在單純采用時間差分算法時，博弈智能體在博弈初期發(fā)揮較好，搜索時間短，能為后面棋局?jǐn)[一個良好陣形.但當(dāng)進(jìn)入至中局和終局時，進(jìn)攻能力減弱，系統(tǒng)處于劣勢.

將引入時間差分算法的CQUTGO-2與采用α-β算法的CQUTGO-1對弈100盤，其中CQUTGO-2執(zhí)黑和執(zhí)白各50盤，其對弈結(jié)果如圖5所示.由此可見在采用時間差分算法后，博弈系統(tǒng)的博弈能力較之前有所提高.

圖5 CQUTGO-1與CQUTGO-2對弈的結(jié)果Fig.5The game results of CQUTGO-1 and CQUTGO-2

3.4 結(jié)果分析

在基于人工神經(jīng)網(wǎng)絡(luò)的時間差分算法中，神經(jīng)網(wǎng)絡(luò)的各個方面均對算法在九路圍棋機(jī)器博弈系統(tǒng)的應(yīng)用效果產(chǎn)生影響，包括樣本集、神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)和訓(xùn)練次數(shù).

1)樣本集的選取.在實際博弈過程中，同一系統(tǒng)狀態(tài)下有多種動作可供選擇.采用棋譜文件導(dǎo)入至系統(tǒng)中，便于樣本提取并可按不同對手選擇不同的棋譜文件.但棋譜文件中出現(xiàn)棋盤狀態(tài)相同的次數(shù)較少，會降低樣本集學(xué)習(xí)價值，影響學(xué)習(xí)效果.有的學(xué)者在選取樣本集時采用隨機(jī)擴(kuò)展方法，以產(chǎn)生在數(shù)量和質(zhì)量上均可觀的樣本集［13］.

2)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu).采用神經(jīng)網(wǎng)絡(luò)仿真Q(st，at)值時，網(wǎng)絡(luò)輸出則直接為相應(yīng)的 st、at的 Q(st，at)值.故網(wǎng)絡(luò)結(jié)構(gòu)直接影響Q(st，at)值，也就直接影響動作的選取和博弈的決策.選取9個棋盤特征作為網(wǎng)絡(luò)輸入，但事實上這樣并不能完全描述整個棋盤狀態(tài).例如可將氣為1、氣為2的棋子數(shù)作為棋盤特征時，當(dāng)氣為1時很可能被提掉，當(dāng)氣為2時，可以形成真眼.

3)訓(xùn)練次數(shù).在神經(jīng)網(wǎng)絡(luò)中，網(wǎng)絡(luò)訓(xùn)練次數(shù)也直接關(guān)系到參數(shù)是否達(dá)到目標(biāo)精度，直接影響學(xué)習(xí)效果.

4 結(jié)束語

本文將時間差分算法應(yīng)用在機(jī)器博弈中，給出了包含系統(tǒng)狀態(tài)、系統(tǒng)動作及動作獎勵的博弈系統(tǒng)模型，并通過實驗驗證了該方法的有效性.引入時間差分算法后的博弈系統(tǒng)是一個具有自學(xué)習(xí)能力的博弈智能體，能在不斷的博弈過程中提高博弈水平.由于圍棋博弈的復(fù)雜度較高，因此為了提高算法實時性，采用此類模型時將系統(tǒng)狀態(tài)統(tǒng)計為6個狀態(tài)因素向量，下棋動作劃分為6類.這樣便簡化了系統(tǒng)狀態(tài)和動作.雖然該方法能提高算法實時性，但其也存在不足，無法清晰劃分動作和系統(tǒng)狀態(tài).而且系統(tǒng)狀態(tài)和動作的劃分直接影響人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，進(jìn)而影響模擬結(jié)果.本文后期研究工作的方向是在保證算法實時性的前提下，如何劃分系統(tǒng)的狀態(tài)和動作.而現(xiàn)階段圍棋機(jī)器博弈大都采用蒙特卡洛算法，后期亦可考慮與其結(jié)合來提高算法的有效性.

［1］張聰品，劉春紅，徐久成.博弈樹啟發(fā)式搜索的α-β剪枝技術(shù)研究［J］.計算機(jī)工程與應(yīng)用，2008，44(16):54-55，97.

ZHANG Congpin，LIU Chunhong，XU Jiucheng.Research on alpha-beta pruning of heuristic search in game-playing tree［J］.Computer Engineering and Applications，2008，44(16):54-55，97.

［2］劉知青，李文峰.現(xiàn)代計算機(jī)圍棋基礎(chǔ)［M］.北京:北京郵電大學(xué)出版社，2011:63-80.

［3］GELLY S，WANG Yizao，MUNOS R，et al.Modification of UCT with patterns in Monte-Carlo Go［R/OL］.［2011-10-15］.http://219.142.86.87/paper/RR-6062.pdf.

［4］GELLY S，WANG Yizao.Exploration exploitation in Go:UCT for Monte-Carlo Go［C/OL］.［2011-10-15］.http://wenku.baidu.com/view/66c2edd6b9f3f90f76c61bc0.html.

［5］張汝波，周寧，顧國昌，等.基于強(qiáng)化學(xué)習(xí)的智能機(jī)器人避碰方法研究［J］.機(jī)器人，1995，21(3):204-209.

ZHANG Rubo，ZHOU Ning，GU Guochang，et al.Reinforcement learning based obstacle avoidance learning for intelligent robot［J］.Robot，1995，21(3):204-209.

［6］沈晶，顧國昌，劉海波.基于免疫聚類的自動分層強(qiáng)化學(xué)習(xí)方法研究［J］.哈爾濱工程大學(xué)學(xué)報，2007，28(4):423-428.

SHEN Jing，GU Guochang，LIU Haibo.Hierarchical reinforcement learning with an automatically generated hierarchy based on immune clustering［J］.Journal of Harbin Engineering University，2007，28(4):423-428.

［7］BAE J，CHHATBAR P，F(xiàn)RANCIS J T，et al.Reinforcement learning via kernel temporal difference［C］//Proceedings of the Annual International Conference of the IEEE Engineering in Medicine and Biology Society.Boston，USA，2011:5662-5665.

［8］SUTTON R S.Learning to predict by the methods of temporal difference［J］.Machine Learning，1988，3(1):9-44.

［9］KAELBLING L P，LITTMAN M L，MOORE A W.Rein forcement learning:a survey［J］.Journal of Artificial Intelligence Research，1996，4:237-285.

［10］阿培丁.機(jī)器學(xué)習(xí)導(dǎo)論［M］.范明，昝紅英，牛常勇，譯.北京:機(jī)械工業(yè)出版社，2009:372-390.

［11］SUTTON R S，BARTO A G.Reinforcement learning:an introduction［M］.Cambridge，USA:The MIT Press，1997.

［12］聶衛(wèi)平，馮大樹.聶衛(wèi)平圍棋道場［M］.北京:北京體育大學(xué)出版社，2004.

［13］徐長明，馬宗民，徐心和，等.面向機(jī)器博弈的即時差分學(xué)習(xí)研究［J］.計算機(jī)科學(xué)，2010，37(8):219-224.

XU Changming，MA Zongmin，XU Xinhe，et al.Study of temporal difference learning in computer games［J］.Computer Science，2010，37(8):219-224.