人機博弈作業(yè)

1、2013-2014學年2學期人機博弈程序的實現(xiàn)學 號 姓 名 專 業(yè) 計算機科學與技術 學 院 計算機與信息工程學院 1基于人工智能理論的五子棋人機對弈摘 要人工智能（Artificial Intelligence），英文縮寫為AI。它是研究、開發(fā)用于模擬、延伸和擴展人的智能的理論、方法、技術及應用系統(tǒng)的一門新的技術科學。 人工智能是計算機科學的一個分支，它企圖了解智能的實質(zhì)，并生產(chǎn)出一種新的能以人類智能相似的方式做出反應的智能機器，該領域的研究包括機器人、語言識別、圖像識別、自然語言處理和專家系統(tǒng)等。人工智能是研究、開發(fā)用于模擬、延伸和擴展人的智能的理論、方法、技術及應用系統(tǒng)的一門新的技術科

2、學。人工智能從誕生以來，理論和技術日益成熟，應用領域也不斷擴大，但沒有一個統(tǒng)一的定義。人工智能是對人的意識、思維的信息過程的模擬。人工智能不是人的智能，但能像人那樣思考、也可能超過人的智能。但是這種會自我思考的高級人工智能還需要科學理論和工程上的突破。人工智能是一門極富挑戰(zhàn)性的科學，從事這項工作的人必須懂得計算機知識，心理學和哲學。人工智能是包括十分廣泛的科學，它由不同的領域組成，如機器學習，計算機視覺等等，總的說來，人工智能研究的一個主要目標是使機器能夠勝任一些通常需要人類智能才能完成的復雜工作。但不同的時代、不同的人對這種“復雜工作”的理解是不同的。計算機人機對弈也是其中之一。作為人智能研

3、究的一個重要分支，計算機博弈是檢驗人工水平的一個重要方面。它的研究為人工智能帶來了很多重要的方法和理論，產(chǎn)生了廣泛的社會影響和學術影響。五子棋人機對弈是計算機博弈中的一種。研究其計算機算法，可以讓我們看到人工智能的初影，也有助于我們?nèi)四X的開發(fā)。五子棋是我國發(fā)明的，研究它可以讓更多的外國人了解，有助于我國優(yōu)秀文化的推廣。關鍵詞：人工智能，計算人機對弈，五子棋，算法第一章 概 述當電腦進入我們的生活中，許多與相關學科都欣欣的向上發(fā)展。典型的有電子商務、電子郵件等。當然也有人智能了。人們在驚嘆機器人高效的工作時，也會想起自己聰明的一面。人工智能也這方面也就深受我們喜愛。1.1背景分析五子棋是起源于中

4、國古代的傳統(tǒng)黑白棋種之一?，F(xiàn)代五子棋日文稱之為“連珠”，英譯為“Ren-ju”，英文稱之為“Gobang”或“FIR”(Five in a Row的縮寫)，亦有“連五子”、“五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱謂。五子棋不僅能增強思維能力，提高智力，而且變化多端，非常富有趣味性和消遣性，因此為人民群眾所喜聞樂見。另一方面，人工智能也在最近幾年發(fā)展迅速。人們不斷的研究出機器人之類的，使它能勝任人們能做的一些復雜的事，或是一些人們不適宜做的事，如水下探測等。而隨著人們工作的加大，運動的時間也越來越少，大部分呆在家里或是工作的地方。這樣人們就通過上網(wǎng)、購物等之類的事來取代生活中

5、的不足。當然也有一部分群體在玩游戲之類的了。而五子棋由于其經(jīng)典、易學等。深受人們的喜愛。人們在玩的同時也增加了自己的智慧。1.2 國內(nèi)外現(xiàn)狀國內(nèi)外研究五子棋的算法不少。有遞歸法、二叉樹等。當然我所討論的是一般的算了法。無論何種算法，其大體遵循兩條原則：1.使規(guī)則更加自然流暢，更容易被人接受。2.使棋的內(nèi)容更加豐富多彩。而對于五子棋來說，所面臨的困境歸根結底是來自于其最本質(zhì)的特點，也是目前一切規(guī)則的共同之處：連五終局（注意是連五終局而不一定是連五獲勝，因為連五一方有可能違反長連禁手而被判負）。這個特點產(chǎn)生的結果就是使很多著法絕對化，從而極大地縮減了棋局的變化空間。當別的棋類中的棋子在大多數(shù)時間里

6、都可以在棋盤上自由馳騁時，五子棋的棋子卻經(jīng)常為了應付對方的沖四和活三而不得不疲于奔命。 計算機對不同棋類研究程度的對比很能說明問題；對中象和國象的研究也足可匹敵人類中的頂尖高手；而對五子棋則動輒是“地毯終結”，以摧腐拉朽之勢把這片領域中的未知之處一個又一個無情碾碎。不可否認這也是很多人認為五子棋“簡單低級”的一個重要原因。面對這樣的窘境，有的人提出一種大膽的設想，認為既然“連五終局”是造成五子棋變化簡單的罪魁禍首，那么就應該將其摒棄，用其它的方法比如說看最后誰連五的數(shù)量更多來判定勝負。對于這樣的想法，我認為大家應該以一種開放的心態(tài)去看待，即使是持反對態(tài)度，也要理解提出此類想法的人為了使五子棋更

7、具活力，更加精彩而花費的心思，不要粗暴地給人家扣上一頂“荒誕不經(jīng)”的帽子完事。目前五子棋在規(guī)則方面遇到的困境不是簡單采用某種現(xiàn)行規(guī)則，甚至不是對現(xiàn)行規(guī)則進行一些枝節(jié)上的修改能解決得了的。必須要有大膽的、飛躍性的變革才能使奄奄一息的五子棋有脫胎換骨的變化。至于具體的變革方式，我這個五子棋的門外漢怕是給不出什么像樣的建議，還得靠你們這些內(nèi)行來想辦法。要說實現(xiàn)這一目標的具體方案，最好是能開一個全國乃至全世界范圍內(nèi)的規(guī)則統(tǒng)一大會，列舉出幾種切實可行的全新規(guī)則并經(jīng)過充分討論后，以投票方式選出最終的統(tǒng)一規(guī)則。也許有人覺得這個方案離現(xiàn)實太過遙遠，不過我倒覺得此方案比統(tǒng)一于現(xiàn)有的有禁或無禁方案要現(xiàn)實可行的多，

8、因為如果在目前某派所掌握的規(guī)則下實現(xiàn)統(tǒng)一，另一派會有嚴重的被欺壓和被掠奪感，從而在心理上產(chǎn)生強烈的抗拒。第二章 環(huán)境介紹Visual C+是Microsoft C/C+ 7.0之后推出的新一代程序開發(fā)工具，它不僅繼承C+的特性，同時具備可視化程序語言(Visual Programming Language)及程序產(chǎn)生器的概念。既然是面向?qū)ο笳Z言，當然會提供系統(tǒng)基礎類給程序員再使用(Reuse)。在Visual C+ 中，延襲Microsoft C/C+7.0的作法，將原有的SDK函數(shù)重新封裝在適當?shù)念愔?，構造了“基礎類函數(shù)庫(Microsoft Foundation Class Library

9、,簡稱MFC)”，它提供了許多現(xiàn)成的框架對象，可供在使用Visual C+設計應用程序是使用。此外，還提供“ClassWizard”與“AppWizard”可幫助構造基本的程序框架，從軟件再使用的技術觀點而言，已由SDK函數(shù)庫方式經(jīng)過面向?qū)ο蟪绦蛟O計方式進展到自動產(chǎn)生模板相關類程序代碼方式(Framework)。第三章 系統(tǒng)簡要代碼背景只顯示一次。其代碼如下：CBitmap bj;/存放背景圖CDC membj; /內(nèi)存變量背景membj.CreateCompatibleDC(&dc);/創(chuàng)建相容的內(nèi)存變量bj.LoadBitmap(IDB_BJ); /加載背景圖membj.Selec

10、tObject(&bj); /選擇背景圖/初始時只需顯示一次背景就可if(0=flagbj) /若是左鍵單擊了之后才可重新繪圖,目的是白子只重新繪制一次if(1=flaglb) dc.BitBlt(0,0,700,700,&membj,0,0,SRCCOPY);/置為1表示不再顯示背景flagbj=1;首先要進行初始化，先對棋盤及分數(shù)進行初始化。/0表示無棋子，1表示為電腦的棋子，2表示為玩家的棋子for(i=0;i<19;i+)for(j=0;j<19;j+)pscoreij=0;/玩家各得分為0cscoreij=0;/電腦各得分為0boradij=0;/各空格置

11、為無子 /各獲勝組合中的棋子數(shù)為0for(k=0;k<1020;k+)wcount0k=0;/電腦獲勝組合數(shù)的個數(shù)wcount1k=0;/玩家獲勝組合數(shù)的個數(shù)然后要對獲勝組合進行初始化。/初始時各種獲勝組合中的值都為falsefor(i=0;i<19;i+)for(j=0;j<19;j+)for(k=0;k<1020;k+)cmpijk=false;plyijk=false;/行的組合情況，count的初始值為0for(i=0;i<19;i+)for(j=0;j<15;j+)for(k=0;k<5;k+) cmpij+kcount=true; plyi

12、j+kcount=true;count+;/列的組合情況for(i=0;i<15;i+)for(j=0;j<19;j+)for(k=0;k<5;k+) cmpi+kjcount=true; plyi+kjcount=true;count+;/正斜的組合情況for(i=0;i<15;i+)for(j=0;j<15;j+)for(k=0;k<5;k+)cmpi+kj+kcount=true;plyi+kj+kcount=true;count+;/反斜的組合情況for(i=0;i<15;i+)for(j=18;j>=4;j-)for(k=0;k<

13、5;k+)cmpi+kj-kcount=true;plyi+kj-kcount=true;count+;進行初始化后，此時start、bply置為ture，bcmp置為false。即對每一種獲勝組合中的情況進行初始化。之后游戲開始，玩家可下子，電腦不可下子。先玩家下子，轉(zhuǎn)入到系統(tǒng)函數(shù)OnLButtonDown()。如下所示void mainFrame:OnLButtonDown(UINT nFlags, CPoint point) /玩家單擊時的動作if(start&&bply)/若開始后且輪到玩家下子則進行判斷if(point.x>=38&&point.

14、y&&point.x<=602&&point.y<=602) mp=(int)floor(point.x-36)/30);np=(int)floor(point.y-36)/30);/空格才可下子if(0=boradmpnp) /置為玩家的子boradmpnp=2;for(k=0;k<1020;k+)/玩家子個數(shù)加1if(-1!=wcount1k&&plympnpk)wcount1k+;/電腦置為不可能獲勝if(cmpmpnpk)cmpmpnpk=false;wcount0k=-1;flaglb=1;/玩家下子了可以貼白子 與t

15、ishi中的flaglb形成合作關系bply=false;/玩家不可下子bcmp=true;/電腦可以下子CFrameWnd:OnLButtonDown(nFlags, point);在此函數(shù)中，首先要判斷下子的位置是否在五子棋的棋盤區(qū)域中。即使其成立point.x>=38&&point.y&&point.x<=602&&point.y<=602。若在區(qū)域中，就調(diào)用了系統(tǒng)中的函數(shù)floor()，用于對鍵單擊時的位置取整，來得到單擊進的位置。之后還要判斷所下了位置是否是空子，若是空子才可下子。若為空，則此格即為玩家的子，borad

16、的值置為2（2表示為玩家的子）。玩家下子后，電腦的布局就要改變。這時對1020種獲勝情況一一來進行討論。若是玩家的子且在此獲勝組合中有可能獲勝，則wcount1中的個數(shù)加一，若是電腦的獲勝組合中也為true，則此時wcount0置為-1，表示在此獲勝組合中不可能獲勝,并把對應的cmp的值置為false,表示電腦在此獲勝組合中不可能獲勝。玩家下完之后，此時就輪到電腦下子了。bply置為true，bcmp置為false，表示玩家下完之后是電腦下子。玩家下完之后，這時就是輪到電腦下子。但在下子前判斷下當前的狀況。先貼子。/玩家下完之后就重新貼子for(i=0;i<19;i+)for(j=0;j

17、<19;j+)/電腦為紅子if(1=boradij)dc.BitBlt(i*30+36,j*30+36,24,24,&memcs,0,0,SRCCOPY);/ 玩家為綠子if(2=boradij)dc.BitBlt(i*30+36,j*30+36,24,24,&memps,0,0,SRCCOPY);剛剛玩家下完之后，只是內(nèi)部的置為玩家的子，但是用戶沒有看到。此時若顯示出來，則可了解到玩家的子確實下了。這時電腦就進入了計算階段。這也是此系統(tǒng)的核心代碼。此函數(shù)放置在OnTimer（）中。如下所示：/是否和棋tie=tieGame();if(tie&&start

18、)start=false;/游戲結束 bcmp=false;/電腦不可下子 bply=false;/玩家不檔下子MessageBox("朋友，水平不錯，竟能與電腦和棋哦n(按F1開始，F(xiàn)12退出！)");flagbj=0;/重新顯示背景圖片/是否電腦獲勝cwin=cmpGame();if(cwin&&start) start=false;/游戲結束 bcmp=false;/電腦不可下子 bply=false;/玩家不檔下子MessageBox("朋友,失敗乃成功之母，請再接再勵!n(按F1開始，F(xiàn)12退出！)");flagbj=0;/重新

19、顯示背景圖片/是否玩家獲勝pwin=plyGame();if(pwin&&start) start=false;/游戲結束 bcmp=false;/電腦不可下子 bply=false;/玩家不檔下子MessageBox("朋友，真牛！一下就贏了，要不收我作徒弟吧n(按F1開始，F(xiàn)12退出！)");flagbj=0;/重新顯示背景圖片先判斷是否是和棋，若是則暫停程序。當然在此，判斷和棋，我是調(diào)用了和棋的函數(shù)tieGame()。其內(nèi)容如下：BOOL mainFrame:tieGame()/若有空格則不為和棋for(i=0;i<19;i+)for(j=0;j

20、<19;j+)if(0=boradij) return false;/若有一方勝也不為和棋for(k=0;k<1020;k+)if(5=wcount0k|5=wcount1k) return false;/否則為和棋return true;要討論19X19格了中的每一個格子。若每一個格子都不為空，即borad!=0,并且在獲勝組合中沒有一方獲勝，則此時電腦即為和棋，返回true，否則都為false。這樣就可實現(xiàn)和棋的判斷了。若是和棋，則此時start置為flase，表示游戲暫時停止。并彈出對話框顯示和棋。若不為和棋，則判斷是否是電腦獲勝，其也調(diào)用判斷電腦獲勝的函數(shù)cmpGame()

21、，其內(nèi)容如下：/是否玩家獲勝BOOL mainFrame:plyGame()for(k=0;k<1020;k+)if(5=wcount1k)/有五子棋相連則獲勝return true;return false;其實也挺容易的，只要看下wcount1中是否有一種情況中的個數(shù)為5，若有此時就返回true，否則返回flase。若是電腦獲勝，則也彈出對話框顯示電腦獲勝。這之后便把start也置為false。若電腦不獲勝，則繼續(xù)判斷是否玩家獲勝，此時同樣調(diào)用函數(shù)cmpGame()來處理。如下所示：BOOL mainFrame:cmpGame()for(k=0;k<1020;k+)if(5=wcount0k)/有五子棋相連則獲勝return true;return false;若在電腦的獲勝組合中有一個組合的個數(shù)為5，則電腦獲勝，這時就彈出對話框，