李 楓，王彥博

(1.北華大學(xué)大數(shù)據(jù)與智慧校園管理中心，吉林 吉林 132013；2.天津大學(xué)建筑工程學(xué)院，天津 300350)

計(jì)算機(jī)博弈(也稱機(jī)器博弈)是現(xiàn)代人工智能領(lǐng)域的熱點(diǎn)問(wèn)題，也被認(rèn)為是人工智能領(lǐng)域最具挑戰(zhàn)性的研究方向之一.計(jì)算機(jī)博弈就是讓計(jì)算機(jī)像人類一樣，學(xué)習(xí)并實(shí)現(xiàn)博弈功能.簡(jiǎn)而言之，就是希望計(jì)算機(jī)有類似人一樣的準(zhǔn)確思維、判斷和推理決策能力[1].計(jì)算機(jī)博弈有兩次受到全世界關(guān)注：第一次是在1997年，“深藍(lán)”計(jì)算機(jī)國(guó)際象棋程序打敗人類世界冠軍卡斯特羅夫；另一次是在2016年，由谷歌團(tuán)隊(duì)設(shè)計(jì)的阿爾法圍棋(AlphaGo)以4∶1戰(zhàn)勝了李世石.這兩次勝利，不僅給計(jì)算機(jī)博弈領(lǐng)域帶來(lái)了巨大的突破和影響，同時(shí)也掀起了整個(gè)人工智能領(lǐng)域的研究高潮[2].圍棋人工智能一直是計(jì)算機(jī)博弈領(lǐng)域的重點(diǎn)，開(kāi)發(fā)運(yùn)用的算法及決策方式有助于擴(kuò)大智能計(jì)算方法的適用范圍，解決一大類優(yōu)化、決策和規(guī)劃智能問(wèn)題，從而進(jìn)一步擴(kuò)展人工智能的疆域.蒙特卡洛評(píng)估是一種動(dòng)態(tài)評(píng)估方法，與傳統(tǒng)利用單純圍棋知識(shí)的思想完全不同，更多地利用數(shù)學(xué)統(tǒng)計(jì)中的概率思想，在一段時(shí)間內(nèi)大幅提高了計(jì)算機(jī)對(duì)圍棋局面判斷的水平，實(shí)現(xiàn)了由傳統(tǒng)計(jì)算機(jī)圍棋到現(xiàn)代計(jì)算機(jī)圍棋的飛躍[3].阿爾法圍棋開(kāi)拓出的利用深度學(xué)習(xí)——人工神經(jīng)網(wǎng)絡(luò)解決計(jì)算機(jī)圍棋問(wèn)題的方法進(jìn)一步拉開(kāi)了計(jì)算機(jī)棋手與人類棋手的差距，利用價(jià)值評(píng)估系統(tǒng)以及增強(qiáng)學(xué)習(xí)網(wǎng)絡(luò)成為研究、討論的熱點(diǎn).但就形勢(shì)判斷來(lái)說(shuō)，單純使用神經(jīng)網(wǎng)絡(luò)需要訓(xùn)練大量有標(biāo)簽的棋譜，對(duì)硬件條件、時(shí)間、數(shù)據(jù)量要求都非常高.基于此，將傳統(tǒng)的蒙特卡洛、專家系統(tǒng)等方法與神經(jīng)網(wǎng)絡(luò)相結(jié)合成為一個(gè)研究方向.但在沒(méi)有配備高端服務(wù)器的情況下進(jìn)行神經(jīng)網(wǎng)絡(luò)局勢(shì)判斷存在以下問(wèn)題：第一，大規(guī)模數(shù)據(jù)及其標(biāo)簽不容易獲得；第二，訓(xùn)練所需時(shí)間太長(zhǎng)，對(duì)機(jī)器性能要求太高.因此，為了解決傳統(tǒng)方法專家系統(tǒng)評(píng)估不準(zhǔn)確，單純使用“勢(shì)函數(shù)”帶來(lái)計(jì)算誤差，以及采用“value net”方法訓(xùn)練時(shí)間太長(zhǎng)及對(duì)機(jī)器性能要求過(guò)高的問(wèn)題，本文選擇專家系統(tǒng)模式庫(kù)、影響函數(shù)給出特征值，將特征值傳遞給深度適配網(wǎng)絡(luò)(Deep Adaptation Network，DAN)，利用少量樣本訓(xùn)練獲得較好的評(píng)估模型[4].

1 圍棋規(guī)則及局面評(píng)估

1.1 圍棋規(guī)則

圍棋，是一種智力運(yùn)動(dòng)，起源于中國(guó)，有幾千年歷史.當(dāng)代圍棋主要使用縱橫各19個(gè)垂直交叉的方格型棋盤(pán)，形成361個(gè)交叉點(diǎn)(在圍棋中稱為“點(diǎn)”).棋局開(kāi)始后，雙方各執(zhí)一種棋子，黑先走，輪流下子，交替行棋，落子后不能移動(dòng).

對(duì)于輸贏的計(jì)算一般有3種規(guī)則，即日韓規(guī)則、中國(guó)規(guī)則和應(yīng)氏規(guī)則.其中，日韓規(guī)則在終局時(shí)需黑貼6.5目，中國(guó)規(guī)則為黑貼3又3/4子，應(yīng)氏規(guī)則為黑貼8目.

1.2 圍棋局面判斷

局面評(píng)估，在圍棋中稱為“形勢(shì)判斷”.在人類棋手的對(duì)弈中，一張一弛正確與否大部分取決于對(duì)形勢(shì)判斷的精確程度，能否做到張弛有序，取決于對(duì)形勢(shì)判斷與局部及全局協(xié)調(diào)的計(jì)算能力；對(duì)于圍棋智能對(duì)弈系統(tǒng)，局面評(píng)估同樣至關(guān)重要.在早期的圍棋對(duì)弈軟件中，大部分選擇把確定目數(shù)(圍棋中對(duì)所占區(qū)域的專業(yè)術(shù)語(yǔ))作為形勢(shì)判斷的依據(jù)，忽略了“勢(shì)”(圍棋中對(duì)于隱藏勢(shì)力的描述)、“孤棋”(沒(méi)有完全活，但有存活可能性的棋子或棋串)對(duì)當(dāng)前局面的影響.后來(lái)的改良方法加入了“勢(shì)函數(shù)”，即將各個(gè)棋子對(duì)距離為“1”(相鄰一格)的影響力賦予一個(gè)對(duì)應(yīng)值(如“9”)，隨著距離增大依次遞減.這種方式較大地提高了形勢(shì)判斷的準(zhǔn)確性，但得出的判斷值依舊不能完全體現(xiàn)當(dāng)前局面的優(yōu)劣.

2 基于價(jià)值評(píng)估的局面判斷算法

基于價(jià)值評(píng)估的圍棋局面判斷流程見(jiàn)圖1.本算法利用專家系統(tǒng)中的影響函數(shù)計(jì)算產(chǎn)生特征值并輸入到深度適配網(wǎng)絡(luò)，通過(guò)小樣本數(shù)據(jù)訓(xùn)練，可以得出圍棋局面判斷網(wǎng)絡(luò).網(wǎng)絡(luò)采用深度適配網(wǎng)絡(luò)DAN.

2.1 專家系統(tǒng)及影響函數(shù)

專家系統(tǒng)主要用來(lái)組成價(jià)值評(píng)估模塊.將通過(guò)專家系統(tǒng)計(jì)算到的知識(shí)庫(kù)特征與影響函數(shù)計(jì)算出的特征值輸入到深度適配網(wǎng)絡(luò)中，形成計(jì)算機(jī)對(duì)棋面的價(jià)值評(píng)估，如局面分布、黑白棋當(dāng)前形勢(shì)、厚薄等等.知識(shí)庫(kù)應(yīng)用相對(duì)簡(jiǎn)單，主要通過(guò)模式匹配：死活庫(kù)簡(jiǎn)化計(jì)算機(jī)對(duì)基本死活型的判斷，定式庫(kù)給出可能的下一步選點(diǎn)，模式庫(kù)對(duì)3×3棋盤(pán)分塊.遍歷比對(duì)輸入數(shù)據(jù)，若符合知識(shí)庫(kù)的特征則作為之后網(wǎng)絡(luò)的輸入特征使用.

圍棋中的影響函數(shù)按照一定規(guī)則(比如根據(jù)棋子的數(shù)量、有無(wú)斷點(diǎn)等)判斷價(jià)值，之后計(jì)算每一個(gè)棋子對(duì)周圍一定范圍的影響值.如果出現(xiàn)某交叉點(diǎn)受多個(gè)棋子影響，則根據(jù)己方或?qū)Ψ降姆绞竭M(jìn)行權(quán)值疊加計(jì)算，最后給定閾值，將當(dāng)前棋局劃分出黑、白勢(shì)力范圍，賦予相應(yīng)數(shù)值.影響函數(shù)的計(jì)算需要3步完成：評(píng)估、規(guī)范化、生成.

本文提及的影響函數(shù)[5]見(jiàn)圖2.如果將該影響函數(shù)產(chǎn)生的數(shù)值直接輸入DAN網(wǎng)絡(luò)進(jìn)行訓(xùn)練，會(huì)引起網(wǎng)絡(luò)參數(shù)迭代過(guò)程漫長(zhǎng)、難以收斂.因此，對(duì)數(shù)據(jù)進(jìn)行預(yù)處理.預(yù)處理特征值生成方法：由影響函數(shù)分成3個(gè)特征圖，第1個(gè)特征圖表示黑方的控制范圍，即取值為+1的位置為1，其余為0；第2、第3個(gè)特征圖分別表示白方的控制范圍以及每個(gè)交叉點(diǎn)是否屬于棋子能夠影響到的范圍.通過(guò)以上方法得到的特征值可以更好地輸入DAN網(wǎng)絡(luò)進(jìn)行訓(xùn)練而不會(huì)產(chǎn)生歧義.

2.2 評(píng)估算法中的DAN網(wǎng)絡(luò)

由于傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)是以完整的圖像輸入，生成標(biāo)量化的結(jié)果概率分布，而本算法輸入的特征值是多個(gè)維數(shù)不同的向量，且希望得到的是19×19帶有標(biāo)簽的向量結(jié)果，因此，選取輸入、輸出較為靈活的DAN網(wǎng)絡(luò).

圖3為DAN模型結(jié)構(gòu)，該模型結(jié)構(gòu)圍繞循環(huán)構(gòu)建了一個(gè)代理結(jié)構(gòu).為了避免像傳統(tǒng)蒙特卡洛方法盲目選擇搜索空間，此模型只能通過(guò)前文中的特征值范圍來(lái)觀察可選空間，即去掉了許多冗余的搜索部分，提升了時(shí)間和空間效率.模型總體架構(gòu)包含6個(gè)AL以及2個(gè)FC(全連接層).6個(gè)AL分別具有64、128、256、512、512個(gè)內(nèi)核；兩個(gè)全連接層大小為1 024.將3×3個(gè)內(nèi)核用于6個(gè)AL的卷積層和循環(huán)層，并且在每個(gè)AL后帶有ReLU激活函數(shù)，同時(shí)使用2×2的最大池化層.所有這些卷積層和遞歸層都經(jīng)過(guò)歸一化處理.全連接層之后為ReLU激活函數(shù)和SOFTMAX計(jì)算，最后得到的結(jié)果成為輸出值.其中，非法點(diǎn)在輸入部分設(shè)置為0.

特別地，在訓(xùn)練過(guò)程中，將目標(biāo)函數(shù)J(θ)設(shè)置為

其中：Ep(si:r:θ)為第p層的模型輸出；R為獎(jiǎng)勵(lì)值，比如設(shè)置結(jié)果勝為1，負(fù)為0；si為第p-1層輸出局面；r為第p層輸入坐標(biāo)；θ為第p層實(shí)時(shí)參數(shù).為了避免出現(xiàn)過(guò)擬合問(wèn)題導(dǎo)致參數(shù)難以優(yōu)化，將梯度樣本θJ(θ)近似化為

其中：M表示步數(shù).

3 實(shí)驗(yàn)數(shù)據(jù)及實(shí)驗(yàn)過(guò)程

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)使用兩個(gè)數(shù)據(jù)集進(jìn)行訓(xùn)練和測(cè)試.第1個(gè)數(shù)據(jù)集來(lái)自GoGoD(2015年冬季版)，數(shù)據(jù)包含82 609個(gè)已有棋譜，訓(xùn)練部分以中國(guó)規(guī)則的數(shù)據(jù)為主，包含約70 000個(gè)棋譜.本實(shí)驗(yàn)沒(méi)有選用常用的KGS棋譜數(shù)據(jù)集，原因是該數(shù)據(jù)集中有很多中、低級(jí)別數(shù)據(jù)，影響訓(xùn)練效果.為了充實(shí)數(shù)據(jù)，還收集了一個(gè)新的圍棋數(shù)據(jù)集(PGD)，包含25 000個(gè)專業(yè)棋譜.以上數(shù)據(jù)集格式均為SGF格式.

為了方便實(shí)驗(yàn)，每個(gè)數(shù)據(jù)均由以下幾種變量作為標(biāo)簽訓(xùn)練：DTEVPWWRPBBRRE，分別代表日期、比賽類型、黑棋、白棋、選手名稱、黑棋實(shí)力、結(jié)果.訓(xùn)練網(wǎng)絡(luò)過(guò)程中產(chǎn)生的特征見(jiàn)表1.

表1 訓(xùn)練特征通道

3.2 實(shí)驗(yàn)過(guò)程

在局面評(píng)估系統(tǒng)中，由于只負(fù)責(zé)對(duì)當(dāng)前局面進(jìn)行選點(diǎn)，輸入數(shù)據(jù)為專家系統(tǒng)提供的局面特征，輸出數(shù)據(jù)為下一步要走棋的位置，因此，訓(xùn)練過(guò)程也是以某個(gè)局面作為輸入，下一步走棋位置作為輸出.本文訓(xùn)練中的數(shù)據(jù)集包括大量棋譜信息，如比賽雙方信息、時(shí)間、比賽結(jié)果等等，以及一棵用于表示走棋順序的結(jié)點(diǎn)樹(shù).

訓(xùn)練中，網(wǎng)絡(luò)以訓(xùn)練數(shù)據(jù)的特征作為輸入，并與其標(biāo)簽計(jì)算交叉熵來(lái)迭代訓(xùn)練網(wǎng)絡(luò)，使得參數(shù)最佳.首先將圍棋中的19×19局面視為具有19×19通道的圖像，每個(gè)通道編碼信息由表1數(shù)據(jù)組成.其中，深度適配網(wǎng)絡(luò)部分由1個(gè)標(biāo)準(zhǔn)的卷積層和1個(gè)設(shè)計(jì)的循環(huán)層組成.首先執(zhí)行圖像矩陣的卷積運(yùn)算，從先前的圖層中提取局部鄰域特征，之后在輸出的前一步使用遞歸方法，迭代提高參數(shù)的訓(xùn)練精度.在此過(guò)程中，每個(gè)神經(jīng)元都隨著迭代次數(shù)優(yōu)化.

本文使用Caffe框架實(shí)現(xiàn)深度適配網(wǎng)絡(luò)DAN[6].作為目前深度學(xué)習(xí)常用框架，Caffe框架訓(xùn)練方便，可用多種語(yǔ)音調(diào)用.本文采用Python語(yǔ)言調(diào)用Caffe框架，完成深度適配網(wǎng)絡(luò)訓(xùn)練.棋步產(chǎn)生即等價(jià)于調(diào)用1次前向算法，利用Python語(yǔ)言實(shí)現(xiàn)前向算法.在交互過(guò)程中，當(dāng)輪到計(jì)算機(jī)落子時(shí)，界面模塊通過(guò)系統(tǒng)調(diào)用Python前向算法，并返回1個(gè)走棋位置.在訓(xùn)練過(guò)程中，本文分別嘗試了訓(xùn)練3層、5層和8層深度適配網(wǎng)絡(luò)，在保證收斂的情況下努力嘗試提高神經(jīng)網(wǎng)絡(luò)的泛化能力，最終確定使用8層深度適配網(wǎng)絡(luò)作為棋步產(chǎn)生引擎.

圖4為本實(shí)驗(yàn)中網(wǎng)絡(luò)針對(duì)兩個(gè)數(shù)據(jù)集迭代過(guò)程中精確度的變化情況.由圖4可知：兩個(gè)數(shù)據(jù)集的精度都在網(wǎng)絡(luò)迭代次數(shù)為190～210區(qū)間達(dá)到峰值，之后隨著迭代次數(shù)的增加產(chǎn)生過(guò)擬合現(xiàn)象，導(dǎo)致精度下降.

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

由圖4可知，本文實(shí)驗(yàn)中的神經(jīng)網(wǎng)絡(luò)在面對(duì)高維數(shù)據(jù)(比如上萬(wàn)次大數(shù)據(jù))時(shí)，沒(méi)有出現(xiàn)大幅跌宕，非常理想地呈現(xiàn)出精度隨著迭代次數(shù)先上升再下降的規(guī)律，尤其是在PGD數(shù)據(jù)上表現(xiàn)更為優(yōu)秀.由此表明，使用影響函數(shù)和專家系統(tǒng)為神經(jīng)網(wǎng)絡(luò)提供特征值的方法，有效避免了精度跌宕的問(wèn)題，更好地進(jìn)行了神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化，解決了當(dāng)前直接使用神經(jīng)網(wǎng)絡(luò)訓(xùn)練造成結(jié)果大幅度震蕩、參數(shù)無(wú)法收斂的問(wèn)題.

為了使結(jié)果更加直觀，本實(shí)驗(yàn)進(jìn)行了算法可視化，結(jié)果見(jiàn)圖5.由圖5可見(jiàn)：在進(jìn)行價(jià)值評(píng)估時(shí)，通過(guò)局面評(píng)估(如分塊、形勢(shì)判斷等等)給出了基于專家系統(tǒng)的幾個(gè)選點(diǎn)(紅色標(biāo)記).其中，圖5 a左上1/4棋盤(pán)更多地利用了專家系統(tǒng)中的定式庫(kù)，下1/2盤(pán)則更多地利用了棋局本身的特征；由于棋局復(fù)雜，圖5 b給出了更多的候選點(diǎn)，這些候選點(diǎn)更多地由分塊的價(jià)值評(píng)估得出.可視化結(jié)果進(jìn)一步表明了專家系統(tǒng)和影響函數(shù)在選取特征值時(shí)的作用，在輸入特征值后，DAN網(wǎng)絡(luò)可以給出較好的評(píng)估結(jié)果.

4 小 結(jié)

本文針對(duì)傳統(tǒng)圍棋人工智能中使用蒙特卡洛方法、傳統(tǒng)專家系統(tǒng)以及單純?nèi)斯ど窠?jīng)網(wǎng)絡(luò)中對(duì)局面判斷的不足，提出基于價(jià)值評(píng)估——利用影響函數(shù)、模式庫(kù)產(chǎn)生特征值，將特征值傳遞給DAN網(wǎng)絡(luò)來(lái)搭建圍棋局面判斷模型，解決了傳統(tǒng)局面對(duì)“勢(shì)力”等隱形價(jià)值評(píng)估不準(zhǔn)確，單純?nèi)斯ど窠?jīng)網(wǎng)絡(luò)耗時(shí)長(zhǎng)、訓(xùn)練難度大的問(wèn)題.實(shí)驗(yàn)證明，本文算法無(wú)須在大型且深入的搜索空間中進(jìn)行交互訓(xùn)練(只需要200次左右的迭代)就可以得到相對(duì)較好的評(píng)估結(jié)果.下一步將改進(jìn)神經(jīng)網(wǎng)絡(luò)部分結(jié)構(gòu)進(jìn)行落子預(yù)測(cè)，更精確地進(jìn)行形勢(shì)判斷.比如，可以利用在計(jì)算機(jī)視覺(jué)中表現(xiàn)較好的殘差網(wǎng)絡(luò)，或是豐富現(xiàn)有的專家系統(tǒng)，以及更加豐富的圍棋深度知識(shí)為形勢(shì)判斷提供更加精確的結(jié)果，以提高訓(xùn)練準(zhǔn)確率.