基于牛角棋的博弈電路系統設計

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

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

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)。