【正文】 到一個好的走法，就將與該走法相對應(yīng)的歷史得分作一個增量，一個多次被搜索并確認為好的走法的歷史紀錄就會較高，當(dāng)搜索中間節(jié)點時，將走法根據(jù)其歷史得分排列順序，以獲得較佳的排列順序。 提出了 History Heuristic 的方法，在基于 AlphaBeta 的搜索當(dāng)中，一個好的走法可以定義如下：1．由其產(chǎn)生的節(jié)點引發(fā)了剪枝?？梢酝ㄟ^一些較復(fù)雜的判斷來找出這些相似的局面，率先搜索，從而提高剪枝效率。通常一個局面經(jīng)搜索得知較好時，在其后繼節(jié)點當(dāng)中往往有一些相似的局面，比如僅有一些無關(guān)緊要的棋子位置不同等等。如何調(diào)整待展開的走法排列的順序，是提高搜索效率的關(guān)鍵。也就是說對一棵極大極小樹來說，如果極大極小搜索需遍歷 106 個節(jié)點求得結(jié)果，那么處于理想狀態(tài)的 AlphaBeta 搜索僅需遍歷約 2022 個節(jié)點就可求得結(jié)果?！v史啟發(fā)（History Heuristic）在前面的章節(jié)我們曾經(jīng)提到過，AlphaBeta 搜索的剪枝效率，幾乎完全取太原科技大學(xué)華科學(xué)院畢業(yè)設(shè)計（論文）12決于節(jié)點的排列順序。在對某一局面搜索之前，先查看哈希表項 hashTable［hashIndex］ ，如果 hashTable［hashIndex］.checksum==Checksum 并且 hashTable［hashIndex］.depth 大于等于最大搜索深度減去當(dāng)前層數(shù)，就返回 hashTable［hashIndex］.eval 作為當(dāng)前局面的估值。定義哈希數(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ù)對哈希表大小取模）以確定此局面在哈希表中的位置。不同的局面對應(yīng)在數(shù)組中同一存儲單元上的情形，叫做沖突。這樣，必然有一些局面對應(yīng)在相同的位置上；但是對一次搜索而言，這種情況發(fā)生的概率并不高。但是，以象棋而論，如果為每一局面在數(shù)組中對應(yīng)一個與其他局面不同的位置的話，則組合的結(jié)果是全世界所有的計算機內(nèi)存加起來也不夠這樣一個數(shù)組用。對棋類博弈來說，定義一個巨大的數(shù)組，將每一局面記入其中，太原科技大學(xué)華科學(xué)院畢業(yè)設(shè)計（論文）11每一局面在數(shù)組中對應(yīng)惟一的位置。3．要能在有限的存儲空間內(nèi)進行。2．將節(jié)點數(shù)據(jù)放入記錄的速度也要非?？?。如何解決？　哈希表（Hash Table）置換表的實現(xiàn)在時間和空間復(fù)雜度上的疑問。但是這個置換表如何實現(xiàn)的？困難集中在時間和空間復(fù)雜度上。這種方法叫做置換表（Transposition Table，簡稱 TT） 。如果要利用已經(jīng)搜索過的節(jié)點的結(jié)果，我們就要用一張表把搜索過的節(jié)點記錄下來。對于節(jié)點F，在搜索分枝的時候，就可能已經(jīng)搜索過了。讀者可以看到，在極大極小樹的不同分枝上，存在著完全相同的節(jié)點。在先前談到的幾種搜索算法中，我們看到可以通過 AlphaBeta 剪枝來剪除太原科技大學(xué)華科學(xué)院畢業(yè)設(shè)計（論文）10兩種類型的冗余分枝/節(jié)點，但是已經(jīng)搜索過的節(jié)點不可以免于搜索。這樣將節(jié)點 D 的后繼兄弟節(jié)點減去稱為 Beta 剪枝（beta cutoff） 。設(shè)想有如圖 22 右半部所示的一棵極大極小樹的片斷，節(jié)點 B 的估值為 8，節(jié)點 D 的估值為 18，由此我們可以判斷節(jié)點 C 的值將大于等于 18（取極大值） ；而節(jié)點 A 的值為節(jié)點 Min（B,C ） ，為 8。AB CFEDACD EBF1 81 881 6a l p h a 剪 枝 示 例b e t a 剪 枝 示 例取 極 小 值 的 節(jié) 點取 極 大 值 的 節(jié) 點圖 lphaBeta 剪枝示例圖將上述這個情形推廣一下，設(shè)想有如圖 左半部所示的一棵極大極小樹的片斷，節(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é)點輪到甲走棋，而甲向下搜索節(jié)點時發(fā)現(xiàn)第一個子節(jié)點就可以將死乙（節(jié)點值為最大值） ，則剩下的節(jié)點就無需再搜索了，甲的值就是第一個子節(jié)點的值。使用負極大值方法，太原科技大學(xué)華科學(xué)院畢業(yè)設(shè)計（論文）9博弈雙方都取極大值。　負極大值算法（Negamax Algorithm）普通的極大極小值算法看起來有一點笨，既然一方試圖取極大值而另一方試圖取極小值——也就是說——我們總要檢查哪一方要取極大值而哪一方又要取極小值，以執(zhí)行不同的動作。在博弈樹搜索的文獻當(dāng)中，極大極小方法往往指的是基于靜態(tài)估值函數(shù)的有限深度的極大極小搜索。利用具體的知識構(gòu)成評估函數(shù)的搜索叫做啟發(fā)式搜索（Heuristic Search） 。否則，只要這個靜態(tài)估值函數(shù)就可以解決所有的棋局了。用以取代超出固定深度的搜索。例如甲勝為+∞；乙勝為∞；和局為 0；這樣我們可以建立一棵固定深度的搜索樹，其葉子節(jié)點不必是終了狀態(tài)，而只是固定深度的最深一層的節(jié)點，其值由上述函數(shù)評出；對于中間節(jié)點，如同前面提到的那樣，甲方取子節(jié)點的最大值，乙方取子節(jié)點的最小值。也就是說，要用更細致的方法來刻畫局面的優(yōu)劣，而不是僅僅使用 0 三個數(shù)字刻畫 3 種終了局面。既然建立整棵的搜索樹不可能，那么，為當(dāng)前所面臨的局面找出一步好棋如何？也就是通過少量的搜索，為當(dāng)前局面選擇一步較好的走法。而如果該節(jié)點所對應(yīng)的局面輪到乙下棋，則該節(jié)點的值是其所有子節(jié)點中值最小的一個的值。當(dāng)輪到甲下棋時，甲定會選擇子節(jié)點值最大的下法；而輪到乙太原科技大學(xué)華科學(xué)院畢業(yè)設(shè)計（論文）8時，乙則會選擇子節(jié)點值最小的下法。所以我們需要其它的算法來減少搜索的數(shù)量。一方面是因為很多情形根本就到達不了葉子節(jié)點。也就是說狀態(tài)圖搜索是純粹的或樹（OR tree） ，而博弈樹搜索是與或樹（AND/OR tree） 。只是狀態(tài)圖搜索僅有一個主體參加，僅是單方面做出的路徑選擇。博弈樹是從根部向下遞歸產(chǎn)生的一棵包含所有可能的對弈過程的搜索樹，這里稱為完全搜索樹。雙方就可以從其所面臨的棋局中選擇一步好棋。對于中間節(jié)點的值可以有如下計算方法：如果該節(jié)點所對應(yīng)的局面輪到甲下棋，則該節(jié)點的值是其所有子節(jié)點中值最佳（對甲而言）的一個的值；如果該節(jié)點所對應(yīng)的局面輪到乙走棋，則該節(jié)點的值是其所有子節(jié)點中值最差（對甲而言）的一個的值。如果我們令甲勝的局面值為 WIN，乙勝的局面值為 LOST，而和局的值為 DRAW。根的若干子節(jié)點則是由甲的每一種可能走法所生成的局面，而這些節(jié)點的子節(jié)點則是由與之相對的乙的每一種可能走法所生成的局面。顯然，我們可以依此構(gòu)建一棵博弈樹，將所有的走法羅列出來。然后又輪到甲走棋，對乙的下法甲又有若干種方法應(yīng)對。太原科技大學(xué)華科學(xué)院畢業(yè)設(shè)計（論文）7　博弈樹設(shè)想下五子棋的情形，兩人對弈，我們將其中一位叫做甲，另一位叫做乙。綜合分析表中幾種算法的效率，本系統(tǒng)按照計算機下每一手棋所應(yīng)用的算法的大致順序，采用的主要算法有博弈樹、負極大值算法、AlphaBeta 剪枝算法、置換表技術(shù)、哈希表技術(shù)、歷史啟發(fā)等。開局時計算機每走一步的平均耗時(ms)，如表 所示。　算法分析五子棋游戲的開發(fā)在搜索算法方面，可以有多種選擇。當(dāng)然，硬件的配置越高，系統(tǒng)的開發(fā)與運行會更流暢。VC++是非常成熟的開發(fā)工具，因此無論在安全性、可用性及可靠性等方面都毫無置疑，因此軟件方面是可行的。太原科技大學(xué)華科學(xué)院畢業(yè)設(shè)計（論文）6根據(jù)該系統(tǒng)目標來衡量所需的技術(shù)是否具備，一般可從軟硬件的性能要求、環(huán)境條件、操作人員水平和數(shù)量等方面去考慮和分析。新 開 局初 始 化 棋 盤對 弈勝 負 判 斷英 雄 榜圖 　系統(tǒng)流程圖本系統(tǒng)是一款休閑的小游戲，是人們?nèi)粘Ｉ願蕵返墓ぞ?。如果此局玩家的成績比英雄榜里的成績更好，則把玩家的姓名和成績記錄到英雄榜中，覆蓋原來的玩家名和成績。初始化棋盤完成后，玩家和計算機就可以在分析了當(dāng)前棋局以后下棋，即對弈階段。太原科技大學(xué)華科學(xué)院畢業(yè)設(shè)計（論文）5第 2 章　可行性研究與算法分析　本系統(tǒng)的可行性研究本系統(tǒng)要實現(xiàn)的目標：作為一個悠閑的小游戲軟件，首先應(yīng)該為用戶提供一套方便的操作方法，在游戲模式、用戶操作、反饋信息方面應(yīng)該有明確的說明，能夠讓大多數(shù)玩家能快速上手，使該游戲看上去是一款悠閑的精品。Visual C++ 的功能強大，用途廣泛。以前，繼承和派生一個類是一件很麻煩的事，而現(xiàn)在簡單了，只需在 Class Wizard 中指定一些必要信息，Visual C++ 將自動為你生成類的框架和代碼。AppWizard 將幫助 MFC 類庫的用戶自動生成一個運行程序框架——一個空的不能做任何事情的應(yīng)用程序，而用戶只需要在該框架的適當(dāng)部分添加擴充代碼就可以得到一個滿意的應(yīng)用程序。Visual C++ 提供一個功能強大的應(yīng)用程序生成向?qū)А狝ppWizard ，這也是其得意之處。用戶可利用 Visual C++ 以兩種方式編寫 Win32 應(yīng)用程序，一種方式是基于 Windows API 的 C 編程方式，另一種是基于 MFC 的 C++編程方式。另外，Visual C++ 還提供了很多向?qū)АＫ木幾g器、調(diào)試器、連接器、編輯器、資源編輯器都有所加強?！￠_發(fā)工具簡介Visual C++ 是 Microsoft 公司開發(fā)的基于 C/C++的面向?qū)ο蟮目梢暬商萍即髮W(xué)華科學(xué)院畢業(yè)設(shè)計（論文）4開發(fā)工具，它是 Visual Studio 中功能最為強大、代碼效率最高的開發(fā)工具。（6）智能性：智能化是這個游戲軟件的一大特色。（5）可擴展性及靈活性：系統(tǒng)的設(shè)計以方便未來業(yè)務(wù)的擴展和系統(tǒng)擴充為目標，系統(tǒng)要求能夠方便的升級，充分保護系統(tǒng)的投資。（3）高可靠性：一個實用的系統(tǒng)同時必須是可靠的，本系統(tǒng)通過合理而先進的結(jié)構(gòu)設(shè)計以及軟、硬件的優(yōu)化選型，可保證系統(tǒng)的可靠性與容錯性。充分滿足游戲玩家的需求，真正成為為玩家提供輕松、娛樂、休閑的工具。（1）實用性：系統(tǒng)以用戶需求為目標，以方便用戶為原則，同時融入先進的設(shè)計思想?！∠到y(tǒng)設(shè)計思想一個優(yōu)秀的游戲軟件，必須有一個正確的設(shè)計思想，通過合理地選擇數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)以及開發(fā)環(huán)境，構(gòu)成一個完善的體系結(jié)構(gòu)，才能充分發(fā)揮計算機應(yīng)用的優(yōu)勢。同時還有一大批的中生代棋手和充滿希望的“明日之星” 。中國作為五子棋的發(fā)源國，要對五子棋在下個世紀的發(fā)展起到世界性的推動作用。但與世界先進的五子棋技術(shù)相比，我們的棋藝水平還要繼續(xù)提高，所以我們要推廣五子棋，太原科技大學(xué)華科學(xué)院畢業(yè)設(shè)計（論文）3宣傳五子棋，爭取在較短的時間內(nèi)趕上和超過世界五子棋壇的先進水平。五子棋既有現(xiàn)代休閑方式所特有的特征“短、平、快” ，又有中國古典哲學(xué)所包含的高深學(xué)問“陰陽易理” ；它既有簡單易學(xué)的特點，為人民群眾所喜聞樂見，又有深奧的技巧；既能組織舉辦群眾性的比賽、活動，又能組織舉辦高水平的國際性比賽；它的棋文化源淵流長，具有東方的神秘和西方的直觀，它是中西方文化的交融點，也是中西方文化交流的一個平臺?，F(xiàn)代五子棋（連珠）的基本下法是：先由執(zhí)黑棋一方將一枚棋子落在天元點上，為了尊重對方和出于禮貌，持白棋的一方通常將盤面的第二手棋布在天元下方周圍。本世紀初五子棋傳入歐洲并迅速風(fēng)靡全歐。從此，連珠活動經(jīng)過了不斷的改良，主要是規(guī)則的變化(即對執(zhí)黑棋一方的限制)。據(jù)日本史料文獻介紹，中國古代的五子棋是經(jīng)由高麗(朝鮮)，于 1688 年至 1704 年的日本元祿時代傳到日本的。古代的五子棋的棋具與圍