搜索性能問題

Question

這是一個雙重問題。我已經把一個簡單的國際象棋引擎放在一起，它執行Alpha-Beta搜索，最後是靜止搜索。靜止搜索正在影響性能。問題是，這是一個可接受的性能影響？如果不是，那麼應該如何解決這個問題呢？

性能影響如下圖所示。

請注意，這些統計數據是在遊戲中考慮的。所述FEN是：

r3k2r/pb2qpbp/1pn1pnp1/2PpP3/2B2B2/2N2N2/PPPQ1PPP/R3K2R瓦特KQkq - 0 1

沒有虛靜：

• 6層片在82,069 ms（〜82秒）
• 5層在5,298毫秒（〜5.3秒）

隨着虛靜：

• 5層在83502毫秒（〜83秒）

我沒有做過使用靜止搜索6層的統計信息，但不會介意計算如果需要的話。

要注意的關鍵是添加靜止搜索等同於搜索一個額外的層。這是正常的嗎？

下面列出了C＃中的Alpha-Beta和Quiescence例程。它們基於chess programming wiki。

public static int AlphaBeta(Board board, int alpha, int beta, int depthLeft, int side) 
    { 
     if (depthLeft == 0) 
     { 
      return Quiescence(board, side, alpha, beta); 
     } 
     List<Move> moves = board.GenerateMoves(side); 

     //nodesCount += moves.Count; 

     BoardState state; 
     int score; 
     int oppositeSide = -1 * side; 

     for (int i = 0; i < moves.Count; i++) 
     { 
      state = board.GetCurrentBoardState(); 
      if (!board.MakeMove(moves[i])) 
      { 
       continue; 
      } 
      score = -AlphaBeta(board, -beta, -alpha, depthLeft - 1, oppositeSide); 
      board.RestoreState(state); 
      if (score >= beta) 
      { 
       return beta; 
      } 
      if (score > alpha) 
      { 
       alpha = score; 
      } 
     } 
     return alpha; 
    } 

虛靜：

private static int Quiescence(Board board, int side, int alpha, int beta) 
    { 
     int standingPat = Evaluation.EvaluateFromPerspectiveOf(board, side); 

     if (standingPat >= beta) 
     { 
      return beta; 
     } 

     if (alpha < standingPat) 
     { 
      alpha = standingPat; 
     } 

     int oppositeSide = -1 * side; 

     List<Move> moves = board.GenerateMoves(side); 
     int score; 
     BoardState state; 
     for (int i = 0; i < moves.Count; i++) 
     { 
      if (!board.IsCaptureMove(moves[i])) 
      { 
       continue; 
      } 

      //nodesCount++; 

      state = board.GetCurrentBoardState(); 
      if (!board.MakeMove(moves[i])) 
      { 
       continue; 
      } 
      score = -Quiescence(board, oppositeSide, -beta, -alpha); 
      board.RestoreState(state); 

      if (score >= beta) 
      { 
       return beta; 
      } 
      if (score > alpha) 
      { 
       alpha = score; 
      } 
     } 
     return alpha; 
    } 

Answer 1

好，quiscence搜索必須具備的性能損失，因爲它沿着一些線更深的搜索以穩定位置的評價。但它不應該是那麼多：'捕捉'線是非常罕見的，不可能像整個第6層一樣多。

您可能想要輸出評估位置的數量，然後查看由Quiscence處理的位置數。這個數字不應該很大。確保您的Quiscence搜索也使用alpha-beta修剪。此外，這些搜索時間（對於5層深度爲5秒，對於6層深度爲82秒）似乎非常緩慢。也許在測試截斷或搜索中的移動排序有問題（即您正在搜索完整的樹）或您的編譯器不執行任何優化。任何現代化的國際象棋引擎都能立刻達到5級的深度。

另一個提示：通常，Quiscence搜索使用一個單獨的移動生成器，它只生成捕獲，檢查和典當升級（這樣的生成器比普通的生成器更簡單，更快）。