人工智能課程設(shè)計(jì)報(bào)告-五子棋

1、<p><b>　　目 錄</b></p><p>　　五子棋簡(jiǎn)介 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 3</p><p>　　需求分析 - - - - - - - - - - - - - - - - - - - - - - - - - - -

2、 - - - - - - 3</p><p>　　主要名詞說明 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 3</p><p>　　主要算法 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 4</p

3、><p>　　程序運(yùn)行界面展示 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 7</p><p>　　不足說明 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 8</p><p>　　心得體會(huì) - -

4、 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 8</p><p><b>　　1、五子棋簡(jiǎn)介</b></p><p>　　選擇五子棋游戲作為本設(shè)計(jì)的課題，是因?yàn)樵撚螒虻囊?guī)則簡(jiǎn)單，所涉及的方向比較少。這樣才能將問題的重點(diǎn)放在人工智能解決上，而非規(guī)則的解決，有更多的精力放在高效算法

5、的優(yōu)化。希望能通過本次系統(tǒng)的設(shè)計(jì)，整合所學(xué)的知識(shí)，實(shí)現(xiàn)從理論到實(shí)踐上的升華。</p><p>　　五子棋是起源于中國古代的傳統(tǒng)黑白棋種之一?，F(xiàn)代五子棋日文稱之為“連珠”，英譯為“Renju”，英文稱之為“Gobang”或“FIR”(Five in a Row的縮寫)，亦有“連五子”、“五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱謂。它不僅能增強(qiáng)思維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性。五子棋

6、既有現(xiàn)代休閑的明顯特征“短、平、快”，又有古典哲學(xué)的高深學(xué)問“陰陽易理”；它既有簡(jiǎn)單易學(xué)的特性，為人民群眾所喜聞樂見，又有深?yuàn)W的技巧和高水平的國際性比賽；它的棋文化源淵流長，具有東方的神秘和西方的直觀；既有“場(chǎng)”的概念，亦有“點(diǎn)”的連接。它是中西文化的交流點(diǎn)，是古今哲理的結(jié)晶。</p><p><b>　　五子棋的規(guī)則如下：</b></p><p>　　棋盤：采用15

7、×15的棋盤。</p><p>　　下法：兩人分別執(zhí)黑白兩色棋子，輪流在棋盤上選擇一個(gè)無子的交叉點(diǎn)落子。</p><p>　　輸贏判斷：黑、白雙方有一方的5個(gè)棋子在橫、豎或斜方向上連接成一線即為該方贏。</p><p><b>　　2、需求分析</b></p><p>　　作為五子棋的設(shè)計(jì)需要考慮到的最基本的需

8、求莫過于人機(jī)對(duì)戰(zhàn)功能的實(shí)現(xiàn)，當(dāng)然還有下棋過程中的悔棋功能以及判斷游戲的勝負(fù)等方面的要求。當(dāng)然最好是要考慮到界面的友好性，作為一個(gè)娛樂軟件，還應(yīng)該考慮到玩家在游戲時(shí)的舒適性，比如可以考慮加入一些背景音樂和音效。</p><p><b>　　3、主要名詞說明</b></p><p>　　3.1 棋盤數(shù)據(jù)——m_data</p><p>　　這是一個(gè)

9、15*15的二位數(shù)組，用來保存當(dāng)前棋盤的落子數(shù)據(jù)。其中對(duì)于每個(gè)成員來說，0表示落黑子，1表示落白子，-1表示無子。</p><p>　　3.2 清空棋盤——Clear</p><p>　　在每一局游戲開始的時(shí)候都需要調(diào)用這個(gè)函數(shù)將棋盤清空，也就是棋盤的初始化工作。這個(gè)函數(shù)主要將m_data中每一個(gè)落子位都置為無子狀態(tài)（-1）。</p><p>　　3.3 初始化操作

10、——Init</p><p>　　對(duì)于人機(jī)對(duì)弈而言，初始化操作包括以下幾個(gè)步驟：</p><p>　?。?）初始化所有的獲勝組合。</p><p>　　（2）如果是計(jì)算機(jī)先走，則占據(jù)天元（棋盤正中央）的位置。</p><p>　　3.4 繪制棋子——Draw</p><p>　　這是很重要的一個(gè)函數(shù)，它根據(jù)參數(shù)給定的坐

11、標(biāo)和顏色繪制棋子。繪制的詳細(xì)過程如下：</p><p>　?。?）將給定的棋盤坐標(biāo)換算為繪圖的像素坐標(biāo)。</p><p>　　（2）根據(jù)坐標(biāo)繪制棋子位圖。</p><p>　　（3）如果先前曾下過棋子，則利用R2_NOTXORPEN將上一個(gè)繪制棋子上的最后落子指示矩形擦除。</p><p>　　（4）在剛繪制完成的棋子四周繪制最后落子指示矩形

12、。</p><p>　　3.5 左鍵消息——OnLButtonUp</p><p>　　作為棋盤唯一響應(yīng)的左鍵消息，也需要做不少的工作：</p><p>　?。?）如果點(diǎn)擊時(shí)的鼠標(biāo)坐標(biāo)在合法坐標(biāo)(0, 0)～(14, 14)之外，亦禁止落子。</p><p>　?。?）如果走的步數(shù)大于1步，則允許悔棋。</p><p>

13、;　　3.6 繪制棋盤——OnPaint</p><p>　　每當(dāng)WM_PAINT消息觸發(fā)時(shí)，都需要對(duì)棋盤進(jìn)行重繪。OnPaint作為響應(yīng)繪制消息的消息處理函數(shù)使用了雙緩沖技術(shù)，減少了多次繪圖可能導(dǎo)致的圖像閃爍問題。這個(gè)函數(shù)主要完成了以下工作：</p><p>　?。?）裝載棋盤位圖并進(jìn)行繪制。</p><p>　?。?）根據(jù)棋盤數(shù)據(jù)繪制棋子。</p>

14、<p>　?。?）繪制最后落子指示矩形。</p><p>　　3.7 勝負(fù)的判斷——Win</p><p>　　這是游戲中一個(gè)極其重要的算法，用來判斷當(dāng)前棋盤的形勢(shì)是哪一方獲勝。其詳細(xì)內(nèi)容請(qǐng)參見“主要算法”一節(jié)。</p><p>　　3.8 悔棋操作——Back</p><p>　　因?yàn)槭侨藱C(jī)對(duì)弈，所以計(jì)算機(jī)是完全允許玩家悔棋的，

15、但是出于對(duì)程序負(fù)荷的考慮，只允許玩家悔當(dāng)前的兩步棋（計(jì)算機(jī)一步，玩家一步）。</p><p><b>　　4、主要算法</b></p><p><b>　　4.1 判斷勝負(fù)</b></p><p>　　五子棋的勝負(fù)，在于判斷棋盤上是否有一個(gè)點(diǎn)，從這個(gè)點(diǎn)開始的橫豎斜四個(gè)方向是否有連續(xù)的五個(gè)同色棋子出現(xiàn)，如圖1：</p&

16、gt;<p><b>　　圖1</b></p><p>　　這個(gè)算法就是Win函數(shù)。從設(shè)計(jì)的思想上，需要它接受一個(gè)棋子的參數(shù)，然后返回一個(gè)值，這個(gè)值來指示是否勝利，代碼如下：</p><p>　　int x, y; </p><p>　　for ( y = 0; y < 15; y++ )

17、 // 判斷橫向</p><p>　　{for ( x = 0; x < 11; x++ )</p><p>　　{if ( color == m_data[x][y] &&color == m_data[x + 1][y] &&color == m_data[x + 2][y] &&color == m_

18、data[x + 3][y] &&color == m_data[x + 4][y] )</p><p>　　{return TRUE;}}}</p><p>　　for ( y = 0; y < 11; y++ ) // 判斷縱向</p><p>　　{for ( x = 0;

19、 x < 15; x++ )</p><p>　　{if ( color == m_data[x][y] &&color == m_data[x][y + 1] &&color == m_data[x][y + 2] &&color == m_data[x][y + 3] &&color == m_data[x][y + 4] )</p&

20、gt;<p>　　{return TRUE;}}}</p><p>　　for ( y = 0; y < 11; y++ ) // 判斷“\”方向</p><p>　　{for ( x = 0; x < 11; x++ )</p><p>　　{if ( color == m

21、_data[x][y] &&color == m_data[x + 1][y + 1] &&color == m_data[x + 2][y + 2] &&color == m_data[x + 3][y + 3] &&color == m_data[x + 4][y + 4] )</p><p>　　{return TRUE;}}}</p&g

22、t;<p>　　for ( y = 0; y < 11; y++ ) // 判斷“/”方向</p><p>　　{for ( x = 4; x < 15; x++ )</p><p>　　{if ( color == m_data[x][y] &&color == m_data[x

23、- 1][y + 1] &&color == m_data[x - 2][y + 2] &&color == m_data[x - 3][y + 3] &&color == m_data[x - 4][y + 4] )</p><p>　　{return TRUE;}}}</p><p>　　return FALSE;

24、 // 不滿足勝利條件</p><p>　　需要說明的一點(diǎn)是，由于搜索順序是從左到右、自上而下，因此在每次循環(huán)的時(shí)候，都有一些坐標(biāo)無需納入考慮范圍。例如對(duì)于橫向判斷而言，由于右邊界所限，因而所有橫坐標(biāo)大于等于11的點(diǎn)，都構(gòu)不成達(dá)到五子連的條件，所以橫坐標(biāo)的循環(huán)上界也就定為11，這樣就提高了搜索的速度。</p><p><

25、b>　　4.2 獲勝組合</b></p><p>　　獲勝組合是一個(gè)三維數(shù)組，它記錄了所有獲勝的情況。也就是說，參考于Win中的情況，對(duì)于每一個(gè)落子坐標(biāo)，獲勝的情況一共有15 * 11 * 2 + 11 * 11 * 2 = 572種，而對(duì)于每個(gè)坐標(biāo)的獲勝組合，應(yīng)該設(shè)置一個(gè)[15][15][572]大小的三維數(shù)組。</p><p>　　在擁有了這些獲勝組合之后，就可以參照

26、每個(gè)坐標(biāo)的572種組合給自己的局面和玩家的局面進(jìn)行打分，也就是根據(jù)當(dāng)前盤面中某一方所擁有的獲勝組合多少進(jìn)行權(quán)值的估算，給出最有利于自己的一步落子坐標(biāo)。在每次游戲初始化（Init）的時(shí)候，需要將每個(gè)坐標(biāo)下可能的獲勝組合都置為true。</p><p>　　由于是雙方對(duì)弈，所以游戲的雙方都需要一份獲勝組合，也就是：</p><p>　　bool m_Computer[15][15][572];

27、 // 電腦獲勝組合</p><p>　　bool m_Player[15][15][572]; // 玩家獲勝組合</p><p><b>　　4.3 落子后處理</b></p><p>　　每當(dāng)一方落子后，都需要作如下處

28、理：</p><p>　　如果己方此坐標(biāo)的獲勝組合仍為true，且仍有可能在此獲勝組合處添加棋子，則將此獲勝組合添加棋子數(shù)加1；如果對(duì)方此坐標(biāo)的獲勝組合仍為true，則將對(duì)方此坐標(biāo)的獲勝組合置為false，并將對(duì)方此獲勝組合添加棋子數(shù)置為-1。</p><p>　　以玩家落子為例，代碼為：</p><p>　　for ( i = 0; i < 572; i++

29、 )</p><p>　　{if ( m_Player[stepPut.x][stepPut.y][i] &&m_Win[0][i] != -1 ) // 修改狀態(tài)變化</p><p>　　m_Win[0][i]++;</p><p>　　if ( m_Computer[stepPut.x][stepPut.y][i] )</p>

30、;<p>　　{m_Computer[stepPut.x][stepPut.y][i] = false;</p><p>　　m_Win[1][i] = -1;}}</p><p>　　4.4 查找棋盤空位</p><p>　　在計(jì)算機(jī)落子之前，需要查找棋盤的空位，所以需要一個(gè)SearchBlank成員函數(shù)完成此項(xiàng)工作，此函數(shù)需要進(jìn)行不重復(fù)的查找，也就

31、是說，對(duì)已查找過的空位進(jìn)行標(biāo)記，并返回找到空位的坐標(biāo)，其代碼如下：</p><p>　　bool COneGame::SearchBlank( int &i, int &j, int nowTable[][15] )</p><p>　　{int x, y;</p><p>　　for ( x = 0; x < 15; x++ )</p&

32、gt;<p>　　{for ( y = 0; y < 15; y++ )</p><p>　　{if ( nowTable[x][y] == -1 && nowTable[x][y] != 2 )</p><p><b>　　{i = x;</b></p><p><b>　　j = y;</

33、b></p><p>　　return true;}}}</p><p>　　return false;}</p><p><b>　　4.5 落子打分</b></p><p>　　找到空位后，需要對(duì)這個(gè)點(diǎn)的落子進(jìn)行打分，這個(gè)分?jǐn)?shù)也就是這個(gè)坐標(biāo)重要性的體現(xiàn)，代碼如下：</p><p>　　i

34、nt COneGame::GiveScore( const STEP& stepPut )</p><p>　　{int i, nScore = 0;</p><p>　　for ( i = 0; i < 572; i++ )</p><p>　　{if ( m_pTable->GetColor() == stepPut.color )</

35、p><p>　　{if ( m_Player[stepPut.x][stepPut.y][i] ) // 玩家下</p><p>　　{switch ( m_Win[0][i] )</p><p><b>　　{case 1:</b></p><p>　　nScore -= 5;<

36、;/p><p><b>　　break;</b></p><p><b>　　case 2:</b></p><p>　　nScore -= 50;</p><p><b>　　break;</b></p><p><b>　　case 3:<

37、;/b></p><p>　　nScore -= 500;</p><p><b>　　break;</b></p><p><b>　　case 4:</b></p><p>　　nScore -= 5000;</p><p><b>　　break;<

38、;/b></p><p><b>　　default:</b></p><p><b>　　break;}}}</b></p><p><b>　　else</b></p><p>　　{if ( m_Computer[stepPut.x][stepPut.y][i] )

39、 // 計(jì)算機(jī)下</p><p>　　{switch ( m_Win[1][i] )</p><p><b>　　{case 1:</b></p><p>　　nScore += 5;</p><p><b>　　break;</b></p><p

40、><b>　　case 2:</b></p><p>　　nScore += 50;</p><p><b>　　break;</b></p><p><b>　　case 3:</b></p><p>　　nScore += 100;</p><p&

41、gt;<b>　　break;</b></p><p><b>　　case 4:</b></p><p>　　nScore += 10000;</p><p><b>　　break;</b></p><p><b>　　default:</b><

42、/p><p>　　break;}}}}</p><p>　　return nScore;</p><p><b>　　}</b></p><p>　　如代碼所示，考慮到攻守兩方面的需要，所以將玩家落子給的分?jǐn)?shù)置為負(fù)值。</p><p><b>　　4.6 防守策略</b><

43、/p><p>　　落子的考慮不單單要從進(jìn)攻考慮，還要從防守考慮。這一細(xì)節(jié)的實(shí)現(xiàn)其實(shí)就是讓計(jì)算機(jī)從玩家棋盤布局分析戰(zhàn)況，然后找出對(duì)玩家最有利的落子位置。整個(gè)過程如下：</p><p>　　for ( m = 0; m < 572; m++ )</p><p>　　{if ( m_Player[i][j][m] )

44、 // 暫時(shí)更改玩家信息</p><p>　　{temp1[n] = m;</p><p>　　m_Player[i][j][m] = false;</p><p>　　temp2[n] = m_Win[0][m];</p><p>　　m_Win[0][m] = -1;</p><p>&l

45、t;b>　　n++;}}</b></p><p>　　ptempTable[i][j] = 0;</p><p><b>　　pi = i;</b></p><p><b>　　pj = j;</b></p><p>　　while ( SearchBlank( i, j, pte

46、mpTable ) )</p><p>　　{ptempTable[i][j] = 2; // 標(biāo)記已被查找</p><p>　　step.color = m_pTable->GetColor();</p><p>　　step.x = i;</p><p&

47、gt;　　step.y = j;</p><p>　　ptemp = GiveScore( step );</p><p>　　if ( pscore > ptemp ) // 此時(shí)為玩家下子，運(yùn)用極</p><p>　　pscore = ptemp;}

48、 小極大法時(shí)應(yīng)選取最小值</p><p>　　for ( m = 0; m < n; m++ )</p><p>　　{m_Player[pi][pj][temp1[m]] = true; // 恢復(fù)玩家信息</p><p>　　m_Win[

49、0][temp1[m]] = temp2[m];}</p><p>　　4.7 選取最佳落子</p><p>　　在循環(huán)結(jié)束的時(shí)候，就可以根據(jù)攻、守兩方面的打分綜合地考慮落子位置了。代碼如下：</p><p>　　if ( ctemp + pscore > cscore )</p><p>　　{cscore = ctemp + psc

50、ore;</p><p>　　bestx = pi;</p><p>　　besty = pj;}</p><p>　　在這之后，重新改變一下棋盤的狀態(tài)（4.3）即可。</p><p><b>　　程序運(yùn)行界面展示</b></p><p><b>　　6、不足說明:</b>&

51、lt;/p><p>　?。?）由于計(jì)算機(jī)在落子時(shí)選取的是得分最高的一步落子，所以如果玩家在開局的時(shí)候不改變落子步驟，那么將會(huì)獲得從頭至尾相同的棋局。考慮可以在某些步驟上加入隨機(jī)因素，使對(duì)弈過程更具趣味性。</p><p>　?。?）可能的話增加一些背景音樂功能；可以增加保存棋局，以便于調(diào)用觀看。</p><p>　?。?）人機(jī)算法部分中的評(píng)估函數(shù)，也需要調(diào)整使得其更加的

52、智能。算法有個(gè)缺點(diǎn)就是當(dāng)棋盤上的棋子相當(dāng)?shù)臅r(shí)候，比如雙方都存在活三，它會(huì)調(diào)用評(píng)估函數(shù)向前預(yù)測(cè)，算出雙方的值相當(dāng)。于是就不選擇自己連四?？梢哉f這是很大的敗筆，不過可以寫個(gè)函數(shù)進(jìn)行修補(bǔ)。</p><p>　?。?）總體感覺系統(tǒng)可維護(hù)性很差，應(yīng)該盡可能的使用常量代替具體數(shù)據(jù)。這樣更利于后期的維護(hù)，避免牽一發(fā)而動(dòng)全身。</p><p><b>　　心得體會(huì)</b></p

53、><p>　　在剛開始編寫這個(gè)程序的時(shí)候，我幼稚地認(rèn)為其中最重要的是博弈算法。但是頭幾天編寫程序的時(shí)候卻發(fā)現(xiàn)程序越寫越不容易維護(hù)，可見是我走錯(cuò)了方向。后來我向幾位真正的高手討教，他們告訴我：我們的先人早已為我們準(zhǔn)備好了各種精良可用的現(xiàn)成算法，我們所要做的就是拿來主義；但是代碼的組織（架構(gòu)）才是真正的核心部分，因此我們必須在編寫代碼之前選擇一種最為合適的方法來組織這些代碼，否則我們將會(huì)失去很多的時(shí)間和金錢。</p