程序設(shè)計實(shí)驗報告PAGEPAGE2上海海事大學(xué)程序設(shè)計課程設(shè)計報告課程題目FIVECHESSGAME作者姓名學(xué)號聯(lián)系方式指導(dǎo)教師學(xué)科(專業(yè))所在學(xué)院提交日期目錄1引言 31.1五子棋介紹 31.2選題背景和動機(jī) 31.3系統(tǒng)所要解決的問題 32系統(tǒng)框架 52.1棋盤類 62.1.1主要成員變量說明： 62.1.2清空棋盤——Clear 62.1.3繪制棋子——Draw 62.1.4左鍵消息——OnLButtonUp 72.1.5 載入棋盤 72.1.6對方落子完畢——Over 72.1.7設(shè)置游戲模式——SetGameMode 72.1.8勝負(fù)的判斷——Win 72.2游戲模式類 83關(guān)鍵技術(shù) 93.1棋盤對話框的制作 93.1.1對話框機(jī)制 93.1.3棋子 103.2人機(jī)對弈 103.2.1難度的選擇 103.2.2機(jī)器的落子判斷 114運(yùn)行結(jié)果 154.1開發(fā)環(huán)境及運(yùn)行環(huán)境 154.1.1開發(fā)環(huán)境 154.1.2運(yùn)行環(huán)境 154．2運(yùn)行圖示 154.2.1棋盤顯示 154.2.2開始的選擇對話框 164.2.3主界面中的游戲難度選項 164.2.4電腦的應(yīng)對 175調(diào)試分析 196總結(jié) 21參考文獻(xiàn) 221引言1.1五子棋介紹五子棋是起源于中國古代的傳統(tǒng)黑白棋種之一。現(xiàn)代五子棋日文稱之為“連珠”，英譯為“Renju”，英文稱之為“Gobang”或“FIR”（FiveinaRow的縮寫），亦有“連五子”、“五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱謂。五子棋不僅能增強(qiáng)思維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性。五子棋既有現(xiàn)代休閑的明顯特征“短、平、快”，又有古典哲學(xué)的高深學(xué)問“陰陽易理”；它既有簡單易學(xué)的特性，為人民群眾所喜聞樂見，又有深奧的技巧和高水平的國際性比賽；它的棋文化源淵流長，具有東方的神秘和西方的直觀；既有“場”的概念，亦有“點(diǎn)”的連接。它是中西文化的交流點(diǎn)，是古今哲理的結(jié)晶。1.2選題背景和動機(jī)隨著社會的發(fā)展，越來越多人接觸和使用計算機(jī)，網(wǎng)上進(jìn)行的棋類運(yùn)動也隨之普及。許多人喜歡上了下棋，但有時又苦于沒有對手。作為一個計算機(jī)專業(yè)的學(xué)生，我對五子棋有很濃厚的興趣，平時也一直和同學(xué)下棋，有時也和電腦下棋，我對計算機(jī)人機(jī)對弈智能算法如何與人腦對抗產(chǎn)生了極大的興趣，當(dāng)然人機(jī)對弈的算法有很多種，許多人也對此有所研究。有些算法的智能程度甚至已經(jīng)與人腦不相上下。這類程序的開發(fā)最重要的莫過于智能算法的實(shí)現(xiàn)，然后就是判斷勝負(fù)的方法。當(dāng)前網(wǎng)絡(luò)上流傳的五子棋游戲功能并不盡善盡美，其中最主要的問題就是人機(jī)對戰(zhàn)和網(wǎng)絡(luò)對戰(zhàn)不能夠一起實(shí)現(xiàn)，所以我決定開發(fā)[1]一個既能夠人機(jī)對戰(zhàn)，又能夠進(jìn)行網(wǎng)絡(luò)對戰(zhàn)的五子棋系統(tǒng)。1.3系統(tǒng)所要解決的問題1）棋盤和棋子的繪制。2）計算機(jī)對下一步落棋的計算3)棋盤的載入4）難度的模式選擇5）棋盤狀態(tài)的判定2系統(tǒng)框架五子棋系統(tǒng)框架：五子棋人機(jī)對弈五子棋人機(jī)對弈人人對弈判斷輸贏結(jié)果棋盤考慮到整個的下棋過程（無論對方是電腦或是其他網(wǎng)絡(luò)玩家）可以分為：己方落子、等待對方落子、對方落子、設(shè)置己方棋盤數(shù)據(jù)這一系列過程，因此一人游戲類、二人游戲類和棋盤類之間的關(guān)系是不同的。2.1棋盤類整個架構(gòu)的核心部分，類名為CTable。封裝了棋盤的各種可能用到的功能，如保存棋盤數(shù)據(jù)、初始化、判斷勝負(fù)等。用戶操作主界面，主界面與CTable進(jìn)行交互來完成對游戲的操作。2.1.1主要成員變量說明：棋盤等待標(biāo)志——m_bWait與m_bOldWait由于在玩家落子后需要等待對方落子，m_bWait標(biāo)志就用來標(biāo)識棋盤的等待狀態(tài)。當(dāng)m_bWait為TRUE時，是不允許玩家落子的。在人人對弈模式下，玩家之間需要互相發(fā)送諸如悔棋、和棋這一類的請求消息，在發(fā)送請求后等待對方回應(yīng)時，也是不允許落子的，所以需要將m_bWait標(biāo)志置為TRUE。在收到對方回應(yīng)后，需要恢復(fù)原有的棋盤等待狀態(tài)，所以需要另外一個變量在發(fā)送請求之前保存棋盤的等待狀態(tài)做恢復(fù)之用，也就是m_bOldWait。等待標(biāo)志的設(shè)置，由成員函數(shù)SetWait和RestoreWait完成。2.1.2清空棋盤——Clear在每一局游戲開始的時候都需要調(diào)用這個函數(shù)將棋盤清空，也就是棋盤的初始化工作。在這個函數(shù)中，主要發(fā)生了這么幾件事情：將m_data中每一個落子位都置為無子狀態(tài)（-1）。按照傳入的參數(shù)設(shè)置棋盤等待標(biāo)志m_bWait，以供先、后手的不同情況之用。2.1.3繪制棋子——Draw這無疑是很重要的一個函數(shù)，它根據(jù)參數(shù)給定的坐標(biāo)和顏色繪制棋子。繪制的詳細(xì)過程如下：將給定的棋盤坐標(biāo)換算為繪圖的像素坐標(biāo)。根據(jù)坐標(biāo)繪制棋子位圖。在剛繪制完成的棋子四周繪制最后落子指示矩形。2.1.4左鍵消息——OnLButtonUp作為棋盤唯一響應(yīng)的左鍵消息，也需要做不少的工作：如果棋盤等待標(biāo)志m_bWait為TRUE，則直接發(fā)出警告聲音并返回，即禁止落子。如果點(diǎn)擊時的鼠標(biāo)坐標(biāo)在合法坐標(biāo)(0,0)～(14,14)之外，亦禁止落子。如果走的步數(shù)大于1步，方才允許悔棋。進(jìn)行勝利判斷，如勝利則修改UI狀態(tài)并增加勝利數(shù)的統(tǒng)計。如未勝利，則向?qū)Ψ桨l(fā)送已經(jīng)落子的消息。落子完畢，將m_bWait標(biāo)志置為TRUE，開始等待對方回應(yīng)。載入棋盤尋找棋盤位圖，通過簡單的代碼載入位圖，直接完成繪制棋盤工作，免去了大量繪制棋盤的多余操作。2.1.6對方落子完畢——Over在對方落子之后，仍然需要做一些判斷工作，這些工作與OnLButtonUp中的類似。2.1.7設(shè)置游戲模式——SetGameMode這個函數(shù)通過傳入的游戲模式參數(shù)對m_pGame指針進(jìn)行了初始化，，就可以利用繼承和多態(tài)特點(diǎn)來使m_pGame指針使用相同的調(diào)用來完成不同的工作了，事實(shí)上，COneGame::Init和CTwoGame::Init都是不同的。2.1.8勝負(fù)的判斷——Win這是游戲中一個極其重要的算法，用來判斷當(dāng)前棋盤的形勢是哪一方獲勝。其詳細(xì)內(nèi)容在關(guān)鍵技術(shù)一節(jié)。2.2游戲模式類用來管理人機(jī)對弈人人對弈兩種游戲模式，類名為CGame。CGame是一個抽象類，經(jīng)由它派生出一人游戲類COneGame和網(wǎng)絡(luò)游戲類CTwoGame，如圖2.2：抽象類抽象類CGameCOneGameCTwoGameCOneGameCTwoGame圖2.2CGame類派生關(guān)系這樣，CTable類就可以通過一個CGame類的指針在游戲初始化的時候根據(jù)具體游戲模式的要求實(shí)例化COneGame或CTwoGame類的對象來區(qū)分人機(jī)對弈還是人人對弈；然后利用多態(tài)性，使用CGame類提供的公有接口就可以完成不同游戲模式下的不同功能了。3關(guān)鍵技術(shù)3.1棋盤對話框的制作3.1.1對話框機(jī)制顯示對話框供人選擇下棋模式BOOLCBestDlg::OnInitDialog()//初始化對話框{ CDialog::OnInitDialog(); m_hIcon=AfxGetApp()->LoadIcon(IDR_MAINFRAME); SetIcon(m_hIcon,TRUE); //設(shè)置大圖標(biāo) SetIcon(m_hIcon,FALSE); //設(shè)置小圖標(biāo) Name1Edit().SetWindowText(g_strName1);//載入用戶名1 Name2Edit().SetWindowText(g_strName2);//載入用戶名2 Name3Edit().SetWindowText(g_strName3);//載入用戶名3 charstr[4];//定義4個字符的字符串 wsprintf(str,"%d",g_nTime1);//wsprintf(緩沖區(qū),格式，要格式化的值)； Time1Edit().SetWindowText(str)//設(shè)置主窗口中空間(ID)的文字或標(biāo)題; wsprintf(str,"%d",g_nTime2);//用來格式化字符串 Time2Edit().SetWindowText(str); wsprintf(str,"%d",g_nTime3); Time3Edit().SetWindowText(str); returnTRUE;}3.1.2棋盤用于載入棋盤m_pDibBoard->LoadDib(IDDIB_BOARD);//載入棋盤位圖，m_pDibBoard->MakeBitmap(pDC);//繪制棋盤上的坐標(biāo)，方便下子3.1.3棋子用于畫棋子CRectCPenteDlg::GetCurStoneArea(CPointpoint)//獲得棋子的坐標(biāo){ intnXd=point.x-m_wStoneWidth/2;//棋子橫坐標(biāo) intnYd=point.y-m_wStoneHeight/2;//棋子縱坐標(biāo) returnCRect(nXd,nYd,nXd+m_wStoneWidth,nYd+m_wStoneHeight);//返回棋子的寬度高度}3.2人機(jī)對弈3.2.1難度的選擇它能讓玩家選擇適合自己的難度設(shè)置電腦難易程度：BOOLCRecordDlg::OnInitDialog()//初始化對話框{ CDialog::OnInitDialog(); m_hIcon=AfxGetApp()->LoadIcon(IDR_MAINFRAME);//載入主框架圖標(biāo) SetIcon(m_hIcon,TRUE); //設(shè)置大圖標(biāo) SetIcon(m_hIcon,FALSE); //設(shè)置小圖標(biāo) CStringstr;//聲明字符串 if(g_nSkill==1)//如果技術(shù)為1 { str.LoadString(g_bChineseIDS_BEGINNER_CHINESE:IDS_BEGINNER_ENGLISH);//載入顯示初學(xué)者難度位圖，并用中文或者英文顯示說明 SkillEdit().SetWindowText(str);//設(shè)置難度窗口 NameEdit().SetWindowText(g_strName1);//設(shè)置窗口，用于輸入姓名 } elseif(g_nSkill==2)//如果技術(shù)為2 { str.LoadString(g_bChineseIDS_INTERMEDIATE_CHINESE:IDS_INTERMEDIATE_ENGLISH);載入中級難度位圖，并顯示 SkillEdit().SetWindowText(str); NameEdit().SetWindowText(g_strName2); } if(g_nSkill==3)//如果難度為3 { str.LoadString(g_bChineseIDS_EXPERT_CHINESE:IDS_EXPERT_ENGLISH);//載入專家級難度位圖，并顯示 SkillEdit().SetWindowText(str); NameEdit().SetWindowText(g_strName3); } NameEdit().SetFocus();對之前設(shè)置的窗口設(shè)置鍵盤焦點(diǎn) returnTRUE;FALSE}3.2.2機(jī)器的落子判斷它使電腦能夠根據(jù)人的走棋加以應(yīng)對人與機(jī)器對弈，機(jī)器是如何判斷的呢？此時就需要引入人機(jī)對弈智能算法：算法如下：CPointCPenteDlg::UrgentPoint(BYTEbyColor)//聲明緊迫度函數(shù){ inti,i0,j,j0; BeginWaitCursor();///是建立等待光標(biāo) CPointptUrgent[2025],ptInit(-1,-1);//建立最大緊迫度2025 for(i=0;i<2025;++i)//初始化i ptUrgent[i]=ptInit;初始化i點(diǎn)的緊迫度nGrade1

=

Judge(i,

j,

(char)(byColor+1));//獲取對方緊迫度

nGrade2

=

Judge(i,

j,

(char)(!byColor+1));//不同緊迫度，賦予不同度權(quán)值

if

(g_nSkill

==

1)

//初學(xué)者難度

{

switch

(nGrade1)

//轉(zhuǎn)向等級1，并對它賦權(quán)值，用于判斷電腦下棋位子

{

case

0

:

nUrgent1

=

0;

break;//在情況0下對緊迫度為1的點(diǎn)賦予權(quán)值0case

1

:

nUrgent1

=

2;

break;//在情況1下對緊迫度為1的點(diǎn)賦予權(quán)值4case

2

:

nUrgent1

=

4;

break；//以下的以此類推，直到賦予40case

3

:

nUrgent1

=

5;

break;

case

4

:

nUrgent1

=

8;

break;

case

5

:

nUrgent1

=

10;

break;

case

6

:

nUrgent1

=

11;

break;……

case

16

:

nUrgent1

=

32;

break;

case

17

:

nUrgent1

=

34;

break;

case

18

:

nUrgent1

=

36;

break;

case

19

:

nUrgent1

=

38;

break;

case

20

:

nUrgent1

=

40;

break;

default

:

nUrgent1

=

40;

break;

}

switch(nGrade2)//轉(zhuǎn)向等級2{case0:nUrgent2=1;break;//在情況0時對緊迫度未2的點(diǎn)賦予權(quán)值1，case1:nUrgent2=3;break;//以下的以此類推直到賦予41為止case2:nUrgent2=6;break; case3:nUrgent2=7;break; case4:nUrgent2=9;break; case5:nUrgent2=21;break;//對緊迫度為2的點(diǎn)賦予在不同的情況下賦予不同的權(quán)值case6:nUrgent2=22;break; case7:nUrgent2=23;break; case8:nUrgent2=24;break; case9:nUrgent2=25;break; case10:nUrgent2=26;break; case11:nUrgent2=27;break; case12:nUrgent2=28;break; case13:nUrgent2=29;break; case14:nUrgent2=30;break; case15:nUrgent2=31;break; case16:nUrgent2=33;break; case17:nUrgent2=35;break; case18:nUrgent2=37;break; case19:nUrgent2=39;break; case20:nUrgent2=41;break; default:nUrgent2=41;break; } }nUrgent

=

min(nUrgent1,nUrgent2)*45

+

max(nUrgent1,

nUrgent2);//如上算法既考慮了對手的權(quán)值，也考慮了自己緊迫點(diǎn)的權(quán)值，通過賦予不同緊迫點(diǎn)不同的權(quán)值，綜合起來且根據(jù)總和最大的來確定自己的下子點(diǎn)，由此而實(shí)現(xiàn)了人機(jī)的對弈。通過如下計算公式求出了最緊急的下子點(diǎn)：

ptUrgent[nUrgent]

=

ptCurrent;//獲取具有最小緊迫度的點(diǎn)

}

}

for

(i=0;

i<2025;

++i)//

初始化i

if

(ptUrgent[i]

!=

ptInit)

//如果緊迫點(diǎn)權(quán)值i不等于初始值

break;

EndWaitCursor();//結(jié)束等待光標(biāo)

if

(ptUrgent[i]

==

ptInit)//如果緊迫點(diǎn)權(quán)值i等于初始值

{

CString

str1,

str2;

聲明2個字符串

str1.LoadString(IDS_DRAW_CHINESE);//載入中文圖片

str2.LoadString(IDS_TITLE_CHINESE);//載入中文標(biāo)題

MessageBox(str1,

str2);//出現(xiàn)顯示平局的對話框

}

return

ptUrgent[i];//返回最小的點(diǎn)

}4運(yùn)行結(jié)果4.1開發(fā)環(huán)境及運(yùn)行環(huán)境4.1.1開發(fā)環(huán)境Intel?Pentium?42.0GHz，512M內(nèi)存，80G硬盤Microsoft?Windows?XPMicrosoft?VisualC++6.04.1.2運(yùn)行環(huán)境Intel?Pentium?2及以上處理器，32M以上內(nèi)存，4G以上硬盤Microsoft?Windows?9X/NT操作系統(tǒng)800*600或以上的屏幕分辨率4．2運(yùn)行圖示4.2.1棋盤顯示通過載入棋盤位圖達(dá)到了如下效果：圖4.2.1.五子棋棋盤4.2.2開始的選擇對話框開始的選擇對話框能讓你選擇與電腦下棋還是與人下棋，以及誰執(zhí)黑先手。圖4.2.2選擇對話框4.2.3主界面中的游戲難度選項通過主界面中的游戲難度選項，能選擇適合自己的難度等級，與電腦對弈。圖4.2.3游戲難度選擇4.2.4電腦的應(yīng)對電腦搶先沖3先行的黑子電腦搶先沖3先行的黑子圖沖3的情況沖3這點(diǎn)的權(quán)值最大，電腦選擇此點(diǎn)。先行黑子進(jìn)行防守白子繼續(xù)沖4進(jìn)攻先行黑子進(jìn)行防守白子繼續(xù)沖4進(jìn)攻圖沖4的情況這時沖4權(quán)值經(jīng)計算最大，故電腦選擇此點(diǎn)。黑子率先沖三電腦選擇防守黑子率先沖三電腦選擇防守圖防守的情況5調(diào)試分析在調(diào)試過程出我的算法出了點(diǎn)問題，特別是對于緊迫點(diǎn)權(quán)值的計算，之后同學(xué)求助于CSDN上面的帖子，我修改了自己的算法。并理解了算法實(shí)現(xiàn)要領(lǐng)：電腦下子實(shí)際上是分兩個步驟的，第一個步驟是盡可能的收集棋盤格局的信息，并且使這些信息以一定的格式存放再內(nèi)存中，以便于第二步的處理。第二個步驟就是，對收集到的信息進(jìn)行分析處理，即要給出一個規(guī)則，用窮舉搜索的辦法遍歷所有收集到的信息，搜索的過程實(shí)際上是用所定下的規(guī)則去衡量每一點(diǎn)的權(quán)值，搜索的目的是為了找到一個權(quán)值最大的點(diǎn)，這個點(diǎn)就是當(dāng)前的最優(yōu)解，也就是應(yīng)該下的子。舉個例子來說：如果在第一步中，先遍歷棋盤上的每一個點(diǎn)，即對于每一個點(diǎn)，我們假定這個點(diǎn)放上黑子，這時候就判斷這個黑子放上去后，會形成多少個活2、活3、活4和5子連珠，然后把對應(yīng)的數(shù)值記下，然后再假定這個點(diǎn)放白棋，又會形成多少個活2、活3、活4和五，當(dāng)然你也可以用兩個下面就是如何利用所得到的信息去下棋了：這個過程也是遍歷分析所得的信息的過程。對上面的信息，我們可以很好的處理。比如，假定四三是必勝的，則我們給他的權(quán)值就很大比如100吧，而活二給的權(quán)值應(yīng)該比較小，就給1吧。然后你可以得到一個權(quán)值的計算公式，舉例說：權(quán)值＝活二的個數(shù)×1+活三的個數(shù)×5+活四的個數(shù)×10+四三的個數(shù)×100就是類似這樣的公式，只要得出權(quán)值最大點(diǎn)，并判斷己方下個子的權(quán)值大于對手的URGENTPOINT的權(quán)值的話，這個位置就是你下一步所要下子的點(diǎn)。下棋是就是遍歷每一個點(diǎn)的信息，對每一個點(diǎn)計算權(quán)值，找到權(quán)值最大的就是要下的點(diǎn)了。上面說了用兩個數(shù)組分別保存黑子和白子的信息也是有必要的，因為可以計算出某一點(diǎn)對黑白雙方的重要程度。就是說如果輪到你下白子了，你光看哪一點(diǎn)對白子有利也不行呀，還要看哪些點(diǎn)對黑子有利，并且要比較這種有利的程度。如果你放某一點(diǎn)能成活3，而別人放另一點(diǎn)就是四三了，你就要搶先吧那一點(diǎn)占了。如上算法既考慮了對手的權(quán)值，也考慮了自己緊迫點(diǎn)的權(quán)值，通過賦予不同緊迫點(diǎn)不同的權(quán)值，綜合起來且根據(jù)總和來確定自己的下子點(diǎn)，由此而實(shí)現(xiàn)了人機(jī)的對弈。通過如下計算公式求出了最緊急的下子點(diǎn)：當(dāng)遇到問題時，我求助于論壇，與許多人交流了有關(guān)人工智能算法的思想，許多程序員回了帖子，并教了我許多技巧，我很感謝他們。這個五子棋本來是沒有聲音的，我覺得缺乏趣味，于是便添加了一些聲音文件，當(dāng)出現(xiàn)重復(fù)地點(diǎn)下子的ERROR，獲勝以及重新開始游戲時，都會有一小段音效，我想這也許也會是一點(diǎn)小小的改變吧。6總結(jié)為期1個學(xué)期的程序設(shè)計課，學(xué)到的是我大學(xué)中最受益的東西。首先，在知識方面，我了解了許多C++MFC的知識以及相關(guān)應(yīng)用。對系統(tǒng)的完成五子棋這個小游戲有了深刻的認(rèn)識。這次的課程設(shè)計，不僅令我掌握了五子棋的人工智能算法，同時也培養(yǎng)了我的動手和實(shí)踐創(chuàng)新能力。我學(xué)會了如何把理論用于實(shí)際應(yīng)用中去。我深深的感到獨(dú)立思考，與他們探討，一起研究一個項目是多么快樂的事情。當(dāng)我在設(shè)計過程中出現(xiàn)困難，并出現(xiàn)疑惑時，我求助于老師，并且通過GOOGLE獲取了許多有助于我程序設(shè)計課題的相關(guān)知識。谷歌為我們中國乃至全世界學(xué)生提供了一