alpha-beta prunning與換位表，迭代加深

Question

我想實現alpha-beta min-max prunning增強換位表。我用這個僞代碼作爲參考：

http://people.csail.mit.edu/plaat/mtdf.html#abmem

function AlphaBetaWithMemory(n : node_type; alpha , beta , d : integer) : integer; 
    if retrieve(n) == OK then /* Transposition table lookup */ 
     if n.lowerbound >= beta then return n.lowerbound; 
     if n.upperbound <= alpha then return n.upperbound; 
     alpha := max(alpha, n.lowerbound); 
     beta := min(beta, n.upperbound); 
    if d == 0 then g := evaluate(n); /* leaf node */ 
    else if n == MAXNODE then 
     g := -INFINITY; a := alpha; /* save original alpha value */ 
     c := firstchild(n); 
     while (g < beta) and (c != NOCHILD) do 
      g := max(g, AlphaBetaWithMemory(c, a, beta, d - 1)); 
      a := max(a, g); 
      c := nextbrother(c); 
    else /* n is a MINNODE */ 
     g := +INFINITY; b := beta; /* save original beta value */ 
     c := firstchild(n); 
     while (g > alpha) and (c != NOCHILD) do 
      g := min(g, AlphaBetaWithMemory(c, alpha, b, d - 1)); 
      b := min(b, g); 
      c := nextbrother(c); 

    if g <= alpha then 
     n.upperbound := g; 
     store n.upperbound; 
    if g > alpha and g < beta then 
     n.lowerbound := g; 
     n.upperbound := g; 
     store n.lowerbound, n.upperbound; 
    if g >= beta then 
     n.lowerbound := g; 
     store n.lowerbound; 
return g; 

三個問題此算法：

1. 我相信我應該存儲深度（=距離到葉級）與每個保存換位僅當entry.depth> = currentDepth（=條目與葉級相距較遠或相等）時才使用表條目並使用條目。這在上面的僞代碼中沒有顯示，並沒有在那裏討論，我想確保我正確理解。

2. 我想存儲每個位置的最佳移動，以便將它用於移動排序並在搜索停止後提取最佳移動。在純粹的最小 - 最大值中，明顯哪個移動是最好的，但在用alpha-beta截止點迭代時哪個移動最好？我可以假設給定位置的最佳移動是循環結束時發現的最好的移動（伴隨切斷或不切斷）？

3. 在迭代深化方案中執行此算法時 - 我應該在每次深度增加前清除換位表嗎？我想不是，我想tu使用前一次迭代中存儲的位置，但我不確定這些信息是否適合進行更深入的搜索（應該在檢查表入口深度時）？

Answer 1

1. 你說得對。 entry.depth存儲換位表條目中信息的層數。所以你只能在entry.depth >= remaining_depth時使用這些信息。

   邏輯是我們不想使用比「正常」搜索更弱的結果。

   有時候，出於調試目的，條件變更爲：

   entry.depth == remaining_depth 
   

   這樣就避免了一些search instabilities。無論如何，它不能保證沒有換位表的搜索結果相同。

2. 並不總是最佳的存儲方式。

   當搜索失敗時，沒有「最佳移動」。我們唯一知道的是，沒有什麼舉措能夠產生大於alpha的分數。沒有辦法猜測哪個移動最好。

   因此，您應該只在下限（beta-cutoff即反駁移動）和精確評分（PV節點）中存儲哈希表中的移動。

3. 不，你不應該。隨着迭代深化，同樣的位置一次又一次到達並且換位表可以加速搜索。

   您應清除移動之間的換位表（或更好地使用其他entry.age字段）。