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

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

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

1 牛角棋博弈軟件設計
1．1 系統總體結構
根據牛角棋博弈系統的功能需求分析，將系統進行模塊劃分，系統總體功能結構如圖1所示。

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