基于牛角棋的博弈電路系統(tǒng)設(shè)計(jì)

摘要：機(jī)器博弈是人工智能領(lǐng)域的重要應(yīng)用之一。以牛角棋博弈為載體，介紹了人機(jī)博弈系統(tǒng)中機(jī)器博弈引擎和人機(jī)接口的設(shè)計(jì)思想，重點(diǎn)論述了招法生成模塊、搜索控制模塊和局面評(píng)估模塊在SoPC系統(tǒng)中的實(shí)現(xiàn)方案。在基于NiosⅡ設(shè)計(jì)的SoPC系統(tǒng)中實(shí)現(xiàn)了固定深度的深度優(yōu)先的負(fù)極大值算法并且使用α-β剪枝技術(shù)對(duì)博弈樹進(jìn)行優(yōu)化。實(shí)驗(yàn)結(jié)果表明所設(shè)計(jì)的博弈電路系統(tǒng)實(shí)現(xiàn)了牛角棋人機(jī)博弈功能，機(jī)器給出招法的時(shí)間和效果達(dá)到高水平博弈棋手的水準(zhǔn)。
關(guān)鍵詞：牛角棋；機(jī)器博弈；片上可編程系統(tǒng)；人工智能

0 引言
    機(jī)器博弈是人工智能學(xué)科的一個(gè)重要研究方向，被稱為人工智能領(lǐng)域的“果蠅”，是檢驗(yàn)人工智能發(fā)展水平的一個(gè)重要方面。國內(nèi)外研究專用博弈集成電路系統(tǒng)的成果還較少，基本上都是采用高性能或多CPU的計(jì)算機(jī)來實(shí)現(xiàn)，使系統(tǒng)像大型服務(wù)器那樣龐大。因此，本文以牛角棋為載體，進(jìn)行機(jī)器博弈算法硬件實(shí)現(xiàn)技術(shù)的研究，使用片上可編程系統(tǒng)(System on a Programmable Chip，SoPC)開發(fā)了完整的牛角棋的雙人博弈系統(tǒng)。進(jìn)而為開發(fā)體積小、實(shí)時(shí)性能高的機(jī)器博弈專用硬件板卡系統(tǒng)進(jìn)行探索。

1 牛角棋博弈軟件設(shè)計(jì)
1．1 系統(tǒng)總體結(jié)構(gòu)
    根據(jù)牛角棋博弈系統(tǒng)的功能需求分析，將系統(tǒng)進(jìn)行模塊劃分，系統(tǒng)總體功能結(jié)構(gòu)如圖1所示。

1．2 招法生成
    招法生成模塊提供了在局面中選出所有可行招法的功能，從而為正確地展開博弈樹提供了支持。
1．2．1 牛角棋的數(shù)字化描述
    為了讓計(jì)算機(jī)下棋，首先就要將所有的棋局元素，包括棋盤、棋子、棋局、著法、規(guī)則、知識(shí)等通過數(shù)字化(編碼)成為數(shù)據(jù)元素，而各種數(shù)據(jù)元素再以特定的關(guān)系構(gòu)成相應(yīng)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)和處理。
    牛角棋的棋盤和棋子編碼如圖2所示。12個(gè)棋位編碼為0～11，紅子用0表示，兩黑子分別用1和2表示。這樣初始棋局便可有兩種形式的表示：
    (1)棋位向量(0，-1，-1，-1，-1，-1，-1，-1，-1，-1，1，2)；
    (2)棋子向量(11，10，0)。

[!--empirenews.page--]
1．2．2 招法的形式化描述
    用表示紅藍(lán)3枚棋子在第n步時(shí)的棋位，第n步時(shí)刻的棋位向量的形式化描述為狀態(tài)Sn：
    
    式中qn+1為第n+1時(shí)刻的招法。
    由于紅子走子方向不受限制，可上可下，可橫走，只能走向空位，不得跳躍。所以紅方棋子可以表述為：
    
    藍(lán)方的棋子走棋方向受到限制，只能上不能下，可以橫走，只能走向空位，不得跳躍。故藍(lán)方的兩枚棋子可以描述為：
    
1．2．3 預(yù)置表招法生成
    預(yù)置表可看作一個(gè)可快速檢索到滿足某些簡單條件的、預(yù)先生成的招法列表的知識(shí)庫。
    對(duì)照?qǐng)D2棋盤的編碼方式，參照牛角棋的規(guī)則，一種預(yù)置招法表的設(shè)計(jì)方案如圖3所示。

    preTable是三維的預(yù)置表，其中的兩個(gè)高維度分別代表了2個(gè)條件：
    (1)棋子的顏色是什么；
    (2)棋子處在什么位置上。
    在明確上述兩個(gè)條件的具體值之后，就可以獲得全部可行著法的列表。由于預(yù)置表是頻繁訪問的數(shù)據(jù)，所以，預(yù)置表占用的空間不應(yīng)太大，而且執(zhí)行時(shí)應(yīng)以能夠載入內(nèi)存為宜，所以針對(duì)具體棋類還須因地制宜地采用一些技巧。
1．3 搜索控制
    在解決機(jī)器博弈問題中，搜索是機(jī)器博弈的核心，他控制著系統(tǒng)各個(gè)模塊的調(diào)用，他效率的高低直接影響搜索的速度，是決定整個(gè)博弈系統(tǒng)棋力高低的首要因素。
    首先，他調(diào)用招法生成模塊，對(duì)當(dāng)前局面產(chǎn)生所有可能的招法并將產(chǎn)生的招法保存到招法列表中。然后，判斷當(dāng)前局面是否有獲勝方，如果有獲勝方返回當(dāng)前局面的估值；否則再判斷是否是葉子節(jié)點(diǎn)，如果是葉子節(jié)點(diǎn)，調(diào)用估值模塊對(duì)當(dāng)前局面進(jìn)行估值并將其返回；如果不是葉子節(jié)點(diǎn)則按照當(dāng)前招法走一步棋并且調(diào)用自身將剛生成的節(jié)點(diǎn)展開，此過程一直持續(xù)下去直到分出勝負(fù)或者搜索到葉子節(jié)點(diǎn)。接著，按照走法將當(dāng)前局面撤銷，退到?jīng)]有走棋時(shí)的局面。然后判斷是否需要剪枝。以上過程反復(fù)執(zhí)行，將龐大的博弈樹一層一層展開以搜索最佳招法，并將其輸出。
    在NiosⅡ系統(tǒng)中，使用遞歸調(diào)用的方式來實(shí)現(xiàn)搜索算法，使用負(fù)極大值算法(Negamax algorithm)，并且采用固定深度的深度優(yōu)先搜索，同時(shí)配合α-β剪枝技術(shù)來搜索最佳招法。
1．4 局面評(píng)估
    對(duì)葉子結(jié)點(diǎn)所對(duì)應(yīng)的局面打分是估值函數(shù)的職責(zé)，通過對(duì)局面的量化值來表示局面的好壞，而博弈樹的其他節(jié)點(diǎn)的值則通過算法從葉子節(jié)點(diǎn)返回得到。函數(shù)的輸入是待評(píng)估的函數(shù)，輸出是一個(gè)數(shù)值。
    博弈樹的葉子結(jié)點(diǎn)是需要調(diào)用估值函數(shù)加以估值的結(jié)點(diǎn)。而博弈樹的中間結(jié)點(diǎn)和根節(jié)點(diǎn)的分值，均可利用極大極小原理從葉子節(jié)點(diǎn)的取值倒推出來。除了殘局階段，搜索樹中的大部分葉子結(jié)點(diǎn)，都是未分勝負(fù)的結(jié)點(diǎn)，需要估值函數(shù)對(duì)該局面做出評(píng)價(jià)，并以數(shù)值的形式反映優(yōu)劣程度。一般地，將所有特征的取值的加權(quán)和作為估值函數(shù)值。局面p的估值函數(shù)V(p)，一般形式如下：
    
    式中：fi表示特征；wi表示權(quán)值。
    需要注意到是，對(duì)于負(fù)極大值算法中葉子節(jié)點(diǎn)的估值必須對(duì)那一方走棋敏感，評(píng)估模塊設(shè)置使能信號(hào)，在搜索狀態(tài)機(jī)發(fā)出評(píng)估使能信號(hào)后，評(píng)估模塊立即對(duì)當(dāng)前局面進(jìn)行評(píng)估并在一定的延時(shí)后返回局面的評(píng)估值。如果評(píng)估使能信號(hào)無效，評(píng)估模塊的輸出保持在高阻態(tài)，不對(duì)局面進(jìn)行評(píng)估。
[!--empirenews.page--]
2 牛角棋博弈系統(tǒng)硬件設(shè)計(jì)
    本系統(tǒng)的處理器為NiosⅡ嵌入式軟核處理器。NiosⅡ是Altera公司提出的數(shù)字系統(tǒng)SoPC解決方案，使得處理器可配置到可編程邏輯器件之中，因此被稱為軟核處理器。NiosⅡ軟核處理器與常見的微控制器相似，它們都是在一個(gè)芯片上包含了處理器、存儲(chǔ)器、以及輸入／輸出電路等功能模塊。相對(duì)于微控制器，NiosⅡ軟核處理器最大的特點(diǎn)為它是一種軟核、可配置的系統(tǒng)。軟核表示處理器的目標(biāo)器件只有在下載設(shè)計(jì)文件后才具備處理器的功能；可配置意味著處理器系統(tǒng)的組成和性能可以根據(jù)需要進(jìn)行調(diào)整。另外，系統(tǒng)還包含計(jì)時(shí)模塊和PLL分頻模塊，硬件系統(tǒng)主要包括NiosⅡ快速型內(nèi)核、SDRAM、三態(tài)橋(tristate bridge)cfi控制器、sysid和并行輸入輸出(pio)。對(duì)系統(tǒng)的各個(gè)模塊添加和配置完成之后，可以使用SoPC Builder自動(dòng)配置各個(gè)模塊的的地址和系統(tǒng)的中斷。

3 測(cè)試結(jié)果
    該設(shè)計(jì)采用的開發(fā)板為A1tera公司的DE2 FPGA開發(fā)板，板上的FPGA為CycloneⅡ系列，芯片的型號(hào)為EP2C35F672C2。
    SoPC系統(tǒng)配置完成以后，在原理圖中將系統(tǒng)各個(gè)模塊的硬件系統(tǒng)進(jìn)行連接，生成硬件系統(tǒng)原理圖。之后，對(duì)系統(tǒng)進(jìn)行綜合、時(shí)序分析等操作，完成硬件系統(tǒng)的調(diào)試。接著對(duì)FPGA的引腳進(jìn)行鎖定，然后將硬件系統(tǒng)全編譯生成FPGA配置文件用于配置FPGA。在使用QuartusⅡ?qū)oPC系統(tǒng)硬件配置到FPGA之后即可在NiosⅡIDE中對(duì)系統(tǒng)的軟件進(jìn)行在線調(diào)試。
    博弈樹的搜索最大層數(shù)設(shè)置為15層，對(duì)系統(tǒng)重新進(jìn)行編譯成功以后將FPGA配置文件和軟件一起下載到FPGA上進(jìn)行驗(yàn)證，圖4為驗(yàn)證過程中的一些局面。其中(a)為游戲開始時(shí)的局面，藍(lán)方2枚棋子和紅方棋子的棋位分別為11，10，0，圖中顯示的是十六進(jìn)制，此時(shí)機(jī)器等待用戶選擇走棋方；(b)為游戲過程中的一個(gè)局面，此時(shí)藍(lán)方2枚棋子和紅方棋子的棋位分別為9，6，4；(c)是游戲結(jié)束時(shí)的局面，此時(shí)紅子被藍(lán)子憋在牛角尖處無法移動(dòng)，藍(lán)方獲勝，LEDG7閃亮。

    在SoPC系統(tǒng)中，設(shè)置的最大搜索層數(shù)為15層。從上面的結(jié)果可以看出，每個(gè)局面搜索時(shí)間最大為2 s，滿足系統(tǒng)設(shè)計(jì)是的性能要求：最大搜索深度大于10層；每個(gè)局面最大搜索時(shí)間最大不超過3 s。針對(duì)系統(tǒng)的智能性和速度方面的測(cè)試結(jié)果如表1所示。選10個(gè)人每人做10次實(shí)驗(yàn)，共計(jì)100次實(shí)驗(yàn)，對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行綜合分析得到數(shù)據(jù)如表1所示。
    從上面結(jié)果可以看出：系統(tǒng)的智能性還有待提高，這主要是為了使系統(tǒng)搜索更快而降低搜索層數(shù)導(dǎo)致的結(jié)果。

4 結(jié)語
    本文以牛角棋的博弈過程為研究載體，論述了機(jī)器博弈系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)過程。實(shí)驗(yàn)結(jié)果表明本文方法具有較好的智能性和實(shí)時(shí)性。隨著現(xiàn)代集成技術(shù)的發(fā)展，F(xiàn)PGA的規(guī)模和速度不斷提高。更加豐富的邏輯資源和嵌入了RAM塊，使得利用FPGA技術(shù)設(shè)計(jì)復(fù)雜度很高的棋類博弈系統(tǒng)(如中國象棋)成為可能。