采用時間差分算法的九路圍棋機器博弈系統

張小川，唐艷，梁寧寧

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

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

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

1 時間差分算法

1.1 強化學習

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

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

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

1.2 時間差分算法

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

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

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

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

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

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

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

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

2.1 系統狀態

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

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

2.2 系統動作

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

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

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

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

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

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

2.3 動作獎勵

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

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

3 實驗

3.1 生成訓練集

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

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

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

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

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

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

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

3.3 實驗結果

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

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

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

3.4 結果分析

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

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

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

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

4 結束語

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

［1］張聰品，劉春紅，徐久成.博弈樹啟發式搜索的α-β剪枝技術研究［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］劉知青，李文峰.現代計算機圍棋基礎［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，FRANCIS 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］.范明，昝紅英，牛常勇，譯.北京:機械工業出版社，2009:372-390.

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

［12］聶衛平，馮大樹.聶衛平圍棋道場［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.