人工智能課程設(shè)計(jì)---五子棋

1、<p><b>　　人工智能課程設(shè)計(jì)</b></p><p>　　--------五子棋</p><p><b>　　一．引言3</b></p><p>　　1.1五子棋簡介3</p><p>　　1.2五子棋的AI構(gòu)想3</p><p>　　二.開發(fā)工具可行

2、性分析5</p><p><b>　　三．需求分析6</b></p><p><b>　　四．程序設(shè)計(jì)6</b></p><p>　　4.1程序設(shè)計(jì)特點(diǎn)6</p><p>　　4.2.程序總體設(shè)計(jì)7</p><p><b>　　五．代碼分析8</b

3、></p><p>　　5.1 初始化賦值系統(tǒng)8</p><p>　　5.2初始化獲勝組合9</p><p>　　5.3重新設(shè)定玩家的獲勝標(biāo)志9</p><p>　　5.4處理鼠標(biāo)事件10</p><p>　　5.5 獲勝檢查算法12</p><p>　　5.6電腦算法(1)1

4、4</p><p>　　5.7電腦算法（2）17</p><p><b>　　六．心得體會(huì)20</b></p><p><b>　　七．參考文獻(xiàn)20</b></p><p><b>　　一．引言</b></p><p>　　人工智能也就是所謂的AI

5、(Artificial Intelligence)，它是一門很抽象的技術(shù)，AI程序的編寫不需要依據(jù)任何既定的思考模式或者規(guī)則。尤其是游戲中的AI可以完全依程序設(shè)計(jì)者本身的思考邏輯制作。我個(gè)人認(rèn)為人工智能的核心應(yīng)該是使計(jì)算機(jī)具有自動(dòng)的處理事件的能力，而我們的所有的研究也應(yīng)該圍繞著這一方向。我們今天討論的是策略類的人工智能。 策略類人工智能可以說是AI中比較復(fù)雜的一種，最常見的策略類AI游戲就是棋盤式游戲。在這類游戲中，通常的策

6、略類AI程序都是使計(jì)算機(jī)判斷目前狀況下所有可走的棋與可能的獲勝狀況，并計(jì)算當(dāng)前計(jì)算機(jī)可走棋步的獲勝分?jǐn)?shù)或者玩家可走棋步的獲勝分?jǐn)?shù)，然后再?zèng)Q定出一個(gè)最佳走法。下面我們先介紹一下五子棋的AI構(gòu)想。 </p><p><b>　　1.1五子棋簡介</b></p><p>　　下面就五子棋的背景和規(guī)則做一些簡單的介紹。</p><p>　　五子棋是起源

7、于中國古代的傳統(tǒng)黑白棋種之一?，F(xiàn)代五子棋日文稱之為“連珠”，英譯為“Renju”，英文稱之為“Gobang”或“FIR”(Five in a Row的縮寫)，亦有“連五子”、“五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱謂。       五子棋不僅能增強(qiáng)思維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性。五子棋既有現(xiàn)代休閑的明顯特征“短、平、快”，又有古典哲學(xué)的高深學(xué)問“

8、陰陽易理”；它既有簡單易學(xué)的特性，為人民群眾所喜聞樂見，又有深?yuàn)W的技巧和高水平的國際性比賽；它的棋文化源淵流長，具有東方的神秘和西方的直觀；既有“場”的概念，亦有“點(diǎn)”的連接。它是中西文化的交流點(diǎn)，是古今哲理的結(jié)晶。</p><p>　　五子棋的規(guī)則如下：棋盤：采用同圍棋盤一樣的15 路或19 路線的棋盤，為了減小問題的規(guī)模，本系統(tǒng)將采用15 路線的棋盤。下法：兩人分別執(zhí)黑白兩色棋子，輪流在棋盤上選擇一個(gè)無子的交

9、叉點(diǎn)落子。無子的交叉點(diǎn)又被稱為空點(diǎn)。輸贏判斷：黑、白雙方有一方的5個(gè)棋子在橫、豎或斜方向上連接成一線即為該方贏。</p><p>　　1.2五子棋的AI構(gòu)想</p><p>　　在由AI所控制的計(jì)算機(jī)玩家上是不成立的，因?yàn)橛?jì)算機(jī)必須知道有那些獲勝方式，并計(jì)算出每下一步棋到棋盤上任一格子的獲勝幾率。</p><p>　　一個(gè)完整的五子棋的AI構(gòu)想必須：</p&g

10、t;<p>　　1、能夠知道所有的獲勝組合</p><p>　　2、建立和使用獲勝表</p><p><b>　　3、設(shè)定獲勝的分?jǐn)?shù)</b></p><p>　　4、使電腦具有攻擊和防守的能力 （一），求五子棋的獲勝組合 在一場五子棋的游戲中，計(jì)算機(jī)必須要知道有那些的獲勝組合，因此我們必須求得獲勝組合的總數(shù)。</

11、p><p>　　我們假定當(dāng)前的棋盤為10*10： </p><p>　　1、計(jì)算水平方向的獲勝組合數(shù)，每一列的獲勝組合是：6，共10列，所以水平方向的獲勝組合數(shù)為：6*10=60 2、計(jì)算垂直方向的獲勝組合總數(shù)，每一行的獲勝組合是：6，共10行，則垂直方向的獲勝組合數(shù)為：6*10=60 3、計(jì)算正對角線方向的獲勝組合總數(shù)，正對角線上的獲勝組合總數(shù)為6+（5+4+3+2+1）*2=36 4

12、、計(jì)算反對角線方向的獲勝組合總數(shù)，反對角線上的獲勝組合總數(shù)為6+（5+4+3+2+1）*2=36  這樣所有的獲勝組合數(shù)為：60+60+36+36=192 （二）、建立和使用獲勝表   我們已經(jīng)計(jì)算出了一個(gè)10*10的五子棋盤會(huì)有192種獲勝方式，這樣我們可以利用數(shù)組建立獲勝表，</p><p>　　獲勝表的主要作用是：</p><p>　　1、判斷當(dāng)前的獲勝

13、方式是否有效；</p><p>　　2、判斷當(dāng)前的獲勝方式中到底有多少子落入該獲勝組合中。詳細(xì)的使用您將在后面的程序中可以看出。 （三）、分?jǐn)?shù)的設(shè)定 在游戲中為了讓計(jì)算機(jī)能夠決定下一步最佳的走法，必須先計(jì)算出計(jì)算機(jī)下到棋盤上任一空格的分?jǐn)?shù)，而其中最高分?jǐn)?shù)便是計(jì)算機(jī)下一步的最佳走法。 原理：我們判定當(dāng)前討論的空格與當(dāng)前討論的點(diǎn)有幾種獲勝的方式，有幾種該空格就加幾分。這種原理初聽起來似乎是無法入手，

14、沒關(guān)系，當(dāng)您了解我們后面的程序后您就會(huì)明白這種決策原理了。 這種決策有一些缺陷，因?yàn)槿绻桓鶕?jù)這個(gè)模型設(shè)計(jì)，就有可能出現(xiàn)電腦或玩家有三個(gè)子連成一線的時(shí)候，計(jì)算機(jī)卻判斷不出，它認(rèn)為其他某些空格是當(dāng)前的獲勝的最佳位置而不去攻擊或防守。沒關(guān)系我們完全可以通過一個(gè)加強(qiáng)算法來改變當(dāng)前的分值情況，也就是說當(dāng)電腦或玩家有三個(gè)子或四個(gè)子連成一線時(shí)，我們通過加強(qiáng)算法將當(dāng)前與三個(gè)子或四個(gè)子有關(guān)的空格的分值提高，從而可以彌補(bǔ)這一缺憾。 （四）、攻擊

15、與防守   以上的方式，事實(shí)上計(jì)算機(jī)只是計(jì)算出了最佳的攻擊位置，為了防守我們還應(yīng)計(jì)算當(dāng)前玩家的最佳的攻擊位置。這樣有什么用呢？道理很簡單，如果玩家最佳攻擊位置的分?jǐn)?shù)大于計(jì)算機(jī)</p><p>　　二.開發(fā)工具可行性分析</p><p>　　本程序采用vb.net開發(fā)工具它是Visual Basic.net的簡稱。提到vb.net，就不能不先提一下Visual Basic是W

16、indows環(huán)境下的一種簡單、易學(xué)的編程語言，由于其開發(fā)程序的快速、高效，深受程序員的喜愛。</p><p>　　VB.NET的特點(diǎn)：</p><p>　　1、真正成為面向?qū)ο笠约爸С掷^承性的語言。2、窗體設(shè)計(jì)器支持可視化繼承，并且包含了許多新的特性，比如自動(dòng)改變窗體大小、資源本地化支持、數(shù)據(jù)類工具內(nèi)在支持XML數(shù)據(jù)。3、直接建立在.NET的框架結(jié)構(gòu)上，因此開發(fā)人員可以充分利用所有.N

17、ET平臺(tái)特性，也可以與其他的.NET語言交互。4、為Windows應(yīng)用程序提供了XCOPY部署，開發(fā)者不再需要為DLL的版本問題擔(dān)憂。 </p><p><b>　　三．需求分析</b></p><p>　　人工智能的第一大成就是下棋程序，在下棋程度中應(yīng)用的某些技術(shù)，如向前看幾步，把困難的問題分解成一些較容易的子問題，發(fā)展成為搜索和問題歸納這樣的人工智能基本技術(shù)。今

18、天的計(jì)算機(jī)程序已能夠達(dá)到下各種方盤棋和國際象棋的錦標(biāo)賽水平。但是，尚未解決包括人類棋手具有的但尚不能明確表達(dá)的能力。如國際象棋大師們洞察棋局的能力。另一個(gè)問題是涉及問題的原概念，在人工智能中叫問題表示的選擇，人們常能找到某種思考問題的方法，從而使求解變易而解決該問題。到目前為止，人工智能程序已能知道如何考慮它們要解決的問題，即搜索解答空間，尋找較優(yōu)解答。 </p><p>　　在設(shè)計(jì)本系統(tǒng)時(shí)考慮到用戶需要的是一個(gè)

19、操作簡便界面簡單的游戲軟件。同時(shí)要提供人機(jī)和人人這樣的功能。特別是人機(jī)部分，要考慮到不同級別的用戶。電腦智能不能太低需要有一定的智能下棋功能。</p><p>　　人機(jī)對戰(zhàn)：選擇和電腦對弈的等級操作，同樣也可以執(zhí)行網(wǎng)絡(luò)聯(lián)機(jī)的悔棋等功能，只是因?yàn)槭侨藱C(jī)所以無需通過確認(rèn)。</p><p><b>　　四．程序設(shè)計(jì)</b></p><p>　　游戲中

20、提供兩種選擇模式：人機(jī)對戰(zhàn)和人人對戰(zhàn)。在人機(jī)對戰(zhàn)中玩家通過選擇不同的等級和電腦一決高下，可以向后悔棋。在人人對戰(zhàn)中雙方通過選擇一方作為服務(wù)器，通過彈出對話框設(shè)置本地應(yīng)用程序監(jiān)聽端口，而另外一方則作為客戶端，通過連接服務(wù)器選項(xiàng)，在彈出的對話框中設(shè)置要連接的服務(wù)器的IP地址和端口號(hào)。當(dāng)雙方都提示連接成功后，兩方才可以進(jìn)行下棋。如要悔棋則需要通過對方的同意。同時(shí)還可以實(shí)現(xiàn)在線聊天。AI的不同等級是以不同的搜索深度確定的。</p>

21、<p><b>　　4.1程序設(shè)計(jì)特點(diǎn)</b></p><p>　　五子棋游戲程序由于規(guī)則簡單操作簡便等特點(diǎn)，自然就成為程序員對人工智能研究的首選對象。所以網(wǎng)絡(luò)上關(guān)于這類的程序很多，但是由于主要都是采用搜索窮舉技術(shù)作為解決方案，這將使得問題的規(guī)模變的很龐大如當(dāng)搜索深度為3時(shí)，每走一步電腦在將最壞的情況下需要搜索的點(diǎn)將達(dá)225*225*225=11390625個(gè)。即使采用的剪枝技術(shù)

22、，其某些點(diǎn)的響應(yīng)的時(shí)間也是讓人無法忍受的，如開局時(shí)，因?yàn)檫@個(gè)時(shí)候每個(gè)點(diǎn)都是空的，沒有可以剪枝的點(diǎn)，必須遍歷真?zhèn)€盤面，所以很耗時(shí)間，大約需要30多秒的時(shí)間，這個(gè)顯然是不可接受的。為了程序設(shè)計(jì)和玩家的忍受時(shí)間的需要。不得不減小深度，所以絕大部分都采用深度為2的檢索，很明顯深度越低系統(tǒng)的智力也相對的降低，需要代價(jià)的。</p><p>　　本程序的一個(gè)主要特點(diǎn)是，采用了高效的優(yōu)化方法，使得在相同的搜索規(guī)模中所花費(fèi)的計(jì)算時(shí)

23、間大幅度的減小。響應(yīng)時(shí)間明顯得到提高。即使搜索深度達(dá)到4的時(shí)候，其響應(yīng)時(shí)間在絕大部分的情況下還是可以接受的。</p><p>　　4.2.程序總體設(shè)計(jì)</p><p>　　結(jié)構(gòu)設(shè)計(jì)的一條基本原理就是程序應(yīng)該模塊化，也就是一個(gè)大程序應(yīng)該由許多規(guī)模適中的模塊按合理的層次結(jié)構(gòu)組織而成?？傮w設(shè)計(jì)階段的第二項(xiàng)主要任務(wù)就是設(shè)計(jì)軟件的結(jié)構(gòu)，也就是確定程序由哪些模塊組成以及模塊間的關(guān)系。通常用層次圖或結(jié)構(gòu)

24、圖描繪軟件的結(jié)構(gòu)。</p><p><b>　　1、系統(tǒng)模型</b></p><p><b>　　選擇操作</b></p><p><b>　　調(diào)用</b></p><p><b>　　2、結(jié)構(gòu)圖</b></p><p><b

25、>　　五．代碼分析</b></p><p>　　這個(gè)階段的任務(wù)還不是編寫程序，而是設(shè)計(jì)出程序的詳細(xì)規(guī)格說明。這種規(guī)格說明的作用很類似于其他工程領(lǐng)域中工程師經(jīng)常使用的工程藍(lán)圖，它們應(yīng)該包含必要的細(xì)節(jié)，程序員可以根據(jù)它們寫出實(shí)際的程序代碼。</p><p>　　下面對該次設(shè)計(jì)中的主要代碼進(jìn)行做個(gè)分析：</p><p>　　5.1 初始化賦值系統(tǒng)<

26、/p><p>　　Sub initplayenvironment() player.FileName = ".\music\zhyu01.mid" player.Play() theplayflag = True //游戲有效  Label1.Vis

27、ible = False //游戲狀態(tài)標(biāo)簽不顯示 PictureBox1.Refresh()   //清空picturebox1的內(nèi)容  yuandian(130, 130)

28、 //調(diào)用繪圖函數(shù)繪制當(dāng)前電腦先走的位置  Dim i, j, m, n As Integer  For i = 0 To 9 For j = 0 To 9  table(i, j) = 

29、0  Next  Next      </p><p>　　//獲勝標(biāo)志初始化 table(4, 4) = 1    //由于我們設(shè)定電腦先手，并下了4，4位所以將其值設(shè)為1 </p>

30、<p>　　5.2初始化獲勝組合  </p><p>　　n = 0 For i = 0 To 9  For j = 0 To 5  For m = 0 To 4  pwin(j

31、 + m, i, n) = True cwin(j + m, i, n) = True  Next  n = n + 1  Next Next For i = 0 To 9  

32、For j = 0 To 5  For m = 0 To 4  pwin(i, j + m, n) = True  cwin(i, j + m, n) = True  Ne

33、xt  n = n + 1  Next  Next  For i = 0 To 5  For j = 0 To 5   For m = 0 To 4  pw

34、in(j + m, i + m, n) = True  cwin(j + m, i + m, n) = True  Next   n = n + 1   Next

35、60;Next </p><p>　　5.3重新設(shè)定玩家的獲勝標(biāo)志</p><p>　　由于電腦已下了4，4位所以我們需要重新設(shè)定玩家的獲勝標(biāo)志 For i = 0 To 5 For j = 9 To 4 Step -1  For m 

36、= 0 To 4  pwin(j - m, i + m, n) = True  cwin(j - m, i + m, n) = True  Next  n = n +

37、60;1  Next  Next For i = 0 To 191  If pwin(4, 4, i) = True Then  pflag(i) = False  End If  Next End Sub<

38、/p><p>　　5.4處理鼠標(biāo)事件 </p><p>　　1、模塊名稱:  themousedown 2、描述:此函數(shù)主要實(shí)行以下功能： （1）判定當(dāng)前游戲標(biāo)志是否有效。 （2）將實(shí)際坐標(biāo)轉(zhuǎn)化成虛擬坐標(biāo)。 （3）繪制玩家的棋子。 （4）執(zhí)行檢查獲勝函數(shù)。 （5）執(zhí)行電腦算法函數(shù)。 Sub themousedown(ByVal x 

39、;As Integer, ByVal y As Integer) If theplayflag = False Then  Exit Sub End If   //檢查游戲狀態(tài)是否有效  Dim i, 

40、;j As Integer  Dim zhx, zhy As Integer zhx = Int((x - 10) / 30) zhy = Int((y - 10) / 30)  For i = 0&#

41、160;To 9  For j = 0 To 9 If table(zhx, zhy) >; 0 Then  Exit Sub  End If  Next  Next       

42、   </p><p>　　5.5 獲勝檢查算法</p><p>　　1、模塊名稱:  checkwin 2、描述: 此模塊執(zhí)行以下功能：（1）檢查是否和棋。 （2）檢查電腦是否獲勝。 （3）檢查玩家是否獲勝。  Sub checkwin() Dim i,

43、0;j, k, m, n As Integer  Dim ca As Integer  Dim pa As Integer  Dim cnormal As Integer = 0 For i = 0 T

44、o 191  If cflag(i) = False Then  cnormal = cnormal + 1 End If Next  If cnormal = 190 Then  Label1.Visible = True

45、Label1.Text = "和棋，請重新開始！"  PictureBox1.Refresh()  theplayflag = False Exit Sub End If //設(shè)定和棋規(guī)則  For i =

46、60;0 To 191  If cflag(i) </p><p>　　End If  Next  Next  If ca = 5 Then   Label1.Visible = True  Label1.Text 

47、;= "電腦獲勝,請重新開始"   PictureBox1.Refresh() theplayflag = False  Exit Sub  End If  End If Next         

48、 //檢查電腦是否獲勝  For i = 0 To 191 If pflag(i) = True Then   pa = 0  For j = 0 To 9  For&#

49、160;k = 0 To 9  If table(j, k) = 2 Then If pwin(j, k, i) = True Then   pa = pa + 1</p><p>　　En

50、d If   End If   Next  Next  If pa = 5 Then  Label1.Visible = True   Label1.Text = "玩家獲勝,請重新開始"  Picture

51、Box1.Refresh()  theplayflag = False  Exit Sub  En End If  Next //檢查玩家是否獲勝  End Sub</p><p>　　5.6電腦算法(1)&

52、lt;/p><p>　　1、模塊名稱:diannao </p><p>　　2描述: 此程序主要執(zhí)行以下功能： （1）初始化賦值系統(tǒng)。 （2）賦值加強(qiáng)算法。 （3）計(jì)算電腦和玩家的最佳攻擊位。 （4）比較電腦和玩家的最佳攻擊位并決定電腦的最佳策略。 （5）執(zhí)行檢查獲勝函數(shù)。  Sub diannao()  Dim i, 

53、j, k, m, n As Integer  Dim dc As Integer  Dim cab As Integer  Dim pab As Integer  For i = 0 To 9 For

54、 j = 0 To 9  pscore(i, j) = 0  cscore(i, j) = 0  Next Next //初始化賦值數(shù)組 For i = 0 To

55、 191  If cflag(i) = True Then  cab = 0  For j = 0 To 9   For k = 0 To 9  If table(j, k)

56、60;= 1 Then  If cwin(j, k, i) = True Then  </p><p>　　5.7電腦算法（2）</p><p>　　1、賦值系統(tǒng) For i = 0 To 191 If cflag

57、(i) = True Then For j = 0 To 9  For k = 0 To 9 If table(j, k) = 0 Then  If cwin(j, k, i) = 

58、True Then  For m = 0 To 9   For n = 0 To 9   If table(m, n) = 1 Then  If cwin(m, n, i) 

59、;= True Then  cscore(j, k) = cscore(j, k) + 1   End If  End If   Next  Next   End If   End If

60、60;Next   Next  End If  Next   For i = 0 To 191  If pflag(i) = True Then   For j = 0 To 9

61、60; For k = 0 To 9  If table(j, k) = 0 Then   If pwin(j, k, i) = True Then  For m =</p><p&g

62、t;<b>　　六．心得體會(huì)</b></p><p>　　這個(gè)課設(shè)題對我來說有一定的挑戰(zhàn)性，因?yàn)槲易约阂膊恢雷约旱降讓W(xué)到了一個(gè)什么樣的境界。但可以肯定，這個(gè)課設(shè)題的要求絕對在我的能力范圍以上。之所以選擇這個(gè)題目是想逼著自己去查更多的資料，學(xué)到更多的東西。結(jié)果也確實(shí)是這樣的，我在這次課設(shè)中學(xué)到了不少東西，也理解了許多原來不理解的東西。盡管做的并不是那么的完善。</p><

63、p>　　總結(jié)這次課設(shè)，我還是收獲不少。雖然遇到了不少的問題，但是我都通過查閱資料把大部分問題都解決了，并且在跟同學(xué)的交流中也學(xué)到了一些他們的設(shè)計(jì)思路，也知道今后要加強(qiáng)哪些方面的知識(shí)。</p><p><b>　　七．參考文獻(xiàn)</b></p><p>　　人工智能研究方法及途徑 熊才權(quán) 2005年第三期</p><p>　　人工智能技術(shù)導(dǎo)論