【正文】 120個(gè)節(jié)點(diǎn)，可見要生成整個(gè)搜索樹是不可能的。對(duì)于 MAX 節(jié)點(diǎn)，由于 MAX 方總是選擇估值最大的走步，因此， MAX 節(jié)點(diǎn)的倒退值應(yīng)該取其后繼節(jié)點(diǎn)估值的最大值。這一過程稱為極大極小過程。而如果該節(jié)點(diǎn)所對(duì)應(yīng)的局面輪到乙走 19 棋，則該節(jié)點(diǎn)的值是其所有子節(jié)點(diǎn)中值最小的一個(gè)的值。為了搜索九步，一個(gè)好的程序只用搜索十萬到一百萬個(gè)位置，而不是沒用前的十億次。這種剪枝稱為 β 剪枝。這樣將節(jié)點(diǎn) D 的后繼兄弟節(jié)點(diǎn)減去稱為（ beta cutoff）。 計(jì)算過程可以直接返回到親節(jié)點(diǎn)上。 false:白棋 struct POINT_IN_CHESSBOARD 保存棋子信息的結(jié)構(gòu) { int * line_heng。 int * line_pie。 int chessman_type。 編程模型及數(shù)據(jù)結(jié)構(gòu) 定 義一個(gè)用來保存棋盤上所有位置信息的數(shù)組 ,從左上角開始 ,橫向排列 ,至左下角結(jié)束 ,編號(hào)從 0 至 224。 定義一個(gè)數(shù)組 ,用來保存每一局雙方所走的棋 struct ACTUAL_STEP_INFO { int chessman_no。 }。 每條線的頭兩個(gè)元素是 :標(biāo)志位 (標(biāo)志位表示此線是否被改變過 ,例如添加了一個(gè)棋子 )，和數(shù)組(線 )長(zhǎng)度 。 —————— int h_line14[17]。//左斜 (撇 )第 1條線 —————— int p_line20[ 7]。//定義一個(gè)空數(shù)組 ,用來填充那些不屬于有效線的點(diǎn) 下面定義一個(gè)用來訪問所有 72條線的數(shù)組 int * visit_all_line[72]={ h_line00,h_line01,h_line02,h_line03,h_line04,h_line05,h_line06,h_line07,h_line08,h_line09,h_line10,h_line11,h_line12,h_line13,h_line14,s_line00,s_line01,s_line02,s_line03,s_line04,s_line05,s_line06,s_line07,s_line08,s_line09,s_line10,s_line11,s_line12,s_line13,s_line14,p_line00,p_line01,p_line02,p_line03,p_line04,p_line05,p_line06,p_line07,p_line08,p_line09,p_line10,p_line11,p_line12,p_line13,p_line14,p_line15,p_line16,p_line17,p_line18,p_line19,p_line20,n_line00,n_line01,n_line02,n_line03,n_line04,n_line05,n_line06,n_line07,n_line08,n_line09,n_line10,n_line11,n_line12,n_line13,n_line14,n_line15,n_line16,n_line17,n_line18,n_line19,n_line20 }。//用來保存上一個(gè)當(dāng)前棋子的精確坐標(biāo) int previous_Chessman_type。 BOOL PutTwoChessmanInFifthStep。 struct MyNode *next。 MyNode *five_current。 MyNode *five_current3。//棋子在棋盤上的位置的編號(hào) bool is_black_chessman。//應(yīng)該用 8才完美，不過估計(jì)實(shí)際上連 5也很難出現(xiàn) int dynamic_created_index。//上面的數(shù)組的索引，初值為 0 上面定義的結(jié)構(gòu)體數(shù)組要初始化的，尤其是數(shù)組的索引，在使用后一定要恢復(fù)為 0。 用來為黑棋保存必勝下法的鏈表 MyNode *SavedVictoryStepHead。 25 第五章 系統(tǒng)實(shí)現(xiàn)技術(shù) 五子棋人機(jī)對(duì)弈程序流程圖 由五子棋人機(jī)對(duì)弈程序流程圖可知， 程序 共 由六個(gè)基本功能模塊構(gòu)成，各模塊的詳細(xì)分析如下： 初始化 1） 初始化 ：首先，建立盤面數(shù)組、對(duì)戰(zhàn)雙方的棋型表并將它們清零以開 始 （ a）初始化 （ b）主循環(huán)控 制模塊 （ c）玩家下子 （ d）盤面分析填 寫棋型表 （ e）電腦下子 （ f）勝負(fù)判斷 結(jié) 束 輪到電腦 輪到玩家 否 則 26 備使用；然后初始化顯示器、鍵盤、鼠等輸入輸出設(shè)備并在屏幕上畫出棋盤。 Game_Over=true。 =20。j15。 ddd+=1。i++) { chessman[i].line_heng=Empty_Array。 chessman[i].position_heng=0。 chessman[i].chessman_type=1。 five_current=five_head。 five_current3=five_head3。 SavedVictoryStepEnd3=SavedVictoryStepHead3。j15。第一個(gè)元素是標(biāo)志位，第二個(gè)元素是數(shù)組中所有元素個(gè)數(shù)。 visit_all_line[i][1]=17。//注意：這看起來像是個(gè)二維數(shù)組，實(shí)際上不是， visit_all_line[i]這是取一個(gè)一維數(shù)組的元素，作為后面的數(shù)組的數(shù)組名 } //撇 捺 類似處理 } 主循環(huán)控制模塊 ：控制下棋順序，當(dāng)輪到某方下子時(shí)，負(fù)責(zé)將程序轉(zhuǎn)到相應(yīng)的模塊中去，主要擔(dān)當(dāng)一個(gè)調(diào)度者的角色。yy=0。 return CPoint(xx,yy)。 xx=0。 } xx=arithmetical_pliment。 29 3) 返回對(duì)齊到交叉點(diǎn)后的單位坐標(biāo) 參數(shù)是鼠標(biāo)單擊處的實(shí)際像素坐標(biāo)例如 :(0,6) CPoint Get_Unit_Coordinate(int x,int y) { int xx,yy,arithmetical_pliment。 xx++。 xx=35*(1+x)。 { CPoint aaa=Get_Unit_Coordinate(x,y)。 1) 判斷參數(shù)所指定的位置處是否是空的位置 ,參數(shù)是一個(gè)單位坐標(biāo) 30 BOOL IsEmptyPosition(CPoint point) { int No=*15+。 actual_step_saved[min_empty_index].is_black_chessman=is_black_chessman。 chessman[chessman_no].line_shu[chessman[chessman_no].position_shu]=2。//白棋子 //將棋子的編號(hào)記錄到對(duì)應(yīng)的線數(shù)組中 chessman[chessman_no].line_heng[chessman[chessman_no].position_heng]=3。 } } 3) 撤銷保存的棋子信息 void Undo_Save_ChessmanInfo()//注意：關(guān)于標(biāo)志位，已經(jīng)作廢了，不再使用它了，但是為了不改動(dòng)數(shù)組下標(biāo)和數(shù)組大小，還保留它。 //將棋子顏色恢復(fù)為 1， 1代表沒棋子的，是空白 chessman[chessman_no].chessman_type=1。 31 chessman[chessman_no].line_shu[0]=0。 chessman[chessman_no].line_na[0]=0。左邊完成后再向右進(jìn)行同樣的操作；最后把左右兩邊的記錄合并起來，得到的數(shù)據(jù)就是該點(diǎn)橫向上的棋型，然后把棋型的編號(hào)填入到對(duì)戰(zhàn)雙方的棋型表中就行了（ x、y 代表坐標(biāo)， n=0、 3 分別代表橫、豎、左斜、右斜四個(gè)方向）。其中最簡(jiǎn)單的計(jì)算方法，就是遍歷棋型表對(duì)戰(zhàn)雙方的棋型表找出其中數(shù)值最大的一點(diǎn)，在該點(diǎn)下子即可?？蓜e小瞧了這 5 步，有時(shí)它甚至?xí)叱鲎屇氖纸薪^的妙著呢！ 依次考察棋盤上的每一個(gè)點(diǎn)，尋找又價(jià)值的點(diǎn)，即若在此點(diǎn)下上一個(gè)棋子就可以形成五連獲勝點(diǎn)，三種禁手點(diǎn)，活四點(diǎn)，四三點(diǎn)， VCF 點(diǎn)，活三點(diǎn)等等。而且，每下上一個(gè)棋子，對(duì) 33 于自己方來講，有可能會(huì)增加活三沖四等的個(gè)數(shù)，而對(duì)于對(duì)手方來講，卻有可能會(huì)減少活三沖四等的個(gè)數(shù) ,這一點(diǎn)要充分考慮到才行。 //actual_position變量記錄的是棋盤上的點(diǎn)在線上的位置 int forword,back。 //看一下橫線上有幾個(gè)同色的棋子連 actual_position=chessman[Chessman_No].position_heng。amp。amp。 看一下豎線上有幾個(gè)同色的棋子連 看一下撇線上有幾個(gè)同色的棋子連 看一下捺線上有幾個(gè)同色的棋子連 如果有 5個(gè)或 5個(gè)以上的同色棋子相連，就可獲勝 if(Max_connected_number=5) { if (draw_black_chessman) AfxMessageBox(黑棋獲勝 !)。 void S_victory_or_defeat(int chessman_no,bool draw_black_chessman) { int i。 Live_Three=0。 //下面要開始判斷勝負(fù)和禁手了 ,共分三步來完成 //step1:從頭至尾搜索一遍 ,看看是否有長(zhǎng)連或 5連 ,如果有 ,則判定為 禁手 或 取勝 ,并且不用再進(jìn)行下面的判斷了 , //否則 ,就必須進(jìn)行下面的 step2:看看有沒有 四 (活四和跳四都是四 )和 step3:活三的判斷 temp1=0。i++) { if(TempArray[i]==2) temp2++。 if (temp14) {if (temp1==5) { AfxMessageBox(黑棋獲勝 !)。 //長(zhǎng)連禁手了，但是并不一定會(huì)輸 ,必須要等確認(rèn)四條線上都沒有 5連后，才可以確認(rèn)是輸了 } //step2:看看有沒有 四 (活四和跳四都是 四 ),因?yàn)橛刑牡某霈F(xiàn)，所以要采用預(yù)走棋的方法來看看是否“四” 35 temp1=0。 //下面的判斷方法是從一條線的頭搜索到尾，找到五、四、三以后再看看是不是包含落子點(diǎn)在內(nèi)。 for (i=2。amp。amp。(actual_position=temp2)) { if ((temp1!=temp3)amp。 // AfxMessageBox(發(fā)現(xiàn)一個(gè)活四 !)。 //“活三”的定義：再添加一個(gè)棋子就能形成“活四”的棋局 //“活四”的定義：兩端的任意一端添加上一個(gè)棋子都能形成五連勝，并且不是長(zhǎng)連！ temp1=0。i++) { if(TempArray[i]==1)//如果是空白棋 ,則預(yù)走上一個(gè)棋子，看看是否出現(xiàn)了四連 (跳四不叫 四連 !)， { //向首端搜索 temp1=i。} 36 //再向末端搜索 temp2=i。} //如果預(yù)走上一步棋后，形成了四連，則進(jìn)一步判斷這個(gè)“四連”是不是活的 ,即這個(gè)四的兩端是否都有空 ,并且將空添上后是否會(huì)出現(xiàn)長(zhǎng)連禁手 if ((temp2temp1+1)==4) {if ((temp12)amp。(TempArray[temp2+1]==1)) {if (TempArrayLength==6)//如果線長(zhǎng)度是 6，則必定是活四 {//再判斷一下是不是剛才走的那步棋形成的活三，如果是，就發(fā)現(xiàn)一個(gè)“活三” if ((actual_position=temp1)amp。 goto BB。 // AfxMessageBox(活三了，橫 )。(actual_position=temp2)) Live_Three++。amp。 //AfxMessageBox(活三了，橫 )。 ScanChessboardAndGetAllWhiteDefencePoint()。 下面開始循環(huán)處理保存到鏈表中的白棋的下點(diǎn)，即試遍白棋所有的合理的應(yīng)對(duì)方法 int Min。 TempChainTableCurrent3=TempChainTableEnd3。 if(ReturnValue==1) { Undo_Save_ChessmanInfo()。 38 //再跳出白棋的 While循環(huán) break。 } //如果白棋返回的是 1，表示白棋防不住這個(gè)黑棋的進(jìn)攻，所以就不用再往下判斷了，返回這個(gè)黑棋的編號(hào)就行了 //因?yàn)榘凑詹┺臉涞睦碚摚谄鍛?yīng)該取最大值才對(duì) if(Min==1) {Undo_Save_ChessmanInfo()。 TempChainTableCurrent=TempChainTableCurrentprev