【正文】 TempChainTableCurrent=TempChainTableCurrentprevious。 38 //再跳出白棋的 While循環(huán) break。 TempChainTableCurrent3=TempChainTableEnd3。 ScanChessboardAndGetAllWhiteDefencePoint()。amp。 // AfxMessageBox(活三了，橫 )。(TempArray[temp2+1]==1)) {if (TempArrayLength==6)//如果線長度是 6，則必定是活四 {//再判斷一下是不是剛才走的那步棋形成的活三，如果是，就發(fā)現(xiàn)一個“活三” if ((actual_position=temp1)amp。} 36 //再向末端搜索 temp2=i。 //“活三”的定義：再添加一個棋子就能形成“活四”的棋局 //“活四”的定義：兩端的任意一端添加上一個棋子都能形成五連勝，并且不是長連！ temp1=0。(actual_position=temp2)) { if ((temp1!=temp3)amp。amp。 //下面的判斷方法是從一條線的頭搜索到尾，找到五、四、三以后再看看是不是包含落子點在內(nèi)。 if (temp14) {if (temp1==5) { AfxMessageBox(黑棋獲勝 !)。 //下面要開始判斷勝負和禁手了 ,共分三步來完成 //step1:從頭至尾搜索一遍 ,看看是否有長連或 5連 ,如果有 ,則判定為 禁手 或 取勝 ,并且不用再進行下面的判斷了 , //否則 ,就必須進行下面的 step2:看看有沒有 四 (活四和跳四都是四 )和 step3:活三的判斷 temp1=0。 void S_victory_or_defeat(int chessman_no,bool draw_black_chessman) { int i。amp。 //看一下橫線上有幾個同色的棋子連 actual_position=chessman[Chessman_No].position_heng。而且，每下上一個棋子，對 33 于自己方來講，有可能會增加活三沖四等的個數(shù)，而對于對手方來講，卻有可能會減少活三沖四等的個數(shù) ,這一點要充分考慮到才行。其中最簡單的計算方法，就是遍歷棋型表對戰(zhàn)雙方的棋型表找出其中數(shù)值最大的一點，在該點下子即可。 chessman[chessman_no].line_na[0]=0。 //將棋子顏色恢復為 1， 1代表沒棋子的，是空白 chessman[chessman_no].chessman_type=1。//白棋子 //將棋子的編號記錄到對應(yīng)的線數(shù)組中 chessman[chessman_no].line_heng[chessman[chessman_no].position_heng]=3。 actual_step_saved[min_empty_index].is_black_chessman=is_black_chessman。 { CPoint aaa=Get_Unit_Coordinate(x,y)。 xx++。 } xx=arithmetical_pliment。 return CPoint(xx,yy)。//注意：這看起來像是個二維數(shù)組，實際上不是， visit_all_line[i]這是取一個一維數(shù)組的元素，作為后面的數(shù)組的數(shù)組名 } //撇 捺 類似處理 } 主循環(huán)控制模塊 ：控制下棋順序，當輪到某方下子時，負責將程序轉(zhuǎn)到相應(yīng)的模塊中去，主要擔當一個調(diào)度者的角色。第一個元素是標志位，第二個元素是數(shù)組中所有元素個數(shù)。 SavedVictoryStepEnd3=SavedVictoryStepHead3。 five_current=five_head。 chessman[i].position_heng=0。 ddd+=1。 =20。 25 第五章 系統(tǒng)實現(xiàn)技術(shù) 五子棋人機對弈程序流程圖 由五子棋人機對弈程序流程圖可知， 程序 共 由六個基本功能模塊構(gòu)成，各模塊的詳細分析如下： 初始化 1） 初始化 ：首先，建立盤面數(shù)組、對戰(zhàn)雙方的棋型表并將它們清零以開 始 （ a）初始化 （ b）主循環(huán)控 制模塊 （ c）玩家下子 （ d）盤面分析填 寫棋型表 （ e）電腦下子 （ f）勝負判斷 結(jié) 束 輪到電腦 輪到玩家 否 則 26 備使用；然后初始化顯示器、鍵盤、鼠等輸入輸出設(shè)備并在屏幕上畫出棋盤。//上面的數(shù)組的索引，初值為 0 上面定義的結(jié)構(gòu)體數(shù)組要初始化的，尤其是數(shù)組的索引，在使用后一定要恢復為 0。//棋子在棋盤上的位置的編號 bool is_black_chessman。 MyNode *five_current。 BOOL PutTwoChessmanInFifthStep。//定義一個空數(shù)組 ,用來填充那些不屬于有效線的點 下面定義一個用來訪問所有 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 }。 —————— int h_line14[17]。 }。 編程模型及數(shù)據(jù)結(jié)構(gòu) 定 義一個用來保存棋盤上所有位置信息的數(shù)組 ,從左上角開始 ,橫向排列 ,至左下角結(jié)束 ,編號從 0 至 224。 int * line_pie。 計算過程可以直接返回到親節(jié)點上。這種剪枝稱為 β 剪枝。而如果該節(jié)點所對應(yīng)的局面輪到乙走 19 棋，則該節(jié)點的值是其所有子節(jié)點中值最小的一個的值。對于 MAX 節(jié)點，由于 MAX 方總是選擇估值最大的走步，因此， MAX 節(jié)點的倒退值應(yīng)該取其后繼節(jié)點估值的最大值。 博弈樹具有如下特點： 博弈的初始狀態(tài)是初始節(jié)點。因此，當任何一方走步時，都選擇自己最為有利，而對另一方最為不利的行動方案。 博弈樹 博弈是一類富有智能行為的競爭活動，如下棋、打牌、戰(zhàn)爭等。這是因為確定估價函數(shù)所依據(jù)的知識往往是經(jīng)驗的和直觀判斷的知識，這類知識通常稱為啟發(fā)式知識。實際上這就是對 A*算法估值函數(shù)的一種設(shè)想。以下以A*搜索 為例進行說明。 B、 “ a”這一點也不是三三，因為橫向也不是活三，而是一個假活三 (此形狀日本稱之為“下 止” )。 三三 ：由于黑方走一著在無子交叉點上同時形成二個或二個以上黑方“活三”的局面。 A、活四 ：在棋盤某一條陽線或陰線上有同色 4 子不間隔地緊緊相連，且在此 4 子兩端延長線上各有一個無子的交叉點與此 4 子緊密相連?？v橫軸上的橫縱線交叉點分別用橫縱線標記的名稱合寫成。本程序不 采用棋譜庫 ，用啟發(fā)式搜索， 做到前瞻 6 步棋 ，盡力擊敗對手。然后，對應(yīng)著每 8 一種可能的回合，都必須分別一步步推算下去，一直算到能把人類棋手的“ 王 ” 殺死的那一步為止。博弈是研究使自己取勝、戰(zhàn)勝對手的策略。 、內(nèi)容及作者的任務(wù) 人工智能是一門廣泛的交叉和前沿科學，從 1956 年正式提出人工智能 6 學科算起，已有 40 多年歷史。 關(guān)鍵詞： 五子棋 人工智能 估值函數(shù) 樹狀搜索算法 極大極小法 2 The program for Renju in man vs puter Abstract: The program for Renju is posed of two parts: a evaluation function and a hashtable treesearching algorithm. The evaluation function is used to judge the advantage or disadvantage situation for each part, the hashtable treesearching algorithm is used to search almost all the possible steps and find out the best pathway for the program. The puter of Artificial Intelligence (AI) imitate the intelligence of human, its inspiring search way is Go and Explore, namely, Minimax. Key words: Renju Artificial Intelligence (AI) evaluation function hashtable treesearching algorithm Minimax 3 五子棋人機對弈程序目錄 中文摘要 英文摘要 第一章 引言?????????????????????????? 5 ????????????????????? 5 本論文的目的、內(nèi)容及作者的任務(wù)?????????????? 5 第二 章 研究現(xiàn)狀及設(shè)計目標??????????????????? 7 ?????????????? 7 ??????????????? 7 ?????????????????? 8 第三章 要解決的幾個關(guān)鍵問題?????????????????? 9 ?????????????????? 9 ???????????????????? 9 ???? ???????????? 9 ????????????????? 13 ?????????????????????? 13 ????????????????????? 13 ?????????? 14 第四章 系統(tǒng)結(jié)構(gòu)與模型???????????????????? 16 ???????????????? 16 ???????????????? 16 ??????????????????????? 16 4 極大極小值算法（ Minimax Algorithm）????????? 18 AlphaBeta 剪枝 (AlphaBeta Purning) ???????? 19 ??????????????????? 21 ??????????????????? 21 ????????????????? 22 第五章 系統(tǒng)實現(xiàn)技術(shù)????????? ???????????? 25 ????????????? 25 ??????????????????????? 25 ??????????????????? 28 ?????????????????????? 29 ????????????????? 31 ?????????????????????? 31 ????????????????????? ? 33 ????????????????????? 37 第六章 性能測試與分析???????????????????? 41 系統(tǒng)運行所需的軟件、硬件環(huán)境?????????????? 41 ???????????????????????? 41 ????????????????? 41 ??????????????????? 42 ????????????????????????