張小川，唐艷，梁寧寧

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

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

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

1 時間差分算法

1.1 強化學習

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

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

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

1.2 時間差分算法

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

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

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

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

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

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

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

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

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

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

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

2.2 系統(tǒng)動作

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

圖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個動作.將時間差分算法應用在圍棋機器博弈中，則此時需解決的問題轉化為求合適的＜類型，方向＞動作.

2.3 動作獎勵

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

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

3 實驗

3.1 生成訓練集

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

圖4 采用神經網絡的時間差分算法Fig.4 The flow chart of the application of temporal difference using neural networks

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

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

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

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

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

3.3 實驗結果

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

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

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

3.4 結果分析

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

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

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

3)訓練次數(shù).在神經網絡中，網絡訓練次數(shù)也直接關系到參數(shù)是否達到目標精度，直接影響學習效果.

4 結束語

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

［1］張聰品，劉春紅，徐久成.博弈樹啟發(fā)式搜索的α-β剪枝技術研究［J］.計算機工程與應用，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)代計算機圍棋基礎［M］.北京:北京郵電大學出版社，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］張汝波，周寧，顧國昌，等.基于強化學習的智能機器人避碰方法研究［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］沈晶，顧國昌，劉海波.基于免疫聚類的自動分層強化學習方法研究［J］.哈爾濱工程大學學報，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］阿培丁.機器學習導論［M］.范明，昝紅英，牛常勇，譯.北京:機械工業(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］.北京:北京體育大學出版社，2004.

［13］徐長明，馬宗民，徐心和，等.面向機器博弈的即時差分學習研究［J］.計算機科學，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.