畢業(yè)論文---五子棋人機(jī)對(duì)弈系統(tǒng)(vc++)

1、<p>　　畢 業(yè) 論 文 （設(shè) 計(jì)）</p><p>　　題 目 五子棋人機(jī)對(duì)弈系統(tǒng) </p><p>　　英文題目 Five chess human-computer system</p><p>　　院 系 信息科學(xué)與技術(shù)學(xué)院 </p><p>　　專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) &l

2、t;/p><p><b>　　二零一零年一月 </b></p><p><b>　　摘 要</b></p><p>　　人工智能是一門正在迅速發(fā)展的新興的，綜合性很強(qiáng)的邊緣科學(xué)。它與生物工程、空間技術(shù)一起被并列為二十一世界三大尖端技術(shù)。它的中心任務(wù)是研究如何使計(jì)算機(jī)去做那些過(guò)去只能靠人的智力才能做的工作。目前各發(fā)達(dá)國(guó)家都把人

3、工智能作為重點(diǎn)列入本車的高科技發(fā)展計(jì)劃當(dāng)中，投入巨大的人力和物力。</p><p>　　計(jì)算機(jī)人機(jī)對(duì)弈也是其中之一。作為人智能研究的一個(gè)重要分支，計(jì)算機(jī)博弈是檢驗(yàn)人工水平的一個(gè)重要方面。它的研究為人工智能帶來(lái)了很多重要的方法和理論，產(chǎn)生了廣泛的社會(huì)影響和學(xué)術(shù)影響。</p><p>　　五子棋人機(jī)對(duì)弈是計(jì)算機(jī)博弈中的一種。研究其計(jì)算機(jī)算法，可以讓我們看到人工智能的初影，也有助于我們?nèi)四X的開(kāi)發(fā)

4、。五子棋是我國(guó)發(fā)明的，研究它可以讓更多的外國(guó)人了解，有助于我國(guó)優(yōu)秀文化的推廣。</p><p>　　[關(guān)鍵詞]：人工智能，計(jì)算人機(jī)對(duì)弈，五子棋，算法</p><p><b>　　Abstract</b></p><p>　　Artificial intelligence is a rapidly developing new, integrat

5、ed a strong Frontier Science. It is with bio-engineering, space technology has been listed as 21 in the world along with the three cutting-edge technology. Its central task is to study how to make the computer do that in

6、 the past to rely on human intelligence to do. AI is currently regarded as the focus of the developed countries included in this car's high-tech development projects invested tremendous human and material resources.

7、 </p><p>　　[KeyWords] ：Artificial intelligence , Man-machine chess computer , </p><p>　　Man-machine chess,algorithm</p><p><b>　　目 錄</b></p><p>　　摘要…………………

8、……………………………………………………………………Ⅰ</p><p>　　Abstract……………………………………………………………………………………Ⅱ</p><p>　　概述………………………………………………………………………………11.1背景分析………………………………………………………………………11.2國(guó)內(nèi)外現(xiàn)狀……………………………………………………………………2&

9、lt;/p><p>　　需求分析…………………………………………………………………………32.1 需求分析……………………………………………………………………32.2 性能需求……………………………………………………………………32.3 系統(tǒng)平臺(tái)需求………………………………………………………………32.4數(shù)據(jù)流圖及數(shù)據(jù)字典………………………………………………………4</p><p>　

10、　總體設(shè)計(jì)…………………………………………………………………………53.1 系統(tǒng)流程圖………………………………………………………………53.2系統(tǒng)分析……………………………………………………………………5</p><p>　　系統(tǒng)實(shí)現(xiàn)…………………………………………………………………………114.1界面實(shí)現(xiàn)……………………………………………………………………114.2智能計(jì)算實(shí)現(xiàn)…………………………………

11、……………………………12</p><p>　　系統(tǒng)維護(hù)………………………………………………………………………305.1 系統(tǒng)測(cè)試……………………………………………………………………305.2 系統(tǒng)維護(hù)……………………………………………………………………31</p><p>　　總結(jié)……………………………………………………………………………31</p><p>

12、　　參考文獻(xiàn)…………………………………………………………………………………33</p><p>　　致謝………………………………………………………………………………………34</p><p><b>　　第一章 概 述</b></p><p>　　當(dāng)電腦進(jìn)入我們的生活中，許多與相關(guān)學(xué)科都欣欣的向上發(fā)展。典型的有電子商務(wù)、電子郵件等。當(dāng)然也有人智

13、能了。人們?cè)隗@嘆機(jī)器人高效的工作時(shí)，也會(huì)想起自己聰明的一面。人工智能也這方面也就深受我們喜愛(ài)。</p><p><b>　　1.1背景分析</b></p><p>　　五子棋是起源于中國(guó)古代的傳統(tǒng)黑白棋種之一?，F(xiàn)代五子棋日文稱之為“連珠”，英譯為“Ren-ju”，英文稱之為“Gobang”或“FIR”(Five in a Row的縮寫)，亦有“連五子”、“五子連”、“

14、串珠”、“五目”、“五目碰”、“五格”等多種稱謂。五子棋不僅能增強(qiáng)思維能力，提高智力，而且變化多端，非常富有趣味性和消遣性，因此為人民群眾所喜聞樂(lè)見(jiàn)。</p><p>　　另一方面，人工智能也在最近幾年發(fā)展迅速。人們不斷的研究出機(jī)器人之類的，使它能勝任人們能做的一些復(fù)雜的事，或是一些人們不適宜做的事，如水下探測(cè)等。而隨著人們工作的加大，運(yùn)動(dòng)的時(shí)間也越來(lái)越少，大部分呆在家里或是工作的地方。這樣人們就通過(guò)上網(wǎng)、購(gòu)物等

15、之類的事來(lái)取代生活中的不足。當(dāng)然也有一部分群體在玩游戲之類的了。而五子棋由于其經(jīng)典、易學(xué)等。深受人們的喜愛(ài)。人們?cè)谕娴耐瑫r(shí)也增加了自己的智慧。</p><p><b>　　1．任務(wù)提出</b></p><p>　　開(kāi)發(fā)者：九江學(xué)院信息科學(xué)與技術(shù)學(xué)院</p><p>　　用戶類型：各類棋牌游戲愛(ài)好者</p><p>　　用

16、戶特點(diǎn)：玩者只要了解五子棋的幾條規(guī)則，能用基本的windows xp操作就能玩此系統(tǒng)。</p><p><b>　　2．系統(tǒng)目標(biāo)</b></p><p>　　系統(tǒng)目標(biāo)是總體設(shè)計(jì)的根據(jù)，是系統(tǒng)具體實(shí)現(xiàn)的前提，本系統(tǒng)將達(dá)到以下目標(biāo)：</p><p>　　(1) 便于一般懂五子棋群體。</p><p><b>　　(

17、2) 便于新手玩</b></p><p><b>　　1.2 國(guó)內(nèi)外現(xiàn)狀</b></p><p>　　國(guó)內(nèi)外研究五子棋的算法不少。有遞歸法、二叉樹(shù)等。當(dāng)然我所討論的是一般的算了法。</p><p>　　無(wú)論何種算法，其大體遵循兩條原則：1.使規(guī)則更加自然流暢，更容易被人接受。2.使棋的內(nèi)容更加豐富多彩。而對(duì)于五子棋來(lái)說(shuō)，所面臨的困境

18、歸根結(jié)底是來(lái)自于其最本質(zhì)的特點(diǎn)，也是目前一切規(guī)則的共同之處：連五終局（注意是連五終局而不一定是連五獲勝，因?yàn)檫B五一方有可能違反長(zhǎng)連禁手而被判負(fù)）。這個(gè)特點(diǎn)產(chǎn)生的結(jié)果就是使很多著法絕對(duì)化，從而極大地縮減了棋局的變化空間。當(dāng)別的棋類中的棋子在大多數(shù)時(shí)間里都可以在棋盤上自由馳騁時(shí)，五子棋的棋子卻經(jīng)常為了應(yīng)付對(duì)方的沖四和活三而不得不疲于奔命。 </p><p>　　計(jì)算機(jī)對(duì)不同棋類研究程度的對(duì)比很能說(shuō)明問(wèn)題；對(duì)中象和國(guó)象

19、的研究也足可匹敵人類中的頂尖高手；而對(duì)五子棋則動(dòng)輒是“地毯終結(jié)”，以摧腐拉朽之勢(shì)把這片領(lǐng)域中的未知之處一個(gè)又一個(gè)無(wú)情碾碎。不可否認(rèn)這也是很多人認(rèn)為五子棋“簡(jiǎn)單低級(jí)”的一個(gè)重要原因。面對(duì)這樣的窘境，有的人提出一種大膽的設(shè)想，認(rèn)為既然“連五終局”是造成五子棋變化簡(jiǎn)單的罪魁禍?zhǔn)祝敲淳蛻?yīng)該將其摒棄，用其它的方法比如說(shuō)看最后誰(shuí)連五的數(shù)量更多來(lái)判定勝負(fù)。對(duì)于這樣的想法，我認(rèn)為大家應(yīng)該以一種開(kāi)放的心態(tài)去看待，即使是持反對(duì)態(tài)度，也要理解提出此類想法的

20、人為了使五子棋更具活力，更加精彩而花費(fèi)的心思，不要粗暴地給人家扣上一頂“荒誕不經(jīng)”的帽子完事。</p><p>　　目前五子棋在規(guī)則方面遇到的困境不是簡(jiǎn)單采用某種現(xiàn)行規(guī)則，甚至不是對(duì)現(xiàn)行規(guī)則進(jìn)行一些枝節(jié)上的修改能解決得了的。必須要有大膽的、飛躍性的變革才能使奄奄一息的五子棋有脫胎換骨的變化。至于具體的變革方式，我這個(gè)五子棋的門外漢怕是給不出什么像樣的建議，還得靠你們這些內(nèi)行來(lái)想辦法。要說(shuō)實(shí)現(xiàn)這一目標(biāo)的具體方案，最

21、好是能開(kāi)一個(gè)全國(guó)乃至全世界范圍內(nèi)的規(guī)則統(tǒng)一大會(huì)，列舉出幾種切實(shí)可行的全新規(guī)則并經(jīng)過(guò)充分討論后，以投票方式選出最終的統(tǒng)一規(guī)則。也許有人覺(jué)得這個(gè)方案離現(xiàn)實(shí)太過(guò)遙遠(yuǎn)，不過(guò)我倒覺(jué)得此方案比統(tǒng)一于現(xiàn)有的有禁或無(wú)禁方案要現(xiàn)實(shí)可行的多，因?yàn)槿绻谀壳澳撑伤莆盏囊?guī)則下實(shí)現(xiàn)統(tǒng)一，另一派會(huì)有嚴(yán)重的被欺壓和被掠奪感，從而在心理上產(chǎn)生強(qiáng)烈的抗拒。</p><p><b>　　第二章 需求分析</b></p

22、><p><b>　　2.1業(yè)務(wù)需求</b></p><p><b>　　使用范圍要求</b></p><p>　　該系統(tǒng)適于游戲愛(ài)好者。</p><p><b>　　2. 功能要求</b></p><p>　　該系統(tǒng)主要有以下功能：</p>

23、<p>　?。?）玩家能與電腦下子</p><p><b>　　（2）適于新手來(lái)玩</b></p><p><b>　　2.2 性能需求</b></p><p>　　雖然系統(tǒng)不大，但要滿足玩家的基本要求，電腦有一定的智能，能給于新手一定的幫助。</p><p>　　2.3 系統(tǒng)平臺(tái)需求&l

24、t;/p><p><b>　　1. 系統(tǒng)開(kāi)發(fā)平臺(tái)</b></p><p>　　操作系統(tǒng)：Windows xp系列</p><p>　　開(kāi)發(fā)工具：Visual C++ 6.0</p><p><b>　　2. 開(kāi)發(fā)環(huán)境介紹</b></p><p>　　Visual C++是Micr

25、osoft C/C++ 7.0之后推出的新一代程序開(kāi)發(fā)工具，它不僅繼承C++的特性，同時(shí)具備可視化程序語(yǔ)言(Visual Programming Language)及程序產(chǎn)生器的概念。既然是面向?qū)ο笳Z(yǔ)言，當(dāng)然會(huì)提供系統(tǒng)基礎(chǔ)類給程序員再使用(Reuse)。在Visual C++ 中，延襲Microsoft C/C++7.0的作法，將原有的SDK函數(shù)重新封裝在適當(dāng)?shù)念愔校瑯?gòu)造了“基礎(chǔ)類函數(shù)庫(kù)(Microsoft Foundation Cla

26、ss Library,簡(jiǎn)稱MFC)”，它提供了許多現(xiàn)成的框架對(duì)象，可供在使用Visual C++設(shè)計(jì)應(yīng)用程序是使用。此外，還提供“ClassWizard”與“AppWizard”可幫助構(gòu)造基本的程序框架，從軟件再使用的技術(shù)觀點(diǎn)而言，已由SDK函數(shù)庫(kù)方式經(jīng)過(guò)面向?qū)ο蟪绦蛟O(shè)計(jì)方式進(jìn)展到自動(dòng)產(chǎn)生模板相關(guān)類程序代碼方式(Framework)。</p><p>　　面向?qū)ο蟮某绦蛟O(shè)計(jì)是一種新型的程序設(shè)計(jì)方法，計(jì)算機(jī)環(huán)境本身

27、就是一個(gè)對(duì)象的集合體，對(duì)象彼此之間通過(guò)消息相互作用，面向?qū)ο蟮某绦蛟O(shè)計(jì)提高了程序的模塊化和可維護(hù)性。面向?qū)ο蟮某绦蛟O(shè)計(jì)有幾個(gè)特點(diǎn)及優(yōu)點(diǎn)。首先，由于對(duì)象包含屬性和方法，因此支持模塊化程序設(shè)計(jì)，而模塊化程序設(shè)計(jì)支持開(kāi)發(fā)的便利性及代碼的可維護(hù)性。</p><p>　　Visual C++ 6.0是Microsoft公司推出的功能最強(qiáng)大、最復(fù)雜的語(yǔ)言產(chǎn)品之一，它是目前為止在Windows環(huán)境下進(jìn)行大型軟件開(kāi)發(fā)的首選。其具

28、有如下特點(diǎn)：</p><p>　　(1)Visual C+ + 的語(yǔ)法符合ANSL C+ + 標(biāo)準(zhǔn)，并在此基礎(chǔ)上針對(duì)Windows操作系統(tǒng)增加了一些語(yǔ)句；</p><p>　　(2)集成了MFC(Microsoft Foundation Class)類庫(kù)，MFC封裝了Windows API函數(shù)和消息，使程序員可以使用MFC高效率地開(kāi)發(fā)各種應(yīng)用程序；</p><p>

29、　　(3)提供了MFC AppWizard，可方便地生成程序框架；</p><p>　　(4)提供了基于MFC的ClassWizard，通過(guò)它可以輕松地完成對(duì)各種MFC類的使用與維護(hù)。</p><p>　　Visual C++ 6.0作為Visual Studio家族中的一員，是Microsoft公司以C++語(yǔ)言為基礎(chǔ)開(kāi)發(fā)的可視化集成開(kāi)發(fā)工具，與其他編程語(yǔ)言Visual Basic 6.0

30、、Visual ForPro等一起，成為廣大程序員喜愛(ài)的開(kāi)發(fā)平臺(tái)。</p><p>　　2.4 數(shù)據(jù)流圖及數(shù)據(jù)字典</p><p>　　由于此系統(tǒng)沒(méi)有數(shù)據(jù)庫(kù)，故沒(méi)有數(shù)據(jù)流與數(shù)據(jù)字典。</p><p><b>　　第三章 總體設(shè)計(jì)</b></p><p>　　經(jīng)過(guò)分析，對(duì)五子棋流程進(jìn)行整理,得出其使用過(guò)程如下:</

31、p><p>　　進(jìn)入系統(tǒng)之后。玩家按F1開(kāi)始游戲，首先是玩家下子，接著電腦下子。一直循環(huán)。在電腦或是玩家下了一個(gè)子后，電腦就計(jì)算一下，是否電腦獲勝或玩家獲勝或是和棋。若有一種情況出現(xiàn)，則暫停游戲顯示出相應(yīng)的結(jié)果。若玩家還想玩，繼續(xù)按F1，若要退出則按F12。在游戲開(kāi)始后，玩家可按F11進(jìn)行智能提示。此按鈕適于新手或是“作弊”的群體。</p><p><b>　　3.1 系統(tǒng)流程圖&l

32、t;/b></p><p>　　程序流程圖如圖3-1所示。首先看到的界面是我們熟悉的棋盤。可看到下面有一行文字。當(dāng)用戶按F1時(shí)，則游戲開(kāi)始，這時(shí)用戶先下子。電腦此時(shí)先根據(jù)算法計(jì)算下，是否和棋，是否電腦獲勝，是否玩家獲勝，若有一種情況發(fā)生，則進(jìn)入暫停階段，此時(shí)下子則無(wú)效，電腦顯示相應(yīng)的結(jié)果，否則電腦就根據(jù)自己的得分算法，計(jì)算出最佳位置。把電腦的子下到最好位置上。電腦下子了后，則電腦繼續(xù)判斷是否和棋，是否電腦獲

33、勝，是否玩家獲勝，若有一種情況發(fā)生，同樣進(jìn)入到暫停階段，顯示相應(yīng)的結(jié)果。若用戶按了F12，則整個(gè)系統(tǒng)退出結(jié)束。若在開(kāi)始后，又按了F11，則顯示提示功能。這對(duì)于新手來(lái)說(shuō)是很好的功能。</p><p><b>　　3.2系統(tǒng)分析</b></p><p>　　在看別人下棋時(shí)，我們常說(shuō)一句“當(dāng)局者迷，旁觀者清”，但這句話對(duì)于AI所控制的計(jì)算機(jī)來(lái)說(shuō)是不正確的。相反，計(jì)算機(jī)必須知

34、道每回合的情況，能夠知道有哪些獲勝的方式，并計(jì)算出下一步棋的位置，判斷當(dāng)前的情況。</p><p>　　A:求得所有獲勝的組合</p><p>　　首先，在一場(chǎng)五子棋的游戲中，計(jì)算機(jī)必須要知道有哪些獲勝的組合，因此必須求得獲勝的組合的總數(shù)，而求出總數(shù)后便可建立一個(gè)數(shù)組?？稍谟螒驁?zhí)行時(shí)判斷勝負(fù)，這個(gè)概念比較復(fù)雜，我們可以在后面的代碼中可看到。</p><p>　　我要

35、做的是19X19的棋盤，獲勝總數(shù)有點(diǎn)多。下面一一來(lái)討論。（以表格作為棋盤，1表示為某一方的子，其中以（i,j）表示第i行第j列的格子，）</p><p>　　計(jì)算水平方向的獲勝組合數(shù)</p><p>　　1 2 3 …… 15 16 17 18 19</p><p>　　可以看

36、到對(duì)于第一行中（1，1），（1，2），（1，3），（1，4），(1,5)這五個(gè)格可以是一個(gè)獲勝組合，而(1,2)，(1,3)，(1,4)，(1,5)，(1,6)這五個(gè)格子也可以組成一個(gè)獲勝組合。這樣一直到最后一種為(1，15)，（1，16），（1，17），（1，18），（1，19）這五個(gè)格子組成一個(gè)獲勝組合。即第一行有15種獲勝的組合?？偟挠?9行?？傻茫瑢?duì)于行中，我們有19X15=285種獲勝組合。</p><p&

37、gt;　　計(jì)算垂直方向的獲勝組合數(shù)</p><p>　　同理對(duì)于垂直的獲勝組合中第一種為第一列的1，2，3，4，5可組成一個(gè)獲勝組合?？偟墨@勝組合也是19X15=285種。</p><p>　　計(jì)算正斜方向的獲勝組合數(shù)</p><p>　　1 2 3 4 5 …… 15 16 17 18

38、 19</p><p>　　在第一行中，則可知（1，1），（2，2），（3，3）,(4,4),(5,5)為一獲勝組合，而(1,3),(2,4)，（3，5），（4，6），（5，7）也是一種獲勝組合。第一行中的最后一種為（1，15），（2，16），（3，17），（4，18），（5，19）?？偟墨@勝組合有15種，而最后一行i只能到15。這樣我們可以計(jì)算得到正斜有15X15=225種。</p><p

39、>　　計(jì)算反斜方向的獲勝組合數(shù)</p><p>　　依據(jù)上一種正斜，同理可推知反斜也有15X15=225種。</p><p>　　由前面的討論中，我們可計(jì)算出19X19表格中五子棋的獲勝種數(shù)。一共有285+285+225+225=1020種獲勝方式。</p><p>　　B:建立一些相應(yīng)的變量</p><p>　　對(duì)此我建立了一個(gè)數(shù)組，

40、如下：</p><p>　　BOOL cmp[19][19][1020]; //電腦的每一顆棋子是否在各個(gè)獲勝組合中</p><p>　　BOOL ply[19][19][1020]; //電腦的每一顆棋子是否在各個(gè)獲勝組合中</p><p>　　int wcount[2][1020]; //電腦與玩家在各個(gè)組合中的棋子個(gè)數(shù)</p>

41、<p>　　(三個(gè)變量的簡(jiǎn)寫來(lái)源cmp:computer ply:player wcount:win count)</p><p>　　如上述討論可知，對(duì)于電腦，若為正斜中的第一種情況，并假定為1020種獲勝組合中的第570種獲勝組合。則其數(shù)組元素值設(shè)定如下：</p><p>　　cmp[0][0][570]=true;</p><p>　　cmp[0][

42、1][570]=flase;</p><p>　　cmp[0][2][570]=false;</p><p><b>　　……</b></p><p>　　cmp[1][0][570]=false;</p><p>　　cmp[1][1][570]=true;</p><p>　　cmp[1][2

43、][570]=false;</p><p><b>　　……</b></p><p>　　cmp[2][2][570]=true;</p><p><b>　　……</b></p><p>　　cmp[3][3][570]=true;</p><p><b>　　…

44、…</b></p><p>　　cmp[4][4][570]=true;</p><p>　　ply[][][]數(shù)組元素的初始化與cmp[][][]是相同的，但若在程序執(zhí)行時(shí)，若玩家的棋占了（0，0）的位置，那么電腦在cmp[0][0][570]元素就會(huì)置為false，因?yàn)橛?jì)算機(jī)就不可能再下到（0，0）上，因此第570種方法中對(duì)電腦來(lái)說(shuō)是不可能的情況了。同理，對(duì)于若是電腦占了（

45、0，0）的位置，則玩家中此獲勝組合中也置為不可能。</p><p>　　wcount[2][1020]用來(lái)記錄玩家或計(jì)算機(jī)在各自的獲勝組合中棋子的個(gè)數(shù)。其中wcount[0][]來(lái)計(jì)算電腦的個(gè)數(shù)，wcount[1][]用來(lái)計(jì)算玩家的個(gè)數(shù)。假如在第570種獲勝組合中填入了3個(gè)電腦的子，則此時(shí)則有wcount[0][570]=3。若在某一時(shí)刻有wcount[][]=5，則此時(shí)即可判定某一方獲勝了。</p>

46、<p><b>　　C：分?jǐn)?shù)的設(shè)定</b></p><p>　　組在游戲中，為了讓電腦找到最佳的走法，必須計(jì)算出電腦下到棋盤中任一格的分?jǐn)?shù)，其中最高分即是電腦下的位置。</p><p>　　如下表所示，為了討論方便，我只畫了一個(gè)10X10的表格（其中C表示電腦的子，P表示玩家的子）</p><p>　　1 2 3

47、4 5 6 7 8 9 10</p><p>　　如上表所示，為什么會(huì)出現(xiàn)在C左邊為0而下面卻為20分呢。</p><p>　　我們看下上面的表格就可知，C的左邊有三個(gè)格，要想獲勝，則必須再加上左右邊的一個(gè)格了，而右邊的一個(gè)格子被電腦占了，因此，此獲勝組合中置為不可能，得分為0。而對(duì)于C下面的格子有四個(gè)獲勝的組合，且每一種組合都可能獲勝，因此每種組合的分?jǐn)?shù)累

48、加，可以得出其分?jǐn)?shù)為20。因此在此棋盤中，最佳位置有四個(gè)。</p><p>　　以上是按每一種獲勝組合為5分的來(lái)計(jì)算的。在每一次運(yùn)行中，電腦都按些種算法，則電腦可以找到最佳的位置。</p><p><b>　　D：攻擊與防守</b></p><p>　　經(jīng)上述討論可知，電腦一直在找自己一方的最佳位置。若玩家在某個(gè)時(shí)刻獲勝了，電腦也在尋找自己的位

49、置。如何才能解決這個(gè)問(wèn)題呢？想想其實(shí)也不難。在下子的過(guò)程中，電腦還必須記下玩家的分?jǐn)?shù)情況，并且計(jì)分方式要一樣。每一次下完之后，電腦便計(jì)分，若是電腦的分?jǐn)?shù)高，則下在已方，反之下在玩家的最佳位置。這樣一來(lái)，電腦也就有了智能了。</p><p><b>　　第四章 系統(tǒng)實(shí)現(xiàn)</b></p><p>　　系統(tǒng)經(jīng)過(guò)分析并加以設(shè)計(jì)，就可以著手進(jìn)行實(shí)現(xiàn)了，本系統(tǒng)主要分為界面實(shí)現(xiàn)和算

50、法實(shí)現(xiàn)。</p><p>　　4.1 界面的實(shí)現(xiàn) </p><p>　　本系統(tǒng)首先印入眼簾的是五子棋的界面。本系統(tǒng)的啟動(dòng)界面窗口如圖4-1所示。</p><p><b>　　圖4-1</b></p><p>　　利用MFC建立一個(gè)MFC工程。在mainFrame的析構(gòu)函數(shù)中，插入下一句代碼：</p>&l

51、t;p>　　Create(NULL,"五子棋",WS_OVERLAPPEDWINDOW&~WS_SIZEBOX&~WS_MAXIMIZEBOX,CRect(0,0,700,700),NULL,NULL,0,NULL);</p><p>　　則此窗口生成的標(biāo)題為“五子棋”，當(dāng)加入了WS_SIZEBOX與WS_MAXIMIZEBOX后，此窗口就不能最大化顯示且不能調(diào)整邊框大小

52、，即一創(chuàng)建的框架為不可改變的大小，另一個(gè)為CRect(0,0,700,700)。此框架的大小為700X700。</p><p>　　窗口創(chuàng)建后就是導(dǎo)入圖片。為此首先導(dǎo)入圖片到工程中，命名為IDB_BJ。要導(dǎo)入一張圖片需要三個(gè)步驟。先要取得設(shè)備的DC。這個(gè)程序是用CClient dc(this)來(lái)取的。為了防止閃爍，我加了一個(gè)標(biāo)記變量flagbj。初始值為0，加載背景之后就置為1。則可知，背景只顯示一次。其代碼如下

53、：</p><p>　　CBitmap bj;//存放背景圖</p><p>　　CDC membj; //內(nèi)存變量背景</p><p>　　membj.CreateCompatibleDC(&dc);//創(chuàng)建相容的內(nèi)存變量</p><p>　　bj.LoadBitmap(IDB_BJ); //加載背景

54、圖</p><p>　　membj.SelectObject(&bj); //選擇背景圖</p><p>　　//初始時(shí)只需顯示一次背景就可</p><p>　　if(0==flagbj) {</p><p>　　//若是左鍵單擊了之后才可重新繪圖,目的是白子只重新繪制一次</p><p>　　i

55、f(1==flaglb) {</p><p>　　dc.BitBlt(0,0,700,700,&membj,0,0,SRCCOPY);</p><p><b>　　}</b></p><p>　　//置為1表示不再顯示背景</p><p><b>　　flagbj=1;</b></p&

56、gt;<p><b>　　}</b></p><p>　　4.2 智能算法實(shí)現(xiàn)</p><p>　　為了計(jì)算得分，在討論之前要聲明幾個(gè)變量和幾個(gè)函數(shù)。</p><p>　　int borad[19][19];//五子棋盤的狀態(tài)。0表示無(wú)棋，1表示為電腦的棋子，2表示為玩家的棋子(borad)</p><p&

57、gt;　　BOOL cmp[19][19][1020];//電腦的獲勝組合情況(computer)</p><p>　　BOOL ply[19][19][1020];//玩家的獲勝組合情況(player)</p><p>　　int wcount[2][1020];//雙方的組合情況中子的個(gè)數(shù),wcount[0][1020]為電腦,wcount[1][1020]為玩家(win

58、count)</p><p>　　int pscore[19][19];//電腦的得分(player score)</p><p>　　int cscore[19][19];//玩家的得分(computer score)</p><p>　　BOOL bcmp;//是否輪到電腦下棋(bool computer)</p><p>

59、　　BOOL bply;//是否輪到玩家下棋(bool computer)</p><p>　　BOOL start;//游戲是否開(kāi)始(start)</p><p>　　BOOL pwin;//電腦是否獲勝(player win)</p><p>　　BOOL cwin;//玩家是否獲勝(computer win)</p>&l

60、t;p>　　BOOL tie;//是否和棋(tie)</p><p>　　BOOL tishi;//是否有智能提示(tishi)</p><p>　　void initGame();//初始化棋盤(initalite game)</p><p>　　void countScore();//計(jì)分函數(shù)(count score)</p>

61、;<p>　　void cmpTurn();//電腦下子算法(computer turn)</p><p>　　BOOL plyGame();//是否玩家獲勝(player game win)</p><p>　　BOOL cmpGame();//是否電腦獲勝(computer game win)</p><p>　　BOOL tie

62、Game();//是否為和棋(tie game)</p><p>　　int topScore();//查找最高分；返回最高分?jǐn)?shù)(top score) //尋找電腦的隨機(jī)位置并保存在mc,nc中(search count) void searchCount(int top,int countTep,int *mc,int *nc);</p><p>　　int countT

63、op(int top);//返回最高分的個(gè)數(shù)(count top score)</p><p>　　首先要進(jìn)行初始化。先對(duì)棋盤及分?jǐn)?shù)進(jìn)行初始化。</p><p>　　//0表示無(wú)棋子，1表示為電腦的棋子，2表示為玩家的棋子</p><p>　　for(i=0;i<19;i++){</p><p>　　for(j=0;j<19;j

64、++){</p><p>　　pscore[i][j]=0;//玩家各得分為0</p><p>　　cscore[i][j]=0;//電腦各得分為0</p><p>　　borad[i][j]=0;//各空格置為無(wú)子 </p><p><b>　　}</b></p><p><b

65、>　　}</b></p><p>　　//各獲勝組合中的棋子數(shù)為0</p><p>　　for(k=0;k<1020;k++){</p><p>　　wcount[0][k]=0;//電腦獲勝組合數(shù)的個(gè)數(shù)</p><p>　　wcount[1][k]=0;//玩家獲勝組合數(shù)的個(gè)數(shù)</p><

66、p><b>　　}</b></p><p>　　然后要對(duì)獲勝組合進(jìn)行初始化。</p><p>　　//初始時(shí)各種獲勝組合中的值都為false</p><p>　　for(i=0;i<19;i++){</p><p>　　for(j=0;j<19;j++){</p><p>　　f

67、or(k=0;k<1020;k++){</p><p>　　cmp[i][j][k]=false;</p><p>　　ply[i][j][k]=false;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b

68、>　　}</b></p><p>　　//行的組合情況，count的初始值為0</p><p>　　for(i=0;i<19;i++){</p><p>　　for(j=0;j<15;j++){</p><p>　　for(k=0;k<5;k++){</p><p>　　cmp[i]

69、[j+k][count]=true;</p><p>　　ply[i][j+k][count]=true;</p><p><b>　　}</b></p><p><b>　　count++;</b></p><p><b>　　}</b></p><p&g

70、t;<b>　　}</b></p><p><b>　　//列的組合情況</b></p><p>　　for(i=0;i<15;i++){</p><p>　　for(j=0;j<19;j++){</p><p>　　for(k=0;k<5;k++){</p><

71、;p>　　cmp[i+k][j][count]=true;</p><p>　　ply[i+k][j][count]=true;</p><p><b>　　}</b></p><p><b>　　count++;</b></p><p><b>　　}</b></

72、p><p><b>　　}</b></p><p><b>　　//正斜的組合情況</b></p><p>　　for(i=0;i<15;i++){</p><p>　　for(j=0;j<15;j++){</p><p>　　for(k=0;k<5;k++){

73、</p><p>　　cmp[i+k][j+k][count]=true;</p><p>　　ply[i+k][j+k][count]=true;</p><p><b>　　}</b></p><p><b>　　count++;</b></p><p><b>

74、;　　}</b></p><p><b>　　}</b></p><p><b>　　//反斜的組合情況</b></p><p>　　for(i=0;i<15;i++){</p><p>　　for(j=18;j>=4;j--){</p><p>　　

75、for(k=0;k<5;k++){</p><p>　　cmp[i+k][j-k][count]=true;</p><p>　　ply[i+k][j-k][count]=true;</p><p><b>　　}</b></p><p><b>　　count++;</b></p>

76、;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　進(jìn)行初始化后，此時(shí)start、bply置為ture，bcmp置為false。即對(duì)每一種獲勝組合中的情況進(jìn)行初始化。之后游戲開(kāi)始，玩家可下子，電腦不可下子。先玩家下子，轉(zhuǎn)入到系統(tǒng)函數(shù)OnLButtonDown()。如下所示</p&g

77、t;<p>　　void mainFrame::OnLButtonDown(UINT nFlags, CPoint point) {</p><p>　　//玩家單擊時(shí)的動(dòng)作</p><p>　　if(start&&bply){//若開(kāi)始后且輪到玩家下子則進(jìn)行判斷</p><p>　　if(point.x>=38&&

78、amp;point.y&&point.x<=602&&point.y<=602) {</p><p>　　mp=(int)floor((point.x-36)/30);</p><p>　　np=(int)floor((point.y-36)/30);</p><p><b>　　//空格才可下子</b&g

79、t;</p><p>　　if(0==borad[mp][np]) {</p><p><b>　　//置為玩家的子</b></p><p>　　borad[mp][np]=2;</p><p>　　for(k=0;k<1020;k++){</p><p><b>　　//玩家子個(gè)

80、數(shù)加1</b></p><p>　　if(-1!=wcount[1][k]&&ply[mp][np][k])</p><p>　　wcount[1][k]++;</p><p>　　//電腦置為不可能獲勝</p><p>　　if(cmp[mp][np][k]){</p><p>　　cmp

81、[mp][np][k]=false;</p><p>　　wcount[0][k]=-1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　flaglb=1;//玩家下子了可以貼白子 與tishi中的flaglb形成合作關(guān)系</p>

82、<p>　　bply=false;//玩家不可下子</p><p>　　bcmp=true;//電腦可以下子</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p>&l

83、t;p>　　CFrameWnd::OnLButtonDown(nFlags, point);</p><p><b>　　}</b></p><p>　　在此函數(shù)中，首先要判斷下子的位置是否在五子棋的棋盤區(qū)域中。即使其成立point.x>=38&&point.y&&point.x<=602&&point

84、.y<=602。若在區(qū)域中，就調(diào)用了系統(tǒng)中的函數(shù)floor()，用于對(duì)鍵單擊時(shí)的位置取整，來(lái)得到單擊進(jìn)的位置。之后還要判斷所下了位置是否是空子，若是空子才可下子。若為空，則此格即為玩家的子，borad[][]的值置為2（2表示為玩家的子）。玩家下子后，電腦的布局就要改變。這時(shí)對(duì)1020種獲勝情況一一來(lái)進(jìn)行討論。若是玩家的子且在此獲勝組合中有可能獲勝，則wcount[1][]中的個(gè)數(shù)加一，若是電腦的獲勝組合中也為true，則此時(shí)wc

85、ount[0][]置為-1，表示在此獲勝組合中不可能獲勝,并把對(duì)應(yīng)的cmp[][][]的值置為false,表示電腦在此獲勝組合中不可能獲勝。玩家下完之后，此時(shí)就輪到電腦下子了。bply置為true，bcmp置為false，表示玩家下完之后是電腦下子。</p><p>　　玩家下完之后，這時(shí)就是輪到電腦下子。但在下子前判斷下當(dāng)前的狀況。先貼子。</p><p>　　//玩家下完之后就重新貼子

86、</p><p>　　for(i=0;i<19;i++){</p><p>　　for(j=0;j<19;j++){</p><p><b>　　//電腦為紅子</b></p><p>　　if(1==borad[i][j])</p><p>　　dc.BitBlt(i*30+36,j

87、*30+36,24,24,&memcs,0,0,SRCCOPY);</p><p><b>　　// 玩家為綠子</b></p><p>　　if(2==borad[i][j])</p><p>　　dc.BitBlt(i*30+36,j*30+36,24,24,&memps,0,0,SRCCOPY);</p>&

88、lt;p><b>　　}</b></p><p><b>　　}</b></p><p>　　剛剛玩家下完之后，只是內(nèi)部的置為玩家的子，但是用戶沒(méi)有看到。此時(shí)若顯示出來(lái)，則可了解到玩家的子確實(shí)下了。這時(shí)電腦就進(jìn)入了計(jì)算階段。這也是此系統(tǒng)的核心代碼。此函數(shù)放置在OnTimer（）中。如下所示：</p><p><

89、b>　　//是否和棋</b></p><p>　　tie=tieGame();</p><p>　　if(tie&&start)</p><p>　　{start=false;//游戲結(jié)束</p><p>　　bcmp=false;//電腦不可下子</p><p>　　bpl

90、y=false;//玩家不檔下子</p><p>　　MessageBox("朋友，水平不錯(cuò)，竟能與電腦和棋哦……\n(按F1開(kāi)始，F(xiàn)12退出！)");</p><p>　　flagbj=0;//重新顯示背景圖片</p><p><b>　　}</b></p><p><b>　　

91、//是否電腦獲勝</b></p><p>　　cwin=cmpGame();</p><p>　　if(cwin&&start)</p><p>　　{ start=false;//游戲結(jié)束</p><p>　　bcmp=false;//電腦不可下子</p><p>　　bply=

92、false;//玩家不檔下子</p><p>　　MessageBox("朋友,失敗乃成功之母，請(qǐng)?jiān)俳釉賱?lì)!\n(按F1開(kāi)始，F(xiàn)12退出！)");</p><p>　　flagbj=0;//重新顯示背景圖片</p><p><b>　　}</b></p><p><b>　　//是

93、否玩家獲勝</b></p><p>　　pwin=plyGame();</p><p>　　if(pwin&&start)</p><p>　　{ start=false;//游戲結(jié)束</p><p>　　bcmp=false;//電腦不可下子</p><p>　　bply=fal

94、se;//玩家不檔下子</p><p>　　MessageBox("朋友，真牛！一下就贏了，要不收我作徒弟吧~~\n(按F1開(kāi)始，F(xiàn)12退出！)");</p><p>　　flagbj=0;//重新顯示背景圖片</p><p><b>　　}</b></p><p>　　先判斷是否是和棋，若

95、是則暫停程序。當(dāng)然在此，判斷和棋，我是調(diào)用了和棋的函數(shù)tieGame()。其內(nèi)容如下：</p><p>　　BOOL mainFrame::tieGame(){</p><p>　　//若有空格則不為和棋</p><p>　　for(i=0;i<19;i++){</p><p>　　for(j=0;j<19;j++){</p

96、><p>　　if(0==borad[i][j]) {</p><p>　　return false;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p&

97、gt;　　//若有一方勝也不為和棋</p><p>　　for(k=0;k<1020;k++){</p><p>　　if(5==wcount[0][k]||5==wcount[1][k]) {</p><p>　　return false;</p><p><b>　　}</b></p><p

98、><b>　　}</b></p><p><b>　　//否則為和棋</b></p><p>　　return true;</p><p><b>　　}</b></p><p>　　要討論19X19格了中的每一個(gè)格子。若每一個(gè)格子都不為空，即borad[][]!=0,并

99、且在獲勝組合中沒(méi)有一方獲勝，則此時(shí)電腦即為和棋，返回true，否則都為false。這樣就可實(shí)現(xiàn)和棋的判斷了。若是和棋，則此時(shí)start置為flase，表示游戲暫時(shí)停止。并彈出對(duì)話框顯示和棋。</p><p>　　若不為和棋，則判斷是否是電腦獲勝，其也調(diào)用判斷電腦獲勝的函數(shù)cmpGame()，其內(nèi)容如下：</p><p><b>　　//是否玩家獲勝</b></p

100、><p>　　BOOL mainFrame::plyGame(){</p><p>　　for(k=0;k<1020;k++){</p><p>　　if(5==wcount[1][k])//有五子棋相連則獲勝</p><p>　　return true;</p><p><b>　　}</b&

101、gt;</p><p>　　return false;</p><p><b>　　}</b></p><p>　　其實(shí)也挺容易的，只要看下wcount[1][]中是否有一種情況中的個(gè)數(shù)為5，若有此時(shí)就返回true，否則返回flase。若是電腦獲勝，則也彈出對(duì)話框顯示電腦獲勝。這之后便把start也置為false。</p><

102、;p>　　若電腦不獲勝，則繼續(xù)判斷是否玩家獲勝，此時(shí)同樣調(diào)用函數(shù)cmpGame()來(lái)處理。如下所示：</p><p>　　BOOL mainFrame::cmpGame(){</p><p>　　for(k=0;k<1020;k++){</p><p>　　if(5==wcount[0][k])//有五子棋相連則獲勝</p><

103、p>　　return true;</p><p><b>　　}</b></p><p>　　return false;</p><p><b>　　}</b></p><p>　　若在電腦的獲勝組合中有一個(gè)組合的個(gè)數(shù)為5，則電腦獲勝，這時(shí)就彈出對(duì)話框，顯示電腦獲勝，游戲時(shí)放暫停狀態(tài)。否則繼續(xù)

104、執(zhí)行。</p><p>　　若玩家下子后沒(méi)有和棋、電腦獲勝或是玩家獲勝，則此時(shí)就輪到電腦下子了。</p><p>　　首先統(tǒng)計(jì)下當(dāng)前分?jǐn)?shù)，看下當(dāng)前的得分情況。如下：</p><p>　　void mainFrame::countScore(){</p><p>　　for(i=0;i<19;i++){</p><p&

105、gt;　　for(j=0;j<19;j++){</p><p><b>　　//初始值為0</b></p><p>　　pscore[i][j]=0;</p><p>　　cscore[i][j]=0;</p><p>　　//若為空則計(jì)算分?jǐn)?shù)</p><p>　　if(0==borad[i

106、][j]) {</p><p>　　//各種情況一一討論</p><p>　　for(k=0;k<1020;k++){</p><p><b>　　//若是玩家</b></p><p>　　if(ply[i][j][k]) {</p><p>　　switch(wcount[1][k]) {

107、</p><p>　　case 0://零個(gè)子情況</p><p>　　pscore[i][j]+=1;</p><p><b>　　break;</b></p><p>　　case 1: //一個(gè)子情況</p><p>　　pscore[i][j]+=5;

108、</p><p><b>　　break;</b></p><p>　　case 2: //二個(gè)子情況</p><p>　　pscore[i][j]+=10;</p><p><b>　　break;</b></p><p>　　case 3:

109、//三個(gè)子情況</p><p>　　pscore[i][j]+=30; break;</p><p>　　case 4: //四個(gè)子情況</p><p>　　pscore[i][j]+=120;</p><p><b>　　break;</b></p><p>

110、<b>　　}</b></p><p><b>　　}</b></p><p><b>　　//若是電腦</b></p><p>　　if(cmp[i][j][k]) {</p><p>　　switch(wcount[0][k]) {</p><p>

111、<b>　　case 0:</b></p><p>　　cscore[i][j]+=1;</p><p><b>　　break;</b></p><p><b>　　case 1:</b></p><p>　　cscore[i][j]+=2;</p><p

112、><b>　　break;</b></p><p><b>　　case 2:</b></p><p>　　cscore[i][j]+=8;</p><p><b>　　break;</b></p><p><b>　　case 3:</b><

113、/p><p>　　cscore[i][j]+=32;</p><p><b>　　break;</b></p><p><b>　　case 4:</b></p><p>　　cscore[i][j]+=128;</p><p><b>　　break;</b&g

114、t;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b><

115、;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　對(duì)于19X19的格子，一一討論。若格子為空，則進(jìn)行統(tǒng)計(jì)，因?yàn)橹挥锌崭癫趴上伦?。?duì)于空格，對(duì)獲勝的1020種情況一一討論，若存在電腦的獲勝組合為true，若組合中已有一個(gè)子，則在此格中的分?jǐn)?shù)加2，若是已有二個(gè)子，則數(shù)加8，三個(gè)的加

116、32，四個(gè)的加128。在此依據(jù)獲勝組合中的棋子越多，則獲勝的機(jī)會(huì)越大，分?jǐn)?shù)也就越高，計(jì)算機(jī)就按此分?jǐn)?shù)來(lái)計(jì)算最佳位置。對(duì)于玩家的分?jǐn)?shù)也用同樣的規(guī)則。</p><p>　　統(tǒng)計(jì)完分之后，若是輪到電腦下子，游戲未結(jié)束，則電腦下子。</p><p>　　//是否輪到電腦下子</p><p>　　if(bcmp&start)</p><p>　

117、　cmpTurn();</p><p>　　在此也調(diào)用了函數(shù)來(lái)處理電腦下子的算法。對(duì)于cmpTurn()的代碼如下：</p><p>　　void mainFrame::cmpTurn(){</p><p>　　//以下用于找到最高分</p><p>　　//最高分為0，tc為電腦的最高分，tp為玩家的最高分</p><p

118、><b>　　tc=tp=0;</b></p><p>　　//標(biāo)記位,0為沒(méi)找到位置，1為有電腦下子的位置</p><p>　　int flag=0;</p><p>　　for(i=0;i<19;i++){</p><p>　　for(j=0;j<19;j++){</p><p&

119、gt;　　//若是空格則統(tǒng)計(jì)分?jǐn)?shù)</p><p>　　if(0==borad[i][j]) {</p><p>　　if(pscore[i][j]>=tp) {</p><p><b>　　mp=i;</b></p><p><b>　　np=j;</b></p><p&g

120、t;　　tp=pscore[i][j];</p><p><b>　　flag=1;</b></p><p><b>　　}</b></p><p>　　if(cscore[i][j]>=tc) {</p><p><b>　　mc=i;</b></p>&

121、lt;p><b>　　nc=j;</b></p><p>　　tc=cscore[i][j];</p><p><b>　　flag=1;</b></p><p><b>　　}</b></p><p><b>　　}</b></p>

122、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　//以下是電腦下了的位置</p><p>　　if(1==flag) {//若有電腦下子的位置才可下子</p><p>　　//玩家分?jǐn)?shù)高，則下在玩家的最高分位置，否則下在電腦的最高分位置<

123、;/p><p>　　if(tc<tp) {</p><p><b>　　mc=mp;</b></p><p><b>　　nc=np;</b></p><p><b>　　}</b></p><p><b>　　//置為電腦的子</b&

124、gt;</p><p>　　borad[mc][nc]=1;</p><p>　　//將1020種情況一一討論</p><p>　　for(k=0;k<1020;k++){</p><p>　　//電腦可以獲勝且在此位置有獲勝組合，則此組合個(gè)數(shù)加1</p><p>　　if(-1!=wcount[0][k]&am

125、p;&cmp[mc][nc][k])</p><p>　　wcount[0][k]++;</p><p>　　//電腦可獲勝，則置玩家不可能獲勝</p><p>　　if(ply[mc][nc][k]) {</p><p>　　ply[mc][nc][k]=false;</p><p>　　wcount[1][

126、k]=-1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//電腦下完后是玩家下子</p><p>　　bcmp=false;</p><p>　　bply=true;</p><p><

127、b>　　}</b></p><p><b>　　}</b></p><p>　　此函數(shù)先對(duì)于玩家與電腦的分?jǐn)?shù)pscore[][],cscroe[][]進(jìn)行統(tǒng)計(jì)，分別找出電腦和玩家的最高分，若找到了，則置flag為1，表示電腦有可下的子。若有可下的子，則進(jìn)行討論。由于前面已得到了電腦與玩家的最高分，并且分別保留了電腦與玩家的最高分的位置，若是玩家的分