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