在國際象棋的Alpha-Beta搜索中實現殺手啓發式

Question

我明白殺手啓發式背後的想法以及爲什麼它有幫助。我正在努力的是如何在Alpha-Beta搜索例程中實現它。特別是如何確保只有兄弟節點的殺手動作首先被試用？僞代碼將非常有幫助。

Answer 1

在搜索樹的許多部分，殺手級動作很可能是一個很好的駁斥動作。所以嘗試殺手爲其他職位移動可能是一個好主意。

你可能會有不同數量的殺手移動每層，並在進入（層）時清除陣列（層+ 1），這會給你一個'兄弟姐妹'殺手。我想說，'+1'偏移量就像一個參數來調整：嘗試清除數組（ply + N），而不是看看性能是最好的（我想增加N會改善事情）。順便說一下，對發動機性能的評估是一項耗費大量資源的任務：通常發動機試圖解決一個測試套件，或者兩個具有不同參數的發動機正在進行比賽（比賽應該足夠長，例如100遊戲）之間來確定哪個更好。

Answer 2

我將討論實施。爲了讓兄弟節點的殺手的動作，用一個方案這樣

killerMoves[ply][slot] 

其中ply是從根部的距離（不搜索的深度）和slot是殺手的數量移動你想要的。這確保了兄弟節點首先被嘗試，因爲兄弟節點處於同一層。

要在獲得beta臨界值時插入殺手移動，可以將給定層的移動移至右側，可能會丟棄舊移動，然後插入新移動。通常情況下，當殺手通過其他機制訂購時，您不會存儲捕獲或散列移動。

for (int i = killerMoves[ply].Length - 2; i >= 0; i--) 
    killerMoves[ply][i + 1] = killerMoves[ply][i]; 
killerMoves[ply][0] = move; 

現在，當您執行移動排序（通過移動列表迭代前），就可以判斷此舉是否是招殺手鐗：

for (int slot = 0; slot < killerMoves[ply].Length; slot++) { 
    int killerMove = killerMoves[ply][slot]; 

    for (int i = 0; i < movesCount; i++) 
     if (moves[i] == killerMove) { 
      // moves[i] is a killer move so move it up the list 
      break; 
    } 
} 

你並不需要清除殺手移動對於一個層或類似的東西，因爲很可能殺手的移動是在同一層上出現的一系列相似位置上的很好的移動。

由於其他答案帶來了它，因此您可能不需要執行嚴格的測試，因爲這個殺手啓發式在理論上是合理的。您可以嘗試使用的殺手移動次數（2或3是常態）以及相對於其他良好移動（如捕獲）的順序。