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

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

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

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

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