淺談博弈電路系統設計

1 牛角棋博弈軟件設計

1．1 系統總體結構

根據牛角棋博弈系統的功能需求分析，將系統進(jìn)行模塊劃分，系統總體功能結構如圖1所示。

1．2 招法生成

招法生成模塊提供了在局面中選出所有可行招法的功能，從而為正確地展開(kāi)博弈樹(shù)提供了支持。

1．2．1 牛角棋的數字化描述

為了讓計算機下棋，首先就要將所有的棋局元素，包括棋盤(pán)、棋子、棋局、著(zhù)法、規則、知識等通過(guò)數字化(編碼)成為數據元素，而各種數據元素再以特定的關(guān)系構成相應的數據結構進(jìn)行存儲和處理。

牛角棋的棋盤(pán)和棋子編碼如圖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)。

1．2．2 招法的形式化描述

用表示紅藍3枚棋子在第n步時(shí)的棋位，第n步時(shí)刻的棋位向量的形式化描述為狀態(tài)Sn：

式中qn+1為第n+1時(shí)刻的招法。

由于紅子走子方向不受限制，可上可下，可橫走，只能走向空位，不得跳躍。所以紅方棋子可以表述為：

藍方的棋子走棋方向受到限制，只能上不能下，可以橫走，只能走向空位，不得跳躍。故藍方的兩枚棋子可以描述為：

1．2．3 預置表招法生成

預置表可看作一個(gè)可快速檢索到滿(mǎn)足某些簡(jiǎn)單條件的、預先生成的招法列表的知識庫。

對照圖2棋盤(pán)的編碼方式，參照牛角棋的規則，一種預置招法表的設計方案如圖3所示。

preTable是三維的預置表，其中的兩個(gè)高維度分別代表了2個(gè)條件：

(1)棋子的顏色是什么；

(2)棋子處在什么位置上。

在明確上述兩個(gè)條件的具體值之后，就可以獲得全部可行著(zhù)法的列表。由于預置表是頻繁訪(fǎng)問(wèn)的數據，所以，預置表占用的空間不應太大，而且執行時(shí)應以能夠載入內存為宜，所以針對具體棋類(lèi)還須因地制宜地采用一些技巧。

1．3 搜索控制

在解決機器博弈問(wèn)題中，搜索是機器博弈的核心，他控制著(zhù)系統各個(gè)模塊的調用，他效率的高低直接影響搜索的速度，是決定整個(gè)博弈系統棋力高低的首要因素。

首先，他調用招法生成模塊，對當前局面產(chǎn)生所有可能的招法并將產(chǎn)生的招法保存到招法列表中。然后，判斷當前局面是否有獲勝方，如果有獲勝方返回當前局面的估值；否則再判斷是否是葉子節點(diǎn)，如果是葉子節點(diǎn)，調用估值模塊對當前局面進(jìn)行估值并將其返回；如果不是葉子節點(diǎn)則按照當前招法走一步棋并且調用自身將剛生成的節點(diǎn)展開(kāi)，此過(guò)程一直持續下去直到分出勝負或者搜索到葉子節點(diǎn)。接著(zhù)，按照走法將當前局面撤銷(xiāo)，退到?jīng)]有走棋時(shí)的局面。然后判斷是否需要剪枝。以上過(guò)程反復執行，將龐大的博弈樹(shù)一層一層展開(kāi)以搜索最佳招法，并將其輸出。

在NiosⅡ系統中，使用遞歸調用的方式來(lái)實(shí)現搜索算法，使用負極大值算法(Negamax algorithm)，并且采用固定深度的深度優(yōu)先搜索，同時(shí)配合α-β剪枝技術(shù)來(lái)搜索最佳招法。

1．4 局面評估

對葉子結點(diǎn)所對應的局面打分是估值函數的職責，通過(guò)對局面的量化值來(lái)表示局面的好壞，而博弈樹(shù)的其他節點(diǎn)的值則通過(guò)算法從葉子節點(diǎn)返回得到。函數的輸入是待評估的函數，輸出是一個(gè)數值。

博弈樹(shù)的葉子結點(diǎn)是需要調用估值函數加以估值的結點(diǎn)。而博弈樹(shù)的中間結點(diǎn)和根節點(diǎn)的分值，均可利用極大極小原理從葉子節點(diǎn)的取值倒推出來(lái)。除了殘局階段，搜索樹(shù)中的大部分葉子結點(diǎn)，都是未分勝負的結點(diǎn)，需要估值函數對該局面做出評價(jià)，并以數值的形式反映優(yōu)劣程度。一般地，將所有特征的取值的加權和作為估值函數值。局面p的估值函數V(p)，一般形式如下：

式中：fi表示特征；wi表示權值。

需要注意到是，對于負極大值算法中葉子節點(diǎn)的估值必須對那一方走棋敏感，評估模塊設置使能信號，在搜索狀態(tài)機發(fā)出評估使能信號后，評估模塊立即對當前局面進(jìn)行評估并在一定的延時(shí)后返回局面的評估值。如果評估使能信號無(wú)效，評估模塊的輸出保持在高阻態(tài)，不對局面進(jìn)行評估。

2 牛角棋博弈系統硬件設計

本系統的處理器為NiosⅡ嵌入式軟核處理器。NiosⅡ是Altera公司提出的數字系統SoPC解決方案，使得處理器可配置到可編程邏輯器件之中，因此被稱(chēng)為軟核處理器。NiosⅡ軟核處理器與常見(jiàn)的微控制器相似，它們都是在一個(gè)芯片上包含了處理器、存儲器、以及輸入／輸出電路等功能模塊。相對于微控制器，NiosⅡ軟核處理器最大的特點(diǎn)為它是一種軟核、可配置的系統。軟核表示處理器的目標器件只有在下載設計文件后才具備處理器的功能；可配置意味著(zhù)處理器系統的組成和性能可以根據需要進(jìn)行調整。另外，系統還包含計時(shí)模塊和PLL分頻模塊，硬件系統主要包括NiosⅡ快速型內核、SDRAM、三態(tài)橋(tristate bridge)cfi控制器、sysid和并行輸入輸出(pio)。對系統的各個(gè)模塊添加和配置完成之后，可以使用SoPC Builder自動(dòng)配置各個(gè)模塊的的地址和系統的中斷。

3 測試結果

該設計采用的開(kāi)發(fā)板為A1tera公司的DE2 FPGA開(kāi)發(fā)板，板上的FPGA為CycloneⅡ系列，芯片的型號為EP2C35F672C2。

SoPC系統配置完成以后，在原理圖中將系統各個(gè)模塊的硬件系統進(jìn)行連接，生成硬件系統原理圖。之后，對系統進(jìn)行綜合、時(shí)序分析等操作，完成硬件系統的調試。接著(zhù)對FPGA的引腳進(jìn)行鎖定，然后將硬件系統全編譯生成FPGA配置文件用于配置FPGA。在使用QuartusⅡ將SoPC系統硬件配置到FPGA之后即可在NiosⅡIDE中對系統的軟件進(jìn)行