【正文】 成現(xiàn)實的可能性。人腦可以通過自學(xué)習(xí)、自組織、自適應(yīng)來不斷提高信息處理能力；而存儲程序式計算機的所有能力都是人們通過編制程序賦予它的，與 人腦相比是機械的、死板的和無法自我提高的。其中戰(zhàn)勝過國際象棋世界冠軍 卡斯帕羅夫的“深藍(lán)”便是最具 說服力的代表；其它像圍棋的“手淡”、象棋的“將族”等也以其優(yōu)秀的人工智能深受棋迷喜愛。 五子棋不僅能增強思維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性。而程序依靠估值函數(shù)來判斷對于一方來說什么局面是好而什么局面是壞，后者是用來搜索幾乎全部可能的棋步次序，目的是為了找出對于程序來說是最佳的一條路線。 人工智能電腦下棋模擬的是人類的智能，它的啟發(fā)式搜索是邊走邊試探，即極大極小法。五子棋既有現(xiàn)代休閑的明顯特征“短、平、快”，又有古典哲學(xué)的高深學(xué)問“陰陽易理”；它既有簡單易學(xué)的特性，為人民群眾所喜聞樂見，又有深奧的技巧和高水平的國際性比賽；它的棋文化淵遠(yuǎn)流長，具有東方的神秘和西方的直觀；既有“場”的概念，亦有“點”的連接。由于五子棋相對圍棋、象棋而言簡單一些，所以結(jié)合自己所學(xué)的《人工智能》課程和 Visual C++ 編制了五子棋人機對弈程序。所以通過該程序設(shè)計也探討一下該領(lǐng)域的問題。 人工智能的先驅(qū)者們曾認(rèn)真地表明過他們的信念：如果能夠 掌握下棋的本質(zhì)，也許就掌握了人類智能行為的核心；那些能夠存在于下棋活動中的重大原則，或許就存在于其它任何需要人類智能的活動中。 長期以來，人們對電腦下棋的原理普遍存在著誤解，通常以為在電腦高速計算的威力下，可以毫不費力地算出雙方所有可能的棋步，從中選擇最優(yōu)的方案。 比如， 機器可以出 “ 兵 ” ，也可以出 “ 車 ” ；人的應(yīng)棋可能是跳 “ 馬 ” ，也可能是讓 “ 后 ” 斜著走 5 格，如此等等。 搜索計算所有組合狀態(tài)的后果是引出天文數(shù)字。如果采用棋譜庫，當(dāng)然可以讓電腦落子如飛，但同時也失去了 “ 電腦思考 ” 的意義。棋盤左右最外邊的兩條 縱線稱邊線。橫行線從近到遠(yuǎn)用阿拉伯?dāng)?shù)字 1～ 15 標(biāo)記。 10 回合 ：雙方 各走一著，稱為一個回合。 “四”包括“活四”和“沖四”。 “三”指活三，包括“連三”和“跳三” 。 黑棋禁手包括“三三”、“四四”和“長連”。 先手：對方必須應(yīng)答的著法，其中 沖四 稱為絕對先手。 關(guān)于禁手 三三禁手 三三禁手 四四禁手 四四禁手 四四禁手 四四禁手 (扁擔(dān)陣 ) 四三三禁手 長連禁手 1關(guān)于非禁手 A、 “ a”這一點不是三三，因為橫向不是活三，而是一個長連禁手的骨架 (日本稱為“六腐” )。 估值函數(shù) 估值是一個通過既有的棋類知識來評估一個局面優(yōu)勢的過程。 這樣可以極大的優(yōu)化普通的廣度優(yōu)先搜索 。 理論上，如果估值函數(shù)永遠(yuǎn)小于實際路線的價值，那么， A*算法總可以找到最優(yōu)解。 曾經(jīng)設(shè)想過一個 五子 棋 AI 模型：把所有的棋子以連在一起的一塊為基本單位，而后再根據(jù)棋子的形狀， 位置 情況，賦 予 它強度、影響力等屬性，用力學(xué) 模型來分析全局勢力范圍，并據(jù)此選擇下一手的大致位置。然后根據(jù)函數(shù)的大小來選擇合適的知識，以提高問題求解的效率，這種策略稱為估值函數(shù)策略。 啟發(fā)式搜索 基于估值函數(shù)的搜索控制策略實際上是一種啟發(fā)式搜索。啟發(fā)式搜索不是一種程序算法，它也是人工智能一般性“問題求解”的主要技術(shù)。判斷部分開 始 （ a）初始化 （ b）主循環(huán)控 制模塊 （ c）玩家下子 （ d）盤面分析填 寫棋型表 （ e）電腦下子 （ f）勝負(fù)判斷 結(jié) 束 輪到電腦 輪到玩 家 否 則 17 用到鏈表和遞歸 ,計算量很大。對弈 的結(jié)果是一方贏，另一方輸；或者雙方和局。 在雙人完備信息博弈過程中，雙方都希望自己能夠獲勝。從 MAX 方的觀點看，可供自己選擇的那些行動方案的主動權(quán)都掌握在自己手里，任何一個方案都有可能被 MAX選中， MAX 必須防止那種對自己最為不利的情況的發(fā)生。根的若干子結(jié)點則是由甲的每一種可能走法所生成的局面，而這些節(jié)點的子節(jié)點則是由與乙相對的乙的每一種可能走法所生成的局面??在這棵樹的末梢，是結(jié)束的棋局，人勝或者計算機勝或是雙方都無法取勝的平局。 極大極小值算法（ Minimax Algorithm） 對于簡單的博弈問題，可以生成整個博弈樹，找到必勝的策略。 為了計算非葉節(jié)點的 值，必須從葉節(jié)點向上倒退。由于我們站在 MAX 的立場上，因此應(yīng)該選擇具有最大倒退值的走步。所以，對于中間節(jié)點的值可以有如下計算方法：如果該節(jié)點所對應(yīng)的局面輪到甲走棋，則該節(jié)點的值是所有子節(jié)點中值最大的一個值。各種各樣的這種算法用于同樣用于其他棋類游戲，如國際象棋和跳棋。 ② 任何 MAX 節(jié)點 n 的 α 值大于或等于它先輩節(jié)點的 β 值，則 n 以下的分枝可停止搜索，并令節(jié)點 n 的倒推值為 α 。 右半部分所示的一棵極大極小樹的片斷，節(jié)點 B 的估值為 8，節(jié)點 D的估值為 18，由此我們可以判斷節(jié)點 C 的值其他子節(jié)點如 E、 F 的值就可以得出父節(jié)點 A 的值了。 β裁減 在考慮輪到對手下棋的一個親節(jié)點及輪到棋手下棋的一個子節(jié)點時，B A C D E F A B C D E F 21 如果該子節(jié)點的部分回溯值已經(jīng)大于或等于其親節(jié)點的部分回溯值，那么就不需要對該子節(jié)點或者其后裔節(jié)點做更多的處理了。 表示是下黑棋還是下白棋 true:黑棋 。//豎 int position_shu。//捺 int position_na。 }。 int chessboard_map[15][15]。 。 //actual_step_saved 數(shù)組中保存的最小可用下標(biāo) ,在數(shù)組為空時此變量的值為 0 下面是橫豎撇捺四個方向的 72 條有效線的定義。//橫向第 1條線。//縱向 (豎 )第 15條線 int p_line00[ 7]。//右斜 (捺 )第 21條線 int Empty_Array[1]。//用來保存當(dāng)前棋子的精確坐標(biāo) CPoint previous_Chessman_Position。 BOOL ComputerFirst。 struct MyNode *previous。 MyNode *five_end。 MyNode *five_end3。 struct Crunode //鏈表中的每一個結(jié)點的類型 { int chessman_no。 struct MyNode *dynamic_created[8]。//為了能省掉動態(tài)分配內(nèi)存的時間，決定用數(shù)組，理論上應(yīng)該 用 225，不過用 100都是足夠大了 int tree_stack_index。這樣，下次就不用再計算了，直接按照保存的步驟走棋就行了。 MyNode *SavedVictoryStepEnd3。 min_empty_index=0。 =20。 for(j=0。i++)//x坐 標(biāo)從 0到 14 { chessboard_map[i][j]=ddd。i225。 chessman[i].line_na=Empty_Array。 chessman[i].position_na=0。 five_end=five_head。 five_end3=five_head3。 5）初 始化用來為白棋保存必勝下法的鏈表 SavedVictoryStepHead3=new MyNode。i++) { for (j=0。 } } 再處理所有的豎線上的點，所有的左斜線 (撇 )上的點，所有的右斜線 (捺 )上的點 7）初始化存儲 72條線的數(shù)組的開頭兩個元素 。i++)//橫豎 { visit_all_line[i][0]=0。j++) visit_all_line[i][j]=1。 xx=0。 } xx=arithmetical_pliment。 arithmetical_pliment=chessman_no。 yy++。 return CPoint(xx,yy)。 while(arithmetical_pliment35)//當(dāng)余數(shù)大于 35時 ,就繼續(xù)減 35 { arithmetical_pliment=arithmetical_pliment35。 5) 返回與單位坐標(biāo)對應(yīng)的像素坐標(biāo) 參數(shù)是單位坐標(biāo) CPoint Pixel_Coordinate(int x,int y) { int xx,yy。//返回精確對齊到交叉點后的像素坐標(biāo) } 6) 返回精確對齊到交叉點后的像素坐標(biāo) 參數(shù)是鼠標(biāo)單擊處的實際像素坐標(biāo) CPoint snap_to_grid(int x,int y)//封裝后的函數(shù)。 } 玩家下子： 當(dāng)輪到玩家下時，您通過鍵盤或鼠標(biāo)在棋盤上落子，程序會根據(jù)該點的位置，在對戰(zhàn)雙方的棋型表數(shù)組的相應(yīng)地方記錄 ‘2’ ，以表明該子是玩家下的。} 2) 保存每一步所下的棋 void SaveChessmanInfo(int chessman_no,bool is_black_chessman) { actual_step_saved[min_empty_index].chessman_no=chessman_no。//黑棋子 //將棋子的編號記錄到對應(yīng)的線數(shù)組中 chessman[chessman_no].line_heng[chessman[chessman_no].position_heng]=2。 } else { chessman[chessman_no].chessman_type=3。 chessman[chessman_no].line_na[chessman[chessman_no].position_na]=3。 min_empty_index=1。//將標(biāo)志位置 0,表示此線沒被修改過 .不對！這條線上還有其它的棋子呀！??！ chessman[chessman_no].line_shu[chessman[chessman_no].position_shu]=1。 chessman[chessman_no].line_na[chessman[chessman_no].position_na]=1。 先來分析己方的棋型，我們從棋盤左上角出發(fā)，向右逐行搜索，當(dāng)遇到一個空白點時，以它為中心向左挨個查找，如果遇到己方的子則記錄然后繼續(xù)，如果遇到對方的子、空白點或邊界就停止查找。所有棋型的編號都 已 事先定義好，越重要的號數(shù)越大！ 電腦下子： 有了上面填寫的兩張棋型表，現(xiàn)在要作的就是讓電腦知道在哪一點下子了。這時再調(diào)用模塊 4 對預(yù)測后的棋進(jìn)行盤面分析，如果出現(xiàn)了 ‘ 四三 ’ 、 ‘ 雙三 ’或 ‘ 雙四 ’ 等制勝點，那么己方就可以獲勝了（當(dāng)然對黑棋而言 ‘ 雙三 ’ 、‘ 雙四 ’ 是禁手，另當(dāng)別論）；否則照同樣的方法向下分析，就可預(yù)測出第二步、第三步 ?? 要是盤面上沒有對手必須防的棋型，哪該怎么辦呢？進(jìn)攻不成的話就得考慮防守了，將自己和對手調(diào)換一下位置，然后用上面的方法來預(yù)測對手的棋，這樣既可以防住對手巧妙的攻擊，又能 待 機發(fā)動 反擊！ 預(yù)測法的運算量相當(dāng)之大，用 P4 預(yù)測 7 步的走法平均需要 15 秒以上時間，所以建議預(yù)測量在 5 步以內(nèi)。是不是應(yīng)該對白棋和黑棋分別建立兩套全局鏈表集呢？我覺得應(yīng)該建立兩套。 void victory_or_defeat(bool draw_black_chessman) {int Max_connected_number,connected_number,actual_position,temp_chessman_type。 temp_chessman_type=chessman[Chessman_No].chessman_type。 while((forword2)amp。 while((back(ptrArray[1]1))amp。 if(Max_connected_numberconnected_number) Max_connected_number=connected_number。 }} 34 b) //按照國際標(biāo)準(zhǔn)連珠規(guī)則來判斷勝負(fù)的函數(shù)。 Dead_and_Live_Four=0。 //將線長度保存到變量 TempArrayLength中 //用一個指針 TempArray來指向線數(shù)組 ,這樣比數(shù)組復(fù)制效率高 TempArray=chessman[chessman_no].line_heng。iTempArrayLength。 } } if (temp2temp1) temp1=temp2。 }else already_exceed_five=true。temp4=1。這樣效率高，缺點是分析復(fù)雜。 while((temp12)amp。 whi