鄭歡

摘要：本文基于實(shí)際作品，采用SOPC技術(shù)和Nios II處理器，描述了具有人工智能的人機(jī)博弈系統(tǒng)的設(shè)計(jì)原理和實(shí)現(xiàn)方法。該系統(tǒng)的硬件以DE0-CV開發(fā)板為核心，使用 LTM觸摸屏作為人機(jī)交互設(shè)備，實(shí)現(xiàn)了三子棋和五子棋游戲，使用Verilog語(yǔ)言實(shí)現(xiàn)了包括觸摸屏的顯示驅(qū)動(dòng)在內(nèi)的所有硬件的驅(qū)動(dòng)功能在集成開發(fā)環(huán)境中用C++語(yǔ)言實(shí)現(xiàn)了人機(jī)博弈的軟件算法。核心算法在實(shí)現(xiàn)棋局識(shí)別和策略優(yōu)化的基礎(chǔ)上加入了深度搜索算法，提高了系統(tǒng)的全局思考能力。

關(guān)鍵詞：SOPC；人機(jī)搏弈；五子棋；深度搜索

1、引言

機(jī)器博弈是人工智能領(lǐng)域中一個(gè)重要且具有挑戰(zhàn)性的研究方向之一。它是人工智能的一塊試金石，而棋類游戲又是博弈的一個(gè)標(biāo)準(zhǔn)型問題，其研究成果中的各種搜索算法、模式識(shí)別為人工智能帶來(lái)了很多重要的方法理論。嵌入式系統(tǒng)已經(jīng)廣泛應(yīng)用到國(guó)民經(jīng)濟(jì)的各個(gè)方面?；贜iosII軟核處理器的SOPC技術(shù)憑借其設(shè)計(jì)方式靈活、開發(fā)周期短、可反復(fù)重構(gòu)等特點(diǎn)，日益廣泛應(yīng)用到嵌入式系統(tǒng)開發(fā)中。

基于以上的背景，采用SOPC技術(shù)來(lái)實(shí)現(xiàn)人機(jī)博弈在嵌入式領(lǐng)域的應(yīng)用這種設(shè)計(jì)思想應(yīng)運(yùn)而生。本系統(tǒng)選擇以五子棋的人機(jī)博弈作為設(shè)計(jì)重點(diǎn)，來(lái)闡明基于SOPC的人機(jī)博弈系統(tǒng)的設(shè)計(jì)與開發(fā)過(guò)程。本設(shè)計(jì)采用SOPC技術(shù)和Nios II處理器實(shí)現(xiàn)了機(jī)器博弈在嵌入式系統(tǒng)中的應(yīng)用，這套硬件系統(tǒng)滿足游戲的音效和視覺效果，并具備博弈智能。

2、整體設(shè)計(jì)

2.1本系統(tǒng)實(shí)現(xiàn)了以下功能：

1. LCD屏圖像顯示；

2. 觸摸控制功能；

3. Tictactoe和五子棋兩種棋的人機(jī)博弈；

4. 對(duì)弈有雙人和人機(jī)兩種模式可選；

5 對(duì)弈難度有初級(jí)難度和高級(jí)難度兩種模式可選；

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

2.2系統(tǒng)總體結(jié)構(gòu)

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

1.DE0-CV開發(fā)板以Altera CycloneV 5CEBA4F23C7N FPGA為核心，使用Verilog語(yǔ)言設(shè)計(jì)CPU，觸摸屏、GPIO及語(yǔ)音紅外接口的驅(qū)動(dòng)以及觸摸屏的顯示內(nèi)容，CPU上運(yùn)行軟件算法程序并實(shí)現(xiàn)對(duì)于LTM觸摸屏和音頻模塊的控制

2. LTM觸摸屏模塊：用來(lái)提供人機(jī)交互界面，控制整個(gè)系統(tǒng)的操作，協(xié)調(diào)各部分的功能，是人工博弈系統(tǒng)的核心控制單元。 。

3.語(yǔ)音播放模塊：實(shí)現(xiàn)系統(tǒng)語(yǔ)音提示功能。

3、硬件設(shè)計(jì)

3.1 DE0-CV 開發(fā)板

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

3.2 主控模塊

本設(shè)計(jì)使用Altera Cyclone III EP3C16F484C6N FPGA芯片作為硬件系統(tǒng)的功能平臺(tái)，在該FPGA上面實(shí)現(xiàn)Nios II 軟核CPU配置、觸摸屏的驅(qū)動(dòng)模塊、觸摸屏顯示設(shè)計(jì)、紅外發(fā)射模塊和計(jì)時(shí)器模塊的設(shè)計(jì)等功能。在SOPC Builder中構(gòu)建的Nios II軟核CPU是整個(gè)硬件系統(tǒng)的控制核心，它實(shí)現(xiàn)了控制系統(tǒng)運(yùn)轉(zhuǎn)， 計(jì)時(shí)器開閉，紅外發(fā)射器控制，觸摸屏 顯示和外部輸入信息獲取等功能。

3.3軟件部分

由人機(jī)博弈算法流程圖 4.1可以看出，五子棋機(jī)器博弈的核心就是機(jī)器走棋的算法，本節(jié)將對(duì)本系統(tǒng)實(shí)現(xiàn)的五子棋機(jī)器走棋算法分層介紹，本系統(tǒng)實(shí)現(xiàn)的五子棋機(jī)器走棋的算法主要包括棋盤表示、局面估值、搜索算法、生成走法、界面控制這幾個(gè)部分。

1.棋盤顯示和界面控制

其中棋盤表示和界面控制即交互界面，在LTM觸摸屏上實(shí)現(xiàn)，介于五子棋盤的特點(diǎn)，程序中的棋盤表示是采用15*15二維數(shù)組來(lái)表示的。白子，黑子，空位分別用不同的編碼來(lái)記錄，并加以區(qū)分。

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

由于五子棋機(jī)器博弈每一步下棋的過(guò)程中，局面估分、搜索算法、走法生成這些過(guò)程都是柔和在一起，而不是獨(dú)立分開的過(guò)程，所以本程序也將走法生成、局面估值、搜索算法嵌在一起，構(gòu)成了機(jī)器走棋函數(shù)。本系統(tǒng)的對(duì)弈設(shè)計(jì)了兩種難度的選擇，由兩種走棋函數(shù)來(lái)實(shí)現(xiàn)機(jī)器不同等級(jí)的智能。

初級(jí)難度的機(jī)器走棋函數(shù)只是讓機(jī)器對(duì)目前盤面進(jìn)行分析，選擇最優(yōu)的位置落子。經(jīng)過(guò)對(duì)五子棋知識(shí)深入的研究，以及不斷的下棋來(lái)積累經(jīng)驗(yàn)，使本設(shè)計(jì)能夠?qū)⑽遄悠鍣C(jī)器博弈程序?qū)Ω鞣N棋型的估分做得很完善，使它能夠從盤面“看”出哪一點(diǎn)有利，哪一點(diǎn)不利，并權(quán)衡利、弊的大小，從而選擇出最優(yōu)的落子點(diǎn) 。本文實(shí)現(xiàn)的估值函數(shù)比較完善，所以本系統(tǒng)初級(jí)難度的機(jī)器走棋函數(shù)的效果比較理想。這讓初級(jí)難度的機(jī)器博弈算法對(duì)棋型的判斷和比較比一般的博弈程序更為出色。本算法實(shí)現(xiàn)的高級(jí)難度的機(jī)器走棋函數(shù)讓博弈程序在具有正確評(píng)估局面能力的基礎(chǔ)上，還能夠像人一樣進(jìn)行深層次的思考，推導(dǎo)目前盤面N回合博弈之后的局面，從而及早做出合理的進(jìn)攻和防守策略。

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

本算法的估值函數(shù)在對(duì)黑子和紅子估值時(shí)，對(duì)黑子得到的是正值，對(duì)白子為負(fù)值。

本算法中實(shí)現(xiàn)極大-負(fù)極大算法過(guò)程如下：

1.先對(duì)黑子（機(jī)器）估值，對(duì)初一組N個(gè)極大的值，存為根節(jié)點(diǎn)

2.將這層以上的所有走法的棋子依次下入虛擬棋盤后對(duì)白子（玩家）估值，每次取出N個(gè)節(jié)點(diǎn)

3.不斷重復(fù)1和2 ，直到達(dá)到預(yù)定搜索深度。

以上過(guò)程如下圖所示：

圖4.2中搜索廣度N=3，搜索的深度為3。其中第一層為黑子落子的最好的兩個(gè)點(diǎn)，即取其估分值最大的兩個(gè)點(diǎn)。第二層為在第一層的基礎(chǔ)上，第一層每個(gè)點(diǎn)落子之后，白子最佳的兩個(gè)落子點(diǎn)。第三層為在前兩層的基礎(chǔ)上，第二層中每個(gè)白子落子之后對(duì)應(yīng)黑子的兩個(gè)最佳的走法。

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

參考文獻(xiàn)：

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

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

[3]張志剛.FPGA與SOPC設(shè)計(jì)教程—DE2實(shí)踐.西安電子科技大學(xué)出版社[M].2007.4

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

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

[6]張明亮.一種新的博弈樹搜索算法及其研究應(yīng)用[D].學(xué)位論文.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++ 中國(guó)象棋程序入門與提高[M].電子工業(yè)出版社.2009.5