【文章內容簡介】 增加的搜索結點數(shù)相對比較少，同時當Move Ordering比較好的時候，大部分結點能夠產生 Beta剪枝的概率相當大，這樣我們就可以避免更繁重的全 AlphaBeta窗口搜索。 在采用 Minimal Window的 NegaScout算法中，每次遞歸擴展的時候，第一個節(jié)點用正常的 AlphaBeta窗口擴展，而后面的都用 Minimal Window進行擴展，這樣的話如果說最優(yōu)的孩子結點最先擴展，則此后的其他孩子結點通過 Alpha值對應的Minimal Window進行搜索都可以輕松剪枝，并且由于采用了 Minimal Window，AlphaBeta窗口縮到最小，剪枝也更容易，搜索節(jié)點也更少，反之，如果發(fā)現(xiàn)該擴展結點使用 Minimal Window不產生剪枝（ 即值小于 Beta），且值仍大于 Alpha，我們才用正常的 AlphaBeta窗口進行再搜索 (research)。 NegaScout算法偽代碼如下圖 [7]： int NegaScout( 局面 p。 int α, int β ) { // 計算局面 p的的極大極小值 int a, b, t, i。 生成局面 p的后繼局面 p1, p2, ..., pw。 if( w == 0 ) return ( Evalutate(p) )。 // 葉結點返回估值 a = α。 b = β。 中國礦業(yè)大學 2021 屆本科生畢業(yè)設計（論文） 第 11 頁 for( i = 1。 i = w。 i++ ) { t = NegaScout( pi, b, a )。 // 遞歸調用 .注意返回值取負 if(t 1amp。amp。 t β amp。amp。 i 1amp。amp。d maxdepth1) //FailHigh: a = NegaScout( pi, β, t )。 // 重新搜索 //t位于空窗之外 a = max( a, t )。 //但 t仍在原窗口之中 if( a = β ) return ( a )。 // (Beta)剪枝 b = a + 1。 // 設置新的空窗 } return ( a )。 } 圖 NegaScout剪枝實例圖 （加 粗 部分是與圖 ） 本系統(tǒng)在實現(xiàn)時 是就是使用 NegaScout 算法，并輔之以置換表 (Transposition Table)和歷史啟發(fā)（ History Heuristic）進行增強。在后面的章節(jié)中將給出部分源代碼。 置換表（ Transposition Table） 在一棵搜索樹中，不 少結點之間雖然是經過不同的路徑到達的，但其狀態(tài)是完全一致的。通過建立 Transposition Table 保存已搜索結點的信息，那么再次遇到相同狀態(tài)的結點時便可以套用之前的搜索結果。在 Transposition Table 中，記錄的信息為最優(yōu)著法、得分、深度等 。 為了快速檢測當前結點是否已經搜索過，我們一般對當前狀態(tài)進行編碼，然后利用 Hash 表的方式進行查找，這里采用的編碼方式是 Zobrist Hash 方法 [13]。 Zobrist Hash 方法：在程序啟動 或棋局開始 的時候，建立一個多維數(shù)組（在五子棋中是三維 ） Z[pieceType][boardWidth][boardHeight]， 其中 pieceType 是棋子種類，五子棋中為黑、白兩種； boardWidth 為棋盤寬度，五子棋為 15； boardHeight為棋盤高度，五子棋為 15。然后，將此數(shù)組中填滿隨機數(shù)。若要求某一局面的哈希值，則將棋盤上所有棋子在數(shù)組 Z 中對應的隨機數(shù)相加，即可得到。對于搜索過程中的每一個結點， Zobrist 方法用增量式計算方法，無須每次都加總所有棋子。在程序根部，作一次加總操作求出根節(jié)點的哈希值，當搜索一個新 結 點時只要將該位置對應的隨機數(shù) 和根 結 點哈希值相加即可。當對這個局面搜索完成后，再將搜索過程加上的值減去，就恢復了當前 結 點的哈希值。這是根據兩次異或同一個數(shù)結果保持不變的原理，避免重新計算整個棋盤的 Hash 值，并且位的異或在計算機內部運算中速度極快。 顯然，增量式計算哈希值的方法在思想上同 AlphaBeta 過程中的的MakeMove/UnMakeMove 是一致的。 Transposition Table 是一種空間換取時間的思想。 中國礦業(yè)大學 2021 屆本科生畢業(yè)設計（論文） 第 12 頁 Transposition Table 結合 AlphaBeta 搜索：在 AlphaBeta 搜索的過程中，一個結 點會出現(xiàn)以下三種情況之一： （ 1） Fail High，結點值至少 =Beta，但不知道其具體值。（ 2） Fail Low，結點值至多 =Alpha，但不知道具體值。（ 3） Exact，Alpha=結點分值 =Beta，此值為準確值。一般只有 Exact 類型，才可作為當前結點的準確值存入 Transposition Talbe，但 Fail High(=Beta)、 Fail Low(=Alpha)所對應的邊界值仍可幫助我們作進一步的剪枝，所以我們在 Transposition Table用字段 entry_type表示 類型，其中 Exact類型為準確值，其余的是表示值的范圍 [12]。 在搜索過程中，首先檢查 Transposition Table 中保存的結果能否直接代表當前結點的值或使當前結點產生 Alpha、 Beta 剪枝，不能的話則繼續(xù)進行該結點的搜索。 Transposition Table 的作用： （ 1）如果在 Transposition Table 訪問中能直接得到結果的話，則可以避免該結點以下子樹的搜索，減少了搜索時間。 （ 2）如果在 Transposition Table 中能查找到當前結點信息，并且存儲深度比當前結點大， 那么實際上是增加了當前子樹的搜索深度，也即增加了結果的準確性。 歷史啟發(fā)（ History Heuristic） 在介紹 NegaScout 算法中曾經提到， AlphaBeta 搜索的剪枝效率，幾乎完全取決于節(jié)點的排列順序（ Move Ordering） 。在節(jié)點排列順序處于理想狀態(tài)的情況下，AlphaBeta 搜索需要遍歷的節(jié)點數(shù)僅為極大極小算法所需遍歷的 結 點數(shù)的平方根的兩倍左右。也就是說對一棵極大極小樹來說，如果極大極小搜索需遍歷 106 個 結點求得結果，那么處于理想狀態(tài)的 AlphaBeta 搜索僅需遍歷 約 2021 個 結 點就可求得結果。而在 結 點的排序最不理想的情況下， AlphaBeta 搜索要遍歷的結點數(shù)同極大極小算法一樣多。如何調整待展開的走法排列的順序，是提高搜索效率的關鍵。根據部分已經搜索的結果來調整將要進行搜索的 結 點順序是一個可行的方向。 在基于 AlphaBeta 的搜索中，一個好的走法可以定義如下 [4]： （ 1）由其產生的 結 點引發(fā)了剪枝。 （ 2）未引發(fā)剪枝，但是其兄弟走法中最值者。 在搜索的過程中，每當找到一個好的走法，就將與該走法相對應的歷史得分作一個增量，一個多次被搜索并確認為好的走法的歷史紀錄 就會較高，當搜索中間 結點時，將走法根據其歷史得分排列順序，以獲得較佳的排列順序。 本 系 統(tǒng) 在實 現(xiàn) 時使 用 NegaScout 算法 并 配 合 上面 介 紹過 的 置換 表（ Transposition Table） 和歷史啟發(fā)（ History Heuristic） 增強 ，核心搜索算法源代碼 如下 [613]： 中國礦業(yè)大學 2021 屆本科生畢業(yè)設計（論文） 第 13 頁 // 主調例程必須將 alpha設為 COMP_LOSS,將 beta設為 COMP_WIN int CNegaScout_TT_HH::NegaScout_MAX( int depth, int alpha, int beta ) { // 用于偶數(shù)層 (從算起 ) int count, i。 int a, b, t。 int score。 if( depth 0 ) { i = IsGameOver( CurPosition, depth )。 if( i != 0 ) return i。 // 已分出勝負 ,返回極值 } // 查詢置換表看是否有當前節(jié)點的有效數(shù)據 score = LookUpHashTable( alpha, beta, depth, 0 )。 if( score != 66666 ) return score。 // 命中 ,直接返回查得數(shù)據 if( depth = 0 ) /* 葉結點 */ { score = m_pEvalEvaluate( CurPosition, 0 )。 // 將估值存入置換表 EnterHashTable( EXACT, score, depth, 0 )。 return score。 } count = CreatePossibleMove( CurPosition, depth, 0 )。 if( depth == m_nMaxDepth ) { // 在根節(jié)點設定進度條 ( 0, count )。 ( 1 )。 } for( i = 0。 i count。 ++i ) { // 取所有走法的歷史得分 m_MoveList[depth][i].score = GetHistoryScore( amp。m_MoveList[depth][i] )。 } // 將走法的歷史得分從大到小排序 MergeSort_Desc( m_MoveList[depth], count )。 中國礦業(yè)大學 2021 屆本科生畢業(yè)設計（論文） 第 14 頁 int bestmove = 1。 a = alpha。 b = beta。 int eval_is_exact = 0。 for( i = 0。 i count。 ++i ) { if( depth == m_nMaxDepth ) ( )。 // 走進度條 // 走子節(jié)點 MakeMove( amp。m_MoveList[depth][i], 0 )。 // 產生子節(jié)點的哈希值 Hash_MakeMove( amp。m_MoveList[depth][i], CurPosition )。 // 遞歸搜索子節(jié)點 ,對第個節(jié)點是全窗口 ,其后是空窗探測 t = NegaScout_MIN( depth1, b, a )。 if( t a amp。amp。 t beta amp。amp。 i 0 ) // FAILHIGH: { a = NegaScout_MIN( depth1, beta, t )。 /* 重新搜索 */ eval_is_exact = 1。 // 設數(shù)據類型為精確值 if( depth == m_nMaxDepth ) // 保留最佳走法 m_cmBestMove = m_MoveList[depth][i]。 bestmove = i。 // 記住最佳走法的位置 } // 恢復當前節(jié)點的哈希值 Hash_UnMakeMove( amp。m_MoveList[depth][i], CurPosition )。 // 撤銷子節(jié)點 UnMakeMove( amp。m_MoveList[depth][i] )。 if( a t ) { // 第次搜索命中 eval_is_exact = 1。 // 精確值 a = t。 if( depth == m_nMaxDepth ) // 保存最佳走法 m_cmBestMove = m_MoveList[depth][i]。 } if( a = beta ) { // 將下邊界存入置換表 EnterHashTable( LOWER_BOUND, a, depth, 0 )。 中國礦業(yè)大學 2021 屆本科生畢業(yè)設計（論文） 第 15 頁 // 將當前走法匯入歷史記錄 EnterHistoryScore( amp。m_