【正文】 42 第七章 結(jié)束 語(yǔ)???????????????????????? 47 參考文獻(xiàn)??????????????????????????? 48 附錄：程序清單（附光盤(pán)） 5 第一章 引 言 五子棋是起源于中國(guó)古代的傳統(tǒng)黑白棋種之一。現(xiàn)代五子棋日文稱(chēng)之為“連珠”，英譯為“ Renju”，英文稱(chēng)之為“ Gobang”或“ FIR” (Five in a Row 的縮寫(xiě) )，亦有“連五子”、“五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱(chēng)謂。目前人工智能在發(fā)展過(guò)程中既有突破但也面臨很大的困難。在決策過(guò)程中要對(duì)形勢(shì)做出恰當(dāng)?shù)墓烙?jì)，搜尋各種可能的策略組合，通過(guò)對(duì)比分析確定對(duì)自己最有利的策略。也就是說(shuō)，電腦若想找到當(dāng)前最優(yōu)的走法，需要全廣度全深度地搜索雙方棋子所有的可能走法。 9 第三章 要解決的幾個(gè)關(guān)鍵問(wèn)題 五子棋棋盤(pán)介紹 五子棋棋盤(pán) ：棋盤(pán)正中一點(diǎn)為“天元”。如“天元” H8，四個(gè)“星”分別為 D D1 L1L4 等。（如下圖） B、沖四 ：除“活四”外的，再下一著棋便可形成五連，并且存在五連的可能性的局面。 四四 ：由于黑方走一著 在無(wú)子交叉點(diǎn)上同時(shí)形成二個(gè)或二個(gè)以上黑方“四”的局面。 C、 “ a”這一點(diǎn)有可能被看作是三三。 在各種搜索算法中，有一個(gè) A*搜索算法，也叫做最佳搜索算法，實(shí)際是一種啟發(fā)式搜索 ， 它是對(duì)于問(wèn)題的各種情況設(shè)定一個(gè)估值函數(shù)，假設(shè)我們選擇的是值最小的道路，在搜索的時(shí)候， A*算法根據(jù)估值函數(shù)判斷下一步應(yīng)選擇的道路，并不停地用走過(guò)的實(shí)際路線的價(jià)值加上下一點(diǎn)的估值函數(shù)作為新的估值。 估值函數(shù) 問(wèn)題求解空間中每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)子目標(biāo)。啟發(fā)式搜索也是邊走邊試探，每走一步，都設(shè)法計(jì)算當(dāng)前棋局的各種可能走法及對(duì)手各種反應(yīng)的得分，然后立足于對(duì)方應(yīng)棋以后自己 面臨的最壞局勢(shì)，尋找那種能夠爭(zhēng)取到的最好的結(jié)果，然后倒推回去選擇滿意的棋步，因而也叫做“極大極小分析法”。博弈分為雙人完備信息博弈和機(jī)遇性博弈。假設(shè)博弈的一方為 MAX，另一方為 MIN。 18 博弈樹(shù)中的節(jié)點(diǎn)是逐層交替出現(xiàn)的。對(duì)于 MIN 節(jié)點(diǎn)，由于 MIN 方總是選擇使估值最小的走步，因此 MIN 節(jié)點(diǎn)的倒退值應(yīng)取其后繼節(jié)點(diǎn)的最小值。 AlphaBeta 剪枝 (AlphaBeta Purning) 對(duì)于一般的最大最小搜索，即使每一步只有很少的下法，搜索的位置也會(huì)增長(zhǎng)非?？?；在大多數(shù)的中局棋形中，每步平均有十個(gè)位置可以下棋，于是假設(shè)搜索九步 (程序術(shù)語(yǔ)稱(chēng)為搜索深度為九 )，就要搜索十億個(gè)位置 (十的九 次方 )，極大地限制了電腦的棋力。 將上述這個(gè)情形推廣一下，設(shè)想有如下圖左部所示的一棵極大極小樹(shù)的片斷，節(jié)點(diǎn)數(shù)字為該節(jié)點(diǎn)的值，節(jié)點(diǎn) B 的值為 18，節(jié)點(diǎn) D 的值為 16，由此我們可以判斷節(jié)點(diǎn) C 的值將小于等于 16（取極小值）；而節(jié)點(diǎn) A 的值為 20 節(jié)點(diǎn) MAX（ B， C），為 18，也就是說(shuō)不再需要估節(jié)點(diǎn) C 的其他子節(jié)點(diǎn)如 E，F(xiàn) 的值就可以得出父節(jié)點(diǎn) A 的值。 棋盤(pán)及棋子表示 首先得為整個(gè)棋盤(pán)建立一張表格用以記錄棋子信息 ，我們使用一個(gè) 15 15 的二維數(shù)組 chessboard_map[15][15] (15 15 是五子棋棋盤(pán)的大小 )，數(shù)組的每一個(gè)元素對(duì)應(yīng)棋盤(pán)上的一個(gè)交叉點(diǎn)，用 ‘1’ 表示 沒(méi)有棋子 、‘ 2’ 代表 黑棋 子、 ‘ 3’ 代表 白棋 子；這張表也是今后分析的基礎(chǔ)。//撇 int position_pie。 POINT_IN_CHESSBOARD chessman[225]。 struct ACTUAL_STEP_INFO actual_step_saved[225]。//橫向第 15 條線 int s_line00[17]。 23 int Chessman_No。//用來(lái)決定在黑方下第五個(gè)棋子的時(shí)候是否采用“五手兩打”的國(guó)際比賽規(guī)則。 還有長(zhǎng)連點(diǎn)的鏈表，活四點(diǎn)的鏈表，四三點(diǎn)的鏈表，雙四點(diǎn)的鏈表，雙三點(diǎn)的鏈表，雙叫四三點(diǎn)的鏈表，單叫四三點(diǎn)的鏈表，連三點(diǎn)的鏈表，跳三點(diǎn)的鏈表，死四點(diǎn)的鏈表，死三點(diǎn)的鏈表，活二點(diǎn)的鏈表。// 棋子 。必須在 InitMyData()函數(shù)中對(duì)上述數(shù)組進(jìn)行初始化 !還有鏈表的指針，也要初始化。 1）初始化函數(shù) void InitMyData() { int i,j。 previous_Chessman_type=1。 } } //給用來(lái)保存棋盤(pán)上所有位置信息的數(shù)組賦初值 CPoint xy。 chessman[i].position_shu=0。 初始化長(zhǎng)連點(diǎn)鏈表 初始化活四點(diǎn)鏈表 初始化四三點(diǎn)鏈表 初始 27 化雙四點(diǎn)鏈表 初始化雙三點(diǎn)鏈表 初始化雙叫四三點(diǎn)鏈表 初始化單叫四三點(diǎn)鏈表 初始化連三點(diǎn)鏈表 初始化跳三點(diǎn)鏈表 初始化死四點(diǎn)鏈表初始化死三點(diǎn)鏈表 初始化活二點(diǎn)鏈表 3）初始化用來(lái)保存白棋的有用點(diǎn)的鏈表 初始化五連點(diǎn)鏈表 ,三個(gè)指針都指向同一個(gè)結(jié)點(diǎn) ,產(chǎn)生一個(gè)頭結(jié)點(diǎn)。 6）沿著 44條線來(lái)初始化棋盤(pán)上的所有點(diǎn) 先處理所有的橫線上的點(diǎn) for (i=0。 28 for(i=0。 1) 由“棋子編號(hào)”到“單位坐標(biāo)” CPoint notounit(int chessman_no) { int xx,yy,arithmetical_pliment。 }。 xx=35*(1+xx)。 } if (arithmetical_pliment17) xx+=1。 // Chessman_No=*15+。 min_empty_index+=1。 chessman[chessman_no].line_shu[chessman[chessman_no].position_shu]=3。 //將要撤銷(xiāo)的棋盤(pán)上的棋子對(duì)應(yīng)的線上的棋子顏色恢復(fù)為 1， 1代表沒(méi)棋子的，是空白 chessman[chessman_no].line_heng[chessman[chessman_no].position_heng]=1。 } 盤(pán)面分析填寫(xiě)棋型表： 本程序核心模塊之一，人工智能算法的根本依據(jù)！其具體實(shí)現(xiàn)方法如下：您在下五子棋時(shí)，一定會(huì)先根據(jù)棋盤(pán)上的情況，找出當(dāng)前最重要的一些點(diǎn)位，如 “ 活三 ” 、 “ 沖四 ” 等；然后再在其中選擇落子點(diǎn)。但這種算法的弱點(diǎn)非常明顯，只顧眼前利益，不能顧全大局，這就和許多五子棋初學(xué)者一樣犯了 “ 目光短淺 ” 的毛病。 勝負(fù)判斷： 某方形成五子連即獲勝；若黑棋走出 ‘ 雙三 ’ 、 ‘ 雙四 ’ 或長(zhǎng)連即以禁手判負(fù)。//chessman 和 Chessman_No都是全局變量 forword=actual_position。(ptrArray[back+1]==temp_chessman_type)) back++。//循環(huán)用的計(jì)數(shù)變量 already_exceed_five=false。//將黑棋的連接數(shù)初始化為 0 temp2=0。 Game_Over=true。這樣不好，效率低，好處是思路簡(jiǎn)單。(TempArray[temp11]==2)) {temp1。amp。//將臨時(shí)變量初始化為 0 temp2=0。 while((temp2(TempArrayLength1))amp。amp。 goto BB。(TempArray[temp2+2]!=2)) {//再判斷一下是不是剛才走的那步棋形成的活三，如果是，就發(fā)現(xiàn)一個(gè)“活三” 37 if ((actual_position=temp1)amp。 //將白棋的各 種防守點(diǎn)保存到局部鏈表 TempChainTableEnd3中 TempChainTableEnd3=SaveDefencePointToChainTable(TempChainTableEnd3)。 while(TempChainTableCurrent3!=TempChainTableHead3) { //下上一個(gè)白棋 if(TempChainTableCurrent3Chessman_No0) { AfxMessageBox()。 // } if(ReturnValueMin) Min=ReturnValue。 } //退出此函數(shù)前要清空此函數(shù)內(nèi)定義的兩個(gè)局部鏈表 //清空黑棋用的 TempChainTableHead 鏈表和白棋用的 TempChainTableHead3 鏈表中的所有的結(jié)點(diǎn) EmptingTwoChainTable(TempChainTableHead,TempChainTableEnd,TempChainTableHead3,TempChainTableEnd3)。 } //繼續(xù)考察下一個(gè)黑棋點(diǎn) Undo_Save_ChessmanInfo()。 } Min=1。不過(guò)，我覺(jué)得這一行代碼好像是多余的。此函數(shù)不需要返回值。 } } else//兩端都要判斷是否會(huì)形成長(zhǎng)連禁手，只有兩端都不會(huì)形成長(zhǎng)連禁手時(shí)，才叫活四 {if ((TempArray[temp12]!=2)amp。(actual_position=temp2)) Live_Three++。amp。(TempArray[temp11]==2)) {temp1。 } } } } //step3:再判斷一下是否出現(xiàn)了一個(gè) 活三 ，判斷的方法是：預(yù)走一步棋看看是否處理出現(xiàn)了活四。amp。 while((temp12)amp。temp4=1。 } } if (temp2temp1) temp1=temp2。 //將線長(zhǎng)度保存到變量 TempArrayLength中 //用一個(gè)指針 TempArray來(lái)指向線數(shù)組 ,這樣比數(shù)組復(fù)制效率高 TempArray=chessman[chessman_no].line_heng。 }} 34 b) //按照國(guó)際標(biāo)準(zhǔn)連珠規(guī)則來(lái)判斷勝負(fù)的函數(shù)。 while((back(ptrArray[1]1))amp。 temp_chessman_type=chessman[Chessman_No].chessman_type。是不是應(yīng)該對(duì)白棋和黑棋分別建立兩套全局鏈表集呢？我覺(jué)得應(yīng)該建立兩套。所有棋型的編號(hào)都 已 事先定義好，越重要的號(hào)數(shù)越大！ 電腦下子： 有了上面填寫(xiě)的兩張棋型表，現(xiàn)在要作的就是讓電腦知道在哪一點(diǎn)下子了。 chessman[chessman_no].line_na[chessman[chessman_no].position_na]=1。 min_empty_index=1。 } else { chessman[chessman_no].chessman_type=3。} 2) 保存每一步所下的棋 void SaveChessmanInfo(int chessman_no,bool is_black_chessman) { actual_step_saved[min_empty_index].chessman_no=chessman_no。//返回精確對(duì)齊到交叉點(diǎn)后的像素坐標(biāo) } 6) 返回精確對(duì)齊到交叉點(diǎn)后的像素坐標(biāo) 參數(shù)是鼠標(biāo)單擊處的實(shí)際像素坐標(biāo) CPoint snap_to_grid(int x,int y)//封裝后的函數(shù)。 while(arithmetical_pliment35)//當(dāng)余數(shù)大于 35時(shí) ,就繼續(xù)減 35 { arithmetical_pliment=arithmetical_pliment35。 yy++。 } xx=arithmetical_pliment。j++) visit_all_line[i][j]=1。 } } 再處理所有的豎線上的點(diǎn)，所有的左斜線 (撇 )上的點(diǎn)，所有的右斜線 (捺 )上的點(diǎn) 7）初始化存儲(chǔ) 72條線的數(shù)組的開(kāi)頭兩個(gè)元素 。 5）初 始化用來(lái)為白棋保存必勝下法的鏈表 SavedVictoryStepHead3=new MyNode。 five_end=five_head。 chessman[i].line_na=Empty_Array。i++)//x坐 標(biāo)從 0到 14 { chessboard_map[i][j]=ddd。 =20。 MyNode *SavedVictoryStepEnd3。//為了能省掉動(dòng)態(tài)分配內(nèi)存的時(shí)間，決定用數(shù)組，理論上應(yīng)該 用 225，不過(guò)用 100都是足夠大了 int tree_stack_index。 struct Crunode //鏈表中的每一個(gè)結(jié)點(diǎn)的類(lèi)型 { int chessman_no。 MyNode *five_end。 BOOL Comput