迭代加深搜索選擇的壞行爲

我正在寫一個Nine Men's Morris遊戲，並且到目前爲止我有一個Negascout搜索，它工作得很好。然而，我想補充迭代加深，所以我想出了這個代碼：迭代加深搜索選擇的壞行爲

public Move GetBestMove(IBoard board, int depth) 
{   
    //Search limits (ms 
    this.maxTime = 9000; 

    //Set initial window 
    int alpha = -INFINITY, beta = INFINITY; 
    int val = 0; 

    //The move that will be returned 
    Move bestMove = null;  

    //Get list of moves for the current board 
    List<Move> moves = board.getMoves(); 

    //Get the time search has started 
    long startTime = System.nanoTime(); 

    //Iterate through the depths 
    for (curDepth = 1; ;) 
    { 
     maxDepth = curDepth; 

     //Reset alpha 
     alpha = -INFINITY; 

     //Reset the best score position 
     int bestPos = -1; 

     //Loop through all the moves 
     for (int i = 0, n = moves.size(); i < n; i++) 
     { 
      //Make the move 
      board.make(moves.get(i), true); 

      //Search deeper 
      val = negascout(board, curDepth, alpha, beta, startTime); 

      //Undo the move 
      board.undo(moves.get(i)); 

      //Keep best move 
      if (val > alpha) 
      { 
       bestMove = moves.get(i); 
       bestPos = i; 
      } 

      //Score missed aspiration window 
      if (val <= alpha || val >= beta) 
      { 
       alpha = -INFINITY; 
       beta = INFINITY; 

       //Go to next iteration 
       continue; 
      } 

      //Set new aspiration window 
      alpha = val - ASPIRATION_SIZE; 
      if (alpha < -INFINITY) 
       alpha = -INFINITY; 

      beta = val + ASPIRATION_SIZE; 
      if (beta > INFINITY) 
       beta = INFINITY; 
     } 

     //Move the best move to the top of the list 
     if (bestPos != -1) 
     { 
      moves.remove(bestPos); 
      moves.add(0, bestMove); 
     } 

     //Time check 
     double curTime = (System.nanoTime() - startTime)/1e6; 
     if (curTime >= maxTime || 
      val == board.getMaxScoreValue() || 
      val == -board.getMaxScoreValue()) 
      break; 

     //Increment current depth 
     curDepth++; 
    } 

    //Return the move 
    return bestMove; 
}

我也使用一個願望窗口。但是，搜索返回最糟糕的舉動！我認爲問題在於重新設置搜索窗口。搜索窗口應該移動到外部循環嗎？

來源

2013-03-20 Ivan-Mark Debono

如果它總是返回最壞的移動，你應該檢查你的選擇分支if（val> alpha）'不應該是其他方式嗎？ – 2013-03-20 09:45:43

No. val比alpha更好，因此這是目前最好的舉措 – 2013-03-20 10:09:28

的iterative deepening strategy：

for (depth = 1;; depth++) { 
    val = AlphaBeta(depth, -INFINITY, INFINITY); // or negascout 
    if (TimedOut()) 
     break; 
}

看起來你GetBestMove實現的一個不同。內循環（遍歷可能的移動）應該是negascout的一部分。此外，似乎只存儲了第一個深度級別（1層）的移動順序，但爲了使迭代加深搜索非常快，它需要在搜索到的每個深度進行移動排序。迭代深化不僅具有考慮時間的優點（在x秒後完成），而且還具有產生良好移動排序的優點。而且alphabeta或者negascout算法會從一個好的移動排序中受益（首先嚐試這個移動，因爲在之前的搜索中它是最好的）。實現移動訂單的常用方法是transposition table。

來自Bruce Moreland的文件The Main Transposition Table和Iterative Deepening對我很有幫助，我希望鏈接也能幫助你！

來源

2013-03-20 22:32:14

由於您使用negascout，你的初始呼叫應該像

val = -negascout(board, curDepth - 1, -beta, -alpha, startTime);

你的根通話是完全相反的相較於內部節點，所以這可以解釋爲什麼它返回最差的舉動。

來源

2013-05-30 04:39:28 Zong

迭代加深搜索選擇的壞行爲

回答

相關問題