【文章內(nèi)容簡介】 在上面的博弈樹中，如果我們令甲勝的局面值為 1，乙勝的局面值為1，而和局的值為 0。當輪到甲下棋時，甲定會選擇子節(jié)點值最大的下法；而輪到乙太原科技大學華科學院畢業(yè)設計（論文）8時，乙則會選擇子節(jié)點值最小的下法。所以，對于中間節(jié)點的值可以有如下計算方法：如果該節(jié)點所對應的局面輪到甲下棋，則該節(jié)點的值是其所有子節(jié)點中值最大的一個的值。而如果該節(jié)點所對應的局面輪到乙下棋，則該節(jié)點的值是其所有子節(jié)點中值最小的一個的值。對博弈樹的這個變化僅僅是形式上的，本質(zhì)上絲毫未變，但是這個形式更容易推廣以運用到一般實際的情形。既然建立整棵的搜索樹不可能，那么，為當前所面臨的局面找出一步好棋如何？也就是通過少量的搜索，為當前局面選擇一步較好的走法。在通常的棋局當中，一個局面的評估往往并不像輸、贏、平 3 種狀態(tài)這么簡單，在分不出輸贏的局面中棋局也有優(yōu)劣之分。也就是說，要用更細致的方法來刻畫局面的優(yōu)劣，而不是僅僅使用 0 三個數(shù)字刻畫 3 種終了局面。假定我們有一個函數(shù)可以為每一局面的優(yōu)劣評分。例如甲勝為+∞；乙勝為∞；和局為 0；這樣我們可以建立一棵固定深度的搜索樹，其葉子節(jié)點不必是終了狀態(tài)，而只是固定深度的最深一層的節(jié)點，其值由上述函數(shù)評出；對于中間節(jié)點，如同前面提到的那樣，甲方取子節(jié)點的最大值，乙方取子節(jié)點的最小值。這個評分的函數(shù)稱作靜態(tài)估值函數(shù)（Static Evaluation Function） 。用以取代超出固定深度的搜索。顯然，我們無法擁有絕對精確的靜態(tài)估值函數(shù)。否則，只要這個靜態(tài)估值函數(shù)就可以解決所有的棋局了。估值函數(shù)給出的只是一個較粗略的評分，在此基礎上進行的少量搜索的可靠性，理論上是不如前述的WIN， LOST，DRAW 三種狀態(tài)的博弈樹的，但這個方法卻是可實現(xiàn)的。利用具體的知識構成評估函數(shù)的搜索叫做啟發(fā)式搜索（Heuristic Search） 。估值函數(shù)在有些文獻中也稱為啟發(fā)函數(shù)（Heuristic Function） 。在博弈樹搜索的文獻當中，極大極小方法往往指的是基于靜態(tài)估值函數(shù)的有限深度的極大極小搜索。MinMax 算法是對弈的基礎思想?！∝摌O大值算法（Negamax Algorithm）普通的極大極小值算法看起來有一點笨，既然一方試圖取極大值而另一方試圖取極小值——也就是說——我們總要檢查哪一方要取極大值而哪一方又要取極小值，以執(zhí)行不同的動作。Knuth 和 Moore 在 1975 年提出了負極大值（Negamax）方法，消除了兩方的差別，而且簡潔優(yōu)雅。使用負極大值方法，太原科技大學華科學院畢業(yè)設計（論文）9博弈雙方都取極大值?！lphaBeta 搜索在極大極小搜索的過程中，存在著一定程度的數(shù)據(jù)冗余。舉一個最簡單的例子：在象棋博弈的過程中，如果某一個節(jié)點輪到甲走棋，而甲向下搜索節(jié)點時發(fā)現(xiàn)第一個子節(jié)點就可以將死乙（節(jié)點值為最大值） ，則剩下的節(jié)點就無需再搜索了，甲的值就是第一個子節(jié)點的值。這個過程，就可以將大量冗余的（不影響結果的）節(jié)點拋棄。AB CFEDACD EBF1 81 881 6a l p h a 剪 枝 示 例b e t a 剪 枝 示 例取 極 小 值 的 節(jié) 點取 極 大 值 的 節(jié) 點圖 lphaBeta 剪枝示例圖將上述這個情形推廣一下，設想有如圖 左半部所示的一棵極大極小樹的片斷，節(jié)點下面數(shù)字為該節(jié)點的值，節(jié)點 B 的值為 18，節(jié)點 D 的值為 16，由此我們可以判斷節(jié)點 C 的值將小于等于 16（取極小值） ；而節(jié)點 A 的值為節(jié)點 Max（B,C） ，為 18，也就是說不再需要估算節(jié)點 C 的其他子節(jié)點如 E、F 的值就可以得出父節(jié)點 A 的值了。這樣將節(jié)點 D 的后繼兄弟節(jié)點減去稱為 Alpha剪枝（alpha cutoff） 。設想有如圖 22 右半部所示的一棵極大極小樹的片斷，節(jié)點 B 的估值為 8，節(jié)點 D 的估值為 18，由此我們可以判斷節(jié)點 C 的值將大于等于 18（取極大值） ；而節(jié)點 A 的值為節(jié)點 Min（B,C ） ，為 8。也就是說不再需要求節(jié)點 C 的其他子節(jié)點如 E、F 的值就可以得出父節(jié)點 A 的值了。這樣將節(jié)點 D 的后繼兄弟節(jié)點減去稱為 Beta 剪枝（beta cutoff） ?！≈脫Q表（Transposition Table）在極大極小搜索的過程中，改進搜索算法的目標在于將不必搜索的（冗余）分枝從搜索的過程中盡量剔除，以達到搜索盡量少的分枝來降低運算量的目的。在先前談到的幾種搜索算法中，我們看到可以通過 AlphaBeta 剪枝來剪除太原科技大學華科學院畢業(yè)設計（論文）10兩種類型的冗余分枝/節(jié)點，但是已經(jīng)搜索過的節(jié)點不可以免于搜索。從圖 22 的極大極小樹的片斷中，我們可以看出，該片斷從節(jié)點 A 開始，有兩個分 B 和 C（為簡化問題，其他節(jié)點從略） ，B 有子節(jié)點 D，C 有子節(jié)點E，再往下 D 有子節(jié)點 F，E 有子節(jié)點 G。讀者可以看到，在極大極小樹的不同分枝上，存在著完全相同的節(jié)點。在上圖中，節(jié)點 F 和 G 完全相同。對于節(jié)點F，在搜索分枝的時候，就可能已經(jīng)搜索過了。那么，在搜索節(jié)點 G 的子節(jié)點時，我們能不能直接利用已經(jīng)搜索過的節(jié)點 F 的結果，而不是重新搜索一遍節(jié)點 G？想法是可行的。如果要利用已經(jīng)搜索過的節(jié)點的結果，我們就要用一張表把搜索過的節(jié)點記錄下來。然后在后續(xù)的搜索中，察看記錄在表中的這些結果，如果將要搜索的某個節(jié)點已有記錄，就直接利用記錄下來的結果。這種方法叫做置換表（Transposition Table，簡稱 TT） 。如果將 AlphaBeta 搜索過程中每一節(jié)點的結果都記錄下來，則在任意節(jié)點向下搜索之前先查看這些紀錄，就可避免上述重復的操作。但是這個置換表如何實現(xiàn)的？困難集中在時間和空間復雜度上。1．可能的節(jié)點可以認為是無窮多，將其存入一張表中要占據(jù)多少存儲空間呢？2．即使有無窮多內(nèi)存空間，一個節(jié)點要從表中找到自己對應的一項，需要花費多少時間？雖然有序表可用二分查找等快速的算法，但要維持表中內(nèi)容有序，又要進行大量排序操作，會耗費更多時間。如何解決？　哈希表（Hash Table）置換表的實現(xiàn)在時間和空間復雜度上的疑問。實際上已經(jīng)明確了要實現(xiàn)置換表必須要滿足如下條件：1．查找記錄中的節(jié)點數(shù)據(jù)時速度要非常快，最好是類似于隨機存取。2．將節(jié)點數(shù)據(jù)放入記錄的速度也要非常快。這就意味著數(shù)據(jù)項插入的過程不可有數(shù)據(jù)移動排序等操作。3．要能在有限的存儲空間內(nèi)進行?？梢岳霉１恚７椒ǖ乃枷霝槊恳粋€學過數(shù)據(jù)結構或算法課程的開發(fā)人員所熟知。對棋類博弈來說，定義一個巨大的數(shù)組，將每一局面記入其中，太原科技大學華科學院畢業(yè)設計（論文）11每一局面在數(shù)組中對應惟一的位置。這樣，將數(shù)據(jù)記入和取出就類似于隨機讀寫，不會有耗時的查找和插入過程。但是，以象棋而論，如果為每一局面在數(shù)組中對應一個與其他局面不同的位置的話，則組合的結果是全世界所有的計算機內(nèi)存加起來也不夠這樣一個數(shù)組用。那么讓每一局面在數(shù)組中對應惟一的位置，但并不保證數(shù)組中每一個數(shù)據(jù)項對應惟一的局面如何呢？比如將所有的局面對應在 106 單位的數(shù)組上。這樣，必然有一些局面對應在相同的位置上；但是對一次搜索而言，這種情況發(fā)生的概率并不高。一旦某個搜索過的局面在該數(shù)組中未找到，我們不過是對它進行AlphaBeta 搜索而已。不同的局面對應在數(shù)組中同一存儲單元上的情形，叫做沖突。我們將利用哈希方法實現(xiàn)置換表的方法敘述如下。定義哈希數(shù)組如下：structHASHITEM｛int64 checksum；//64 位哈希值，用以驗證表中數(shù)據(jù)是否是要找的局面int depth；//該表項求值時的搜索深度enum｛ exact，lower_bound，upper_bound ｝entry_type；//表項值的類型double eval； //所代表的節(jié)點的值｝hashtable［HASH_TABLE_SIZE］ ；//定義大小為 HASH_TABLE_SIZE 的哈希數(shù)組對要搜索的每一節(jié)點，計算出它的一個哈希值（hashIndex，通常是一個 32位數(shù)對哈希表大小取模）以確定此局面在哈希表中的位置。計算另一個 64 位的哈希值（Checksum）來校驗表中的數(shù)據(jù)項是否是所要的那一項。在對某一局面搜索之前，先查看哈希表項 hashTable［hashIndex］ ，如果 hashTable［hashIndex］.checksum==Checksum 并且 hashTable［hashIndex］.depth 大于等于最大搜索深度減去當前層數(shù)，就返回 hashTable［hashIndex］.eval 作為當前局面的估值。當對一個局面的搜索完成之后，將 Checksum、當前層數(shù)和估值結果保存到 hashTable［hashIndex ］當中，以備后面的搜索使用。　歷史啟發(fā)（History Heuristic）在前面的章節(jié)我們曾經(jīng)提到過，AlphaBeta 搜索的剪枝效率，幾乎完全取太原科技大學華科學院畢業(yè)設計（論文）12決于節(jié)點的排列順序。在節(jié)點排列順序處于理想狀態(tài)的情況下，AlphaBeta 搜索需遍歷的節(jié)點數(shù)僅為極大極小算法所需遍歷的節(jié)點數(shù)的平方根的兩倍左右。也就是說對一棵極大極小樹來說，如果極大極小搜索需遍歷 106 個節(jié)點求得結果，那么處于理想狀態(tài)的 AlphaBeta 搜索僅需遍歷約 2022 個節(jié)點就可求得結果。而在節(jié)點的排序最不理想的情況下，AlphaBeta 搜索要遍歷的結點數(shù)同極大極小算法一樣多。如何調(diào)整待展開的走法排列的順序，是提高搜索效率的關鍵。根據(jù)部分已經(jīng)搜索的結果來調(diào)整將要進行搜索的節(jié)點順序是一個可行的方向。通常一個局面經(jīng)搜索得知較好時，在其后繼節(jié)點當中往往有一些相似的局面，比如僅有一些無關緊要的棋子位置不同等等。這些相似的局面往往也是較好的?？梢酝ㄟ^一些較復雜的判斷來找出這些相似的局面，率先搜索，從而提高剪枝效率。但這一方法需要具體棋類相關的知識，并且往往判斷復雜而效果不彰。 提出了 History Heuristic 的方法，在基于 AlphaBeta 的搜索當中，一個好的走法可以定義如下：1．由其產(chǎn)生的節(jié)點引發(fā)了剪枝。2．未引發(fā)剪枝，但是其兄弟走法中的最佳者。在搜索的過程中，每當找到一個好的走法，就將與該走法相對應的歷史得分作一個增量，一個多次被搜索并確認為好的走法的歷史紀錄就會較高，當搜索中間節(jié)點時，將走法根據(jù)其歷史得分排列順序，以獲得較佳的排列順序。這比采用基于棋類知識而對節(jié)點排序的方法要容易得多。由于歷史得分表隨搜索而改變，對節(jié)點順序的排列也會隨之動態(tài)改變?！”菊滦〗Y本系統(tǒng)的可行性研究，從市場可行性、技術可行性方面著手進行考慮。市場可行性主要研究五子棋游戲的潛在市場；技術可行性主要研究系統(tǒng)開發(fā)軟硬件條件。綜上考慮，本項目的開發(fā)技術成熟、完備，運行環(huán)境優(yōu)良，具有一定的開發(fā)前景。算法分析部分主要介紹了五子棋游戲開發(fā)用到的算法。按照計算機下每一太原科技大學華科學院畢業(yè)設計（論文）13手棋時，應用算法的大致順序，本系統(tǒng)使用的主要算法有極大極小值算法、負極大值算法、AlphaBeta 算法、置換表技術、哈希表技術、歷史啟發(fā)等。其中的極大極小值算法是對弈算法的基礎。哈希表技術的使用，是置換表技術能夠?qū)崿F(xiàn)的基礎。各種算法的綜合使用，得以提高算法的效率。第 3 章　總體設計　總體設計過程總體設計過程通常由四個主要階段組成：系統(tǒng)體系結構設計，確定系統(tǒng)的具體體系結構實現(xiàn)方案；系統(tǒng)模塊設計，確定系統(tǒng)模塊層次；結構算法設計，確定軟件結構和典型算法；交互設計，確定系統(tǒng)的交互界面。總體設計的典型過程包括如下七個階段：（1）選取合理的體系結構方案（2）推薦最佳方案（3）系統(tǒng)模塊設計（4）數(shù)據(jù)結構和算法設計（5）交互設計（6）編寫文檔（7）審查和復審由于本系統(tǒng)應用到算法的設計，下面詳細描述一下第四個階段。高效率的程序基于良好的數(shù)據(jù)結構與算法，一般來說，數(shù)據(jù)結構與算法就是一類數(shù)據(jù)的表示及其相關的操作。從數(shù)據(jù)表示的觀點來看，存儲在數(shù)組中的一個有序整數(shù)表也是一種數(shù)據(jù)結構。算法是指對數(shù)據(jù)結構施