采用時(shí)間差分算法的九路圍棋機(jī)器博弈系統(tǒng)

張小川，唐艷，梁寧寧

(重慶理工大學(xué)計(jì)算機(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ī)器博弈中有著重要的研究價(jià)值.

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

1 時(shí)間差分算法

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)勢(shì).該方法通過不斷的試探與環(huán)境進(jìn)行交互，根據(jù)試探所得到的反饋來決定下一動(dòng)作選取，不同于傳統(tǒng)的監(jiān)督學(xué)習(xí).監(jiān)督學(xué)習(xí)需要一個(gè)教師信號(hào)來告訴智能體怎樣選取動(dòng)作，并給出好壞程度的評(píng)價(jià)標(biāo)準(zhǔn)，而強(qiáng)化學(xué)習(xí)則是通過環(huán)境反饋來評(píng)價(jià)采取某動(dòng)作的好壞［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)生新著法時(shí)，圍棋棋盤的狀態(tài)就發(fā)生了改變，博弈環(huán)境的狀態(tài)也隨著發(fā)生轉(zhuǎn)移.同時(shí)在博弈進(jìn)程中，從博弈開始到博弈結(jié)束，其整個(gè)過程包含系列的博弈著法，即博弈著法的集合;因此利用強(qiáng)化學(xué)習(xí)解決圍棋博弈問題的核心，就是要建立一種合適的內(nèi)部獎(jiǎng)勵(lì)機(jī)制，使得博弈程序或圍棋人工生命體能執(zhí)行最大化內(nèi)部獎(jiǎng)勵(lì)的局部動(dòng)作，從而學(xué)會(huì)發(fā)現(xiàn)一個(gè)最佳的著法序列，并提高博弈水平.

1.2 時(shí)間差分算法

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

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

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

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

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

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

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

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

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

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

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

2.2 系統(tǒng)動(dòng)作

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

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

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

圖3 四大基本動(dòng)作Fig.3 4 Basic actions

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

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

2.3 動(dòng)作獎(jiǎng)勵(lì)

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

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

3 實(shí)驗(yàn)

3.1 生成訓(xùn)練集

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

圖4 采用神經(jīng)網(wǎng)絡(luò)的時(shí)間差分算法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)計(jì)算Q(st，at)值，式(3)中需要用到的獎(jiǎng)勵(lì)ra則由式(6)得到，再將 st、at、Q(st，at)存儲(chǔ)至系統(tǒng)中得到樣本集 TS(表 1給出樣本集TS中10個(gè)訓(xùn)練樣本).其中折扣率γ取0.5，η 取 0.4，η 隨時(shí)間逐漸減小，每次減小0.001 2.需注意的是，由于圍棋博弈空間巨大，故訓(xùn)練時(shí)需要相當(dāng)數(shù)量的樣本才能達(dá)到訓(xùn)練效果，本文選取的樣本數(shù)為4 000.

表1 TS樣本集中的10個(gè)樣本Table 1 10 samples of TS sample set

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

本文采用BP神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)輸入層有9個(gè)節(jié)點(diǎn)，由系統(tǒng)狀態(tài)集 S={Sn，Se，Sl，On，Oe，Ol}、表示動(dòng)作位置的x和y，以及用哈希值存儲(chǔ)的整個(gè)棋盤表示s組成，隱藏層4個(gè)節(jié)點(diǎn)，輸出層1個(gè)節(jié)點(diǎn).初始訓(xùn)練時(shí)網(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í)過程中，可將每一個(gè)或一定數(shù)量的棋譜文件視為學(xué)習(xí)的一個(gè)停頓.訓(xùn)練好神經(jīng)網(wǎng)絡(luò)后，保留修改好的權(quán)值和閾值等參數(shù).

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

3.3 實(shí)驗(yàn)結(jié)果

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

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

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

3.4 結(jié)果分析

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

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

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

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é)束語

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

［1］張聰品，劉春紅，徐久成.博弈樹啟發(fā)式搜索的α-β剪枝技術(shù)研究［J］.計(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ì)算機(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］沈晶，顧國昌，劉海波.基于免疫聚類的自動(dòng)分層強(qiáng)化學(xué)習(xí)方法研究［J］.哈爾濱工程大學(xué)學(xué)報(bào)，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)平圍棋道場(chǎng)［M］.北京:北京體育大學(xué)出版社，2004.

［13］徐長明，馬宗民，徐心和，等.面向機(jī)器博弈的即時(shí)差分學(xué)習(xí)研究［J］.計(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.