【導讀】人工智能是近年來很活躍的研究領域之一。機器學習和博弈是人工智。能研究的重要分支。國內外對博弈的研究已經(jīng)較為廣泛，特別是IBM的。國際象棋程序―深藍‖，已經(jīng)達到了人類的世界冠軍水平。搜索算法實現(xiàn)，難以避免―組合爆炸‖的危機，因此，一個真正―智能‖的，有學習能力的高效率的博弈策略還有待進一步研究。常富有趣味性和消遣性。然而當我們與電腦對戰(zhàn)時，您知道電腦是怎樣像。人腦一樣進行思考的嗎？本文設計和實現(xiàn)了一個人機對戰(zhàn)的五子棋游戲，對整個程序進行UML建模，以減少程序開發(fā)周期。搜索引擎在基本的極。與置換表，這樣減少搜索次數(shù)、時間，增加搜索效率。的數(shù)據(jù)結構、估值函數(shù)、勝負判斷方法和整個搜索算法過程。

　　

【正文】 計 棋盤表示 本系統(tǒng)基于圖 51 所示的數(shù)據(jù)表示棋盤 ： 1. 盤數(shù)據(jù)由一個 15*15 的二維數(shù)組表示。 2. 用數(shù)字 ―0‖和 ―1‖來表示不同的棋子。 3. 沒有棋子的格子用 0xFF 表示。 上述內容僅僅是在實現(xiàn)各個模塊時要遵循的數(shù)據(jù)表示，為了在使用的時 能夠避免數(shù)據(jù)表示差錯，我將棋子的定義成一系列的宏定義，便以使用 圖 51 五子棋棋盤 燕山大學本科畢業(yè)設計（論文） 21 宏定義放在頭文件（ ）中 走法產(chǎn)生器 任何一種人機博弈棋類游戲都會涉及走法產(chǎn)生，顧名思義，走法產(chǎn) 生就是決定怎么走才是合法的步驟。 五子棋的走法產(chǎn)生比較容易，對于五子棋來說，棋盤上的所有空白的位置都是合法的落子點。 走法產(chǎn)生類文件在（ ），實現(xiàn)文件在 中。 搜索引擎 對于本系統(tǒng)，最重要的就是在此部分，搜索引擎，這是決定電腦的 ―智力 ‖是否高的一個重要標準。 本游戲的搜索引擎主要采用 NegeScout 算法與歷史啟發(fā)以及置換表三部分組成。 NegeScout 算法 在介紹 NegeScout 算法之前，首先介紹博弈樹以及極大極小算法 博弈樹 博弈樹是指在博弈過程中，任何一方都希望自己取得勝利。因此，在某一方當前有多個行動方案可供選擇時，他總是挑選對自己最為有利而對對方最為不利的那個行動方案。此時，如果我們站在 A 方的立場上，則可供 A 選擇的若干行動方案之間是 ―或 ‖關系，因為主動權操在 A 方手里，他或者選擇這個行動方案，或者選擇另一個行動方案，完全由 A 方?jīng)Q定，考慮到對 A 方有利總是要選取最大值，所以 A 方搜索極大值。但是，若 B方也有若干個可供選擇的行動方案，則對 A 方來說這些行動方案之間是―與 ‖的關系，因為這時主動權操在 B 方手里，這些可供選擇的任何一個行動方案都肯能被 B 方選中， B 方一定會選擇對 A 方最不利的方案，因此，B 方總是要選擇使 A 方得分最小的路線走，稱極小值搜索。 A 方就必須考慮到對自己最不利的情況的發(fā)生。 第 5 章 總體設計 22 若把上述博弈過程用圖表示出來，得到的是一棵 ―與 /或樹 ‖。這里特別 指出，該 ―與 /或樹 ‖是始終站在某一方（例如 A 方）的立場上得出來的， 決不可一會兒站在這一方的立場上，一會兒站在另一方的立場上。稱描述博弈過程的與 /或樹為博弈樹，它有如下特點： （ 1）博弈的初始格局是初始結點。 （ 2）在博弈樹中， ―或 ‖節(jié)點和 ―與 ‖節(jié)點是逐層交替出現(xiàn)的。自己 一方擴展的節(jié)點間是 ―或 ‖關系，對方擴展的節(jié)點之間是 ―與 ‖關系。雙方輪流地擴展節(jié)點。 （ 3）所有能使自己一方獲勝的終局都是本原問題，相應的節(jié)點是可解 節(jié)點；所有使對方獲勝的終局都是不可解節(jié)點 [6]。 極大極小值分析法 在二人博弈問題中，最常用的方法是極大極小值分析法。 圖 52 給出用極大極小值分析法計算博弈樹倒推值的實例： 圖 52 d=4 的博弈樹的極大極小搜索過程 [7] 在前文的博弈樹中，如果令假勝的局面值為 1，乙勝的局面值為 1，而燕山大學本科畢業(yè)設計（論文） 23 和局的值為 0。當輪到甲走時，甲定會選擇子節(jié)點值最大的走法；而輪到乙時，乙則會選擇子節(jié)點值最小走法。所以對于中間節(jié)點的值可以有如下計算方法；如果該節(jié)點所對應的局面輪到甲走棋，則該節(jié)點的值時其所有子節(jié)點中值最大的一個值，反之輪乙走棋，則該節(jié)點的值時所有子節(jié)點 中值最小的一個值。我們可以這樣想，如果有一種函數(shù)能夠可以為每一局面的憂劣評分。例如甲勝為 +∞；乙勝為 —∞；和局為 0；其他的情形依據(jù)雙方剩余棋子的數(shù)量及位置評定一個具體的分數(shù)。這樣我們可以建立一棵固定深度的搜索樹，其葉子節(jié)點不必是終了狀態(tài)，而只是固定深度的最深一層的節(jié)點，其值由上述函數(shù)評出；對于中間節(jié)點，如同前面提到的那樣，甲方取子節(jié)點的最大值，乙方取子節(jié)點的最小值。這個評分的函數(shù)稱靜態(tài)估值函數(shù)。用以取代超出固定深度的搜索。估值函數(shù)給出的只是一個較粗略的評分，在此基礎上進行的少量搜索的可靠性，理論上是不如前述 的WIN,LOST,DRAW 三種狀態(tài)的博弈樹的，但這個方法卻是可實現(xiàn)的。而極大極小方法往往是指基于靜態(tài)估值函數(shù)的有限深度的極大極小搜索 [8]。 α－ β剪枝算法 在極大極小搜索的過程中，存在著一定程度的數(shù)據(jù)冗余而 α－ β剪枝算法可以解決極大極小值分析過程中存在一定的不足，首先看下面兩幅圖： 圖 53 alphabeta 剪枝 假如，對于上圖左邊部分所示的數(shù)的片段，根據(jù)所示的節(jié)點的值， B第 5 章 總體設計 24 為 18， D 為 16。因此我們可以斷定出 C 的值一定小于 16，而 A 的值是MAX(B,C)為 18，這樣的話不用估值 C 點以后的節(jié)點了就能算出 A 的值。這樣的節(jié)點 D 的后繼節(jié)點減去的方法叫 alpha 剪枝。反之對于圖 43 右半部分，這種剪枝叫做 beta 剪枝。 將 alpha 與 beta 剪枝加入 MINIMAX 搜索，這就是著名 alphabeta 搜索算法。 這里給出 alphabeta 偽代碼： //偽代碼， alphabeta 算法。 int AlphaBeta(nPly,nAlpha,nBeta) { if(game over) return Eveluation。//勝負已分，返回估值 if(nPly = 0) return Eveluation。//葉子節(jié)點返回估值 if(Is Min Node) //判斷當前節(jié)點為何種節(jié)點 { for (each possible move m) //對于每一種走 法 m { Make move m。//生成新節(jié)點 Score = alphabeta(nPly – 1 , nAlpha , nBeta)//遞歸搜索子節(jié)點 Unmake move m。//撤銷搜索過的節(jié)點 if (score nBeta) { nBeta = score。//取最小值 if(nAlpha = nBeta) return nAlpha。//alpha 剪枝，拋 棄后繼節(jié)點 }} return nBeta。//返回最小值 } Else 燕山大學本科畢業(yè)設計（論文） 25 {//取極大值的節(jié)點 for (each possible move m) //對于每一種走法 m { Make move m。//生成新節(jié)點 Score = alphabeta(nPly – 1 , nAlpha , nBeta)//遞歸搜索子節(jié)點 Unmake move m。//撤銷搜索過的節(jié)點 if (score nAlpha) { nAlpha = score。//取最大值 if(nAlpha = nBeta) return nBeta。//beta 剪枝，拋棄后繼節(jié)點 }} return nAlpha。//返回最大值 } } Alphabeta 搜索能夠讓我們忽略很多節(jié)點的搜索，這樣可以大大提高搜索效率。這也讓對于同一棵樹的搜索來說， alphabeta 搜索所花的時間遠遠少于極大極小算法所花的時間 [9] 有前面的介紹我們可以了解，如果節(jié)點排列最理想的情形之下，使用Alphabeta 搜索建立的博弈樹的 節(jié)點個數(shù)為： W(d+1)/2 + Wd/2 +1 其中 W 是博弈樹的分支因子， d 是最大搜索深度。這個數(shù)字大約是極大極小搜索建立節(jié)點數(shù)的平方根的 2 倍左右。我們也將這棵理想的博弈樹叫做極小樹。在最差的情況之下， alphabeta 搜索建立的博弈樹的節(jié)點也和極大極小值一樣。 [10][11] 極小窗口搜索（ NegaScout 算法） 極小窗口搜索時 alphabeta 的變種。正常情況下，在搜索樹的根結點，也就是電腦棋手需要決策的局面，我們可以調用 alphabeta 算法來得到根結點的分值，同時也可以得 到應該走哪一步棋的結論。這時，調用該函數(shù)時，我們應使參數(shù) alpha=1000， beta=1000，這里 1000 是一個足夠大的數(shù)。這第 5 章 總體設計 26 是因為在根結點時，我們需要把窗口初始化成最大，在搜索過程中，隨著信息的獲得，這個窗口會漸漸地減小，最后收斂到根結點的最優(yōu)值上。 于是，我們可以對 ab 裁剪作一個改進：我們假定：假如第一步是最佳的移動，其后繼則次之，知道另一個節(jié)點被證明最佳的。在其中一個中間節(jié)點，其第一個分支以完整窗口（ a,b）搜索值并產(chǎn)生一個位于該窗口的值V，后繼的分支則先用零窗口例如（ v,v+1）搜索。 然后 ab 算法調用判斷一下，這個搜索是否能夠改善當前的最優(yōu)值，即局面 p 某一個子結點的實際最優(yōu)值是否比 alpha 大。如果比 alpha 小，則跳過這個子結點。進一步，當該子結點的返回值大于 alpha 時，從前面的分析中已經(jīng)知道，它的實際最優(yōu)值大于這個值，所以當返回值大于 beta 時，其實際最優(yōu)值也超過了 beta，這時就應該進行剪枝。這就是 NegaScout 搜索。下面給出偽代碼： //偽代碼 NegaScout Function negascout(node, depth, α, β) if node is a terminal node or depth = 0 return the heuristic value of node b := β (* initial window is (β, α) *) foreach child of node a := negascout (child, depth 1, b, α) if α a β (* check if nullwindow failed high*) a := negascout(child, depth 1, β, α) (* full research *) α := max(α, a) if α ≥ β return α * Beta cutoff *) b := α + 1 (* set new null window *) return α 在這個新算法中，增加的時間消耗是零窗口 ab 調用，而如果零窗口ab 調用的返回值比 alpha 小，那么就可以節(jié)約一個較大窗口的 ab 調用花費的時間，當零窗口 ab 調用的返回值比 beta 大時，則直接產(chǎn)生了進一步的剪枝。實踐證明，由于零窗口 ab 裁剪中產(chǎn)生了大量的剪枝，所以其實踐燕山大學本科畢業(yè)設計（論文） 27 消耗相對于大窗口 ab 調用而言是很小的?？偟恼f， NegaScout 搜索較 ab裁剪有效 [12]。 搜索引擎類在 。實現(xiàn)部分 。中 置換表 在搜索進行中，查詢所有的走步，經(jīng)常會在相同的或者不同的路徑上遇到相同的棋局，這樣的子樹就沒有必要重復搜索，把子樹根節(jié)點的估值、子樹的最好走步和取得這個值的深度信息保存在一個稱為置換表的數(shù)據(jù)結構中，下次遇到時直接運用即可。 但是，對不同的情況要區(qū)別對待。對于固定深度的搜索，如果前一次保存的子樹深度小于新節(jié)點要搜索的深度，還是要進行重新的搜索以保證所取得數(shù)據(jù)的準確程度。反之，如果置換表中保存的子樹信息表明，子樹的深 度大于或者等于當前的新節(jié)點要求的搜索深度，它的信息就可以直接運用了。 置換表增強如果和有效的 alphabeta 搜索結合使用，結果就會使實際搜索的博弈樹小于最小樹。博弈樹搜索的問題實際上是一個有向圖的搜索。那些在置換表中被命中的節(jié)點，就是有向圖中若干路徑的交叉點。只有避免這些交點被重復搜索，搜索過程中生成的搜索樹才有可能小于最小樹。這也是后來證明深度優(yōu)先的算法并不比最佳優(yōu)先的算法差的原因之一。 下面給出此算法的偽代碼： //偽代碼，置換表 Int alphabeta ( depth ,amp。alpha , amp。beta,) { Value = lookupTT(depth ,index)。//查詢置換表 If( value is valid)//查看此節(jié)點是否已在置換表中 Return vaule ； //已有，直接返回表中記錄值 //沒查到，進行 alphabeta 搜索過程， Search with alphabeta... 第 5 章 總體設計 28 //將搜索過的值記錄到置換表中 storeTOTT(depth,valu