基于SOPC的人機博弈系統設計與實現

鄭歡

摘要：本文基于實際作品，采用SOPC技術和Nios II處理器，描述了具有人工智能的人機博弈系統的設計原理和實現方法。該系統的硬件以DE0-CV開發板為核心，使用 LTM觸摸屏作為人機交互設備，實現了三子棋和五子棋游戲，使用Verilog語言實現了包括觸摸屏的顯示驅動在內的所有硬件的驅動功能在集成開發環境中用C++語言實現了人機博弈的軟件算法。核心算法在實現棋局識別和策略優化的基礎上加入了深度搜索算法，提高了系統的全局思考能力。

關鍵詞：SOPC；人機搏弈；五子棋；深度搜索

1、引言

機器博弈是人工智能領域中一個重要且具有挑戰性的研究方向之一。它是人工智能的一塊試金石，而棋類游戲又是博弈的一個標準型問題，其研究成果中的各種搜索算法、模式識別為人工智能帶來了很多重要的方法理論。嵌入式系統已經廣泛應用到國民經濟的各個方面?；贜iosII軟核處理器的SOPC技術憑借其設計方式靈活、開發周期短、可反復重構等特點，日益廣泛應用到嵌入式系統開發中。

基于以上的背景，采用SOPC技術來實現人機博弈在嵌入式領域的應用這種設計思想應運而生。本系統選擇以五子棋的人機博弈作為設計重點，來闡明基于SOPC的人機博弈系統的設計與開發過程。本設計采用SOPC技術和Nios II處理器實現了機器博弈在嵌入式系統中的應用，這套硬件系統滿足游戲的音效和視覺效果，并具備博弈智能。

2、整體設計

2.1本系統實現了以下功能：

1. LCD屏圖像顯示；

2. 觸摸控制功能；

3. Tictactoe和五子棋兩種棋的人機博弈；

4. 對弈有雙人和人機兩種模式可選；

5 對弈難度有初級難度和高級難度兩種模式可選；

6. 紅外控制提示音輸出；

2.2系統總體結構

如圖2.1所示，系統總體分為三大模塊：FPGA開發板（DE0-CV）、紅外語音模塊、LTM觸摸屏模塊，其中：

1.DE0-CV開發板以Altera CycloneV 5CEBA4F23C7N FPGA為核心，使用Verilog語言設計CPU，觸摸屏、GPIO及語音紅外接口的驅動以及觸摸屏的顯示內容，CPU上運行軟件算法程序并實現對于LTM觸摸屏和音頻模塊的控制

2. LTM觸摸屏模塊：用來提供人機交互界面，控制整個系統的操作，協調各部分的功能，是人工博弈系統的核心控制單元。 。

3.語音播放模塊：實現系統語音提示功能。

3、硬件設計

3.1 DE0-CV 開發板

DE0 FPGA開發板是臺灣友晶公司開發的一套輕薄型的SOPC開發平臺， DE0搭載了Altera CycloneV 5CEBA4F23C7N FPGA，可提供15，408 LEs（邏輯單元）以及346 I/O，并搭配了豐富的外部接口。

3.2 主控模塊

本設計使用Altera Cyclone III EP3C16F484C6N FPGA芯片作為硬件系統的功能平臺，在該FPGA上面實現Nios II 軟核CPU配置、觸摸屏的驅動模塊、觸摸屏顯示設計、紅外發射模塊和計時器模塊的設計等功能。在SOPC Builder中構建的Nios II軟核CPU是整個硬件系統的控制核心，它實現了控制系統運轉， 計時器開閉，紅外發射器控制，觸摸屏 顯示和外部輸入信息獲取等功能。

3.3軟件部分

由人機博弈算法流程圖 4.1可以看出，五子棋機器博弈的核心就是機器走棋的算法，本節將對本系統實現的五子棋機器走棋算法分層介紹，本系統實現的五子棋機器走棋的算法主要包括棋盤表示、局面估值、搜索算法、生成走法、界面控制這幾個部分。

1.棋盤顯示和界面控制

其中棋盤表示和界面控制即交互界面，在LTM觸摸屏上實現，介于五子棋盤的特點，程序中的棋盤表示是采用15*15二維數組來表示的。白子，黑子，空位分別用不同的編碼來記錄，并加以區分。

2.局面估值、搜索算法、走法生成

由于五子棋機器博弈每一步下棋的過程中，局面估分、搜索算法、走法生成這些過程都是柔和在一起，而不是獨立分開的過程，所以本程序也將走法生成、局面估值、搜索算法嵌在一起，構成了機器走棋函數。本系統的對弈設計了兩種難度的選擇，由兩種走棋函數來實現機器不同等級的智能。

初級難度的機器走棋函數只是讓機器對目前盤面進行分析，選擇最優的位置落子。經過對五子棋知識深入的研究，以及不斷的下棋來積累經驗，使本設計能夠將五子棋機器博弈程序對各種棋型的估分做得很完善，使它能夠從盤面“看”出哪一點有利，哪一點不利，并權衡利、弊的大小，從而選擇出最優的落子點 。本文實現的估值函數比較完善，所以本系統初級難度的機器走棋函數的效果比較理想。這讓初級難度的機器博弈算法對棋型的判斷和比較比一般的博弈程序更為出色。本算法實現的高級難度的機器走棋函數讓博弈程序在具有正確評估局面能力的基礎上，還能夠像人一樣進行深層次的思考，推導目前盤面N回合博弈之后的局面，從而及早做出合理的進攻和防守策略。

極大-負極大值算法是通過極大-極小值算法[6]變換過來，二者是等價的。極大-極小值算法是考慮雙方對弈若干步之后， 從可能的走法中選一步相對好的來走。若最大（Max）節點為甲方下的棋，此時選擇估值最大的點走。 最?。?Min ）節點為乙方下的棋， 此時選擇估值最小的點行走。因此 Min節點的父節點（ Max節點）所賦的倒推值等于端節點估值中的最大值。另一方面， Max節點的父節點（ Min節點） 所賦的倒推值等于端節點估值中的最小值。這樣一級一級地計算倒推值，直至起始節點的后繼節點也被賦以倒推值為止，即從下往上逐層交替使用極小極大的選值方法。這種算法在搜索時將任何機器的弈棋水平都假設為最高，這樣的搜索質量很高，得到的走法也比較合理。極大-負極大值算法則是將原本取Min節點對應的負值取反，就變成了正值，所以原本Min節點是取負的最小值，現在則取正的最大值，這就叫極大-負極大值算法。

本算法的估值函數在對黑子和紅子估值時，對黑子得到的是正值，對白子為負值。

本算法中實現極大-負極大算法過程如下：

1.先對黑子（機器）估值，對初一組N個極大的值，存為根節點

2.將這層以上的所有走法的棋子依次下入虛擬棋盤后對白子（玩家）估值，每次取出N個節點

3.不斷重復1和2 ，直到達到預定搜索深度。

以上過程如下圖所示：

圖4.2中搜索廣度N=3，搜索的深度為3。其中第一層為黑子落子的最好的兩個點，即取其估分值最大的兩個點。第二層為在第一層的基礎上，第一層每個點落子之后，白子最佳的兩個落子點。第三層為在前兩層的基礎上，第二層中每個白子落子之后對應黑子的兩個最佳的走法。

搜索廣度和深度越大，計算越耗時，但經實驗表明機器的博弈智能越高。本系統選取搜索深度為5，廣度為3，經大量的實驗表明，在不耗費很長的計算時間開銷的情況下，博弈算法達到了比較好的智能，較成功的平衡了搜索算法與智能水平之間的矛盾，本文實現的估值函數比較完善，使得該博弈程序能在沒有深度搜索的情況下識別出更多的棋型，這種算法顯著增強了對搜索的質量，在實現同種智能的情況下大大降低了硬件要求，跟有利于機器博弈算發在嵌入式系統中的應用。這也使得本機在沒有深度搜索的情況下，相對于其他的五子棋博弈程序，本系統實現的算法表現更為出色。

參考文獻：

[1]Tictactoe[OL].http：//en.wikipedia.org/wiki/Tic-tac-toe

[2]五子棋[OL]. http：//baike.baidu.com/view/2697.htm

[3]張志剛.FPGA與SOPC設計教程—DE2實踐.西安電子科技大學出版社[M].2007.4

[4]觸摸屏[OL].http：//baike.baidu.com/view/10658.htm

[5]TRDB_LTM_UserGuide_v1.23[OL].http：//www.terasic.com

[6]張明亮.一種新的博弈樹搜索算法及其研究應用[D].學位論文.2007.10

[7]史上最聰明的五子棋[OL].http：//www.4399.com/flash/ 30402.htm

[8]皇冠五子棋[OL].http：//www.xiaoyouxi.cn/down/soft/ 730/ 22701.htm

[9]蔣鵬，雷貽祥，陳圓圓.C/C++ 中國象棋程序入門與提高[M].電子工業出版社.2009.5