人工智能課程設計報告-五子棋

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

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

3、><p>　　程序運行界面展示 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 7</p><p>　　不足說明 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 8</p><p>　　心得體會 - -

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

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

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

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

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

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

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

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

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

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

14、<p>　?。?）繪制最后落子指示矩形。</p><p>　　3.7 勝負的判斷——Win</p><p>　　這是游戲中一個極其重要的算法，用來判斷當前棋盤的形勢是哪一方獲勝。其詳細內(nèi)容請參見“主要算法”一節(jié)。</p><p>　　3.8 悔棋操作——Back</p><p>　　因為是人機對弈，所以計算機是完全允許玩家悔棋的，

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

16、gt;<p><b>　　圖1</b></p><p>　　這個算法就是Win函數(shù)。從設計的思想上，需要它接受一個棋子的參數(shù)，然后返回一個值，這個值來指示是否勝利，代碼如下：</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>　　需要說明的一點是，由于搜索順序是從左到右、自上而下，因此在每次循環(huán)的時候，都有一些坐標無需納入考慮范圍。例如對于橫向判斷而言，由于右邊界所限，因而所有橫坐標大于等于11的點，都構不成達到五子連的條件，所以橫坐標的循環(huán)上界也就定為11，這樣就提高了搜索的速度。</p><p><

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

26、每個坐標的572種組合給自己的局面和玩家的局面進行打分，也就是根據(jù)當前盤面中某一方所擁有的獲勝組合多少進行權值的估算，給出最有利于自己的一步落子坐標。在每次游戲初始化（Init）的時候，需要將每個坐標下可能的獲勝組合都置為true。</p><p>　　由于是雙方對弈，所以游戲的雙方都需要一份獲勝組合，也就是：</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>　　每當一方落子后，都需要作如下處

28、理：</p><p>　　如果己方此坐標的獲勝組合仍為true，且仍有可能在此獲勝組合處添加棋子，則將此獲勝組合添加棋子數(shù)加1；如果對方此坐標的獲勝組合仍為true，則將對方此坐標的獲勝組合置為false，并將對方此獲勝組合添加棋子數(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>　　在計算機落子之前，需要查找棋盤的空位，所以需要一個SearchBlank成員函數(shù)完成此項工作，此函數(shù)需要進行不重復的查找，也就

31、是說，對已查找過的空位進行標記，并返回找到空位的坐標，其代碼如下：</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>　　找到空位后，需要對這個點的落子進行打分，這個分數(shù)也就是這個坐標重要性的體現(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、 // 計算機下</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>　　如代碼所示，考慮到攻守兩方面的需要，所以將玩家落子給的分數(shù)置為負值。</p><p><b>　　4.6 防守策略</b><

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

44、 // 暫時更改玩家信息</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; // 標記已被查找</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 ) // 此時為玩家下子，運用極</p><p>　　pscore = ptemp;}

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

49、0][temp1[m]] = temp2[m];}</p><p>　　4.7 選取最佳落子</p><p>　　在循環(huán)結束的時候，就可以根據(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>　　程序運行界面展示</b></p><p><b>　　6、不足說明:</b>&

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

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

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