基于牛角棋的博弈電路系統(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è)重要方面。國(guó)內(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)。