Chess Quiescence Search ist too large

Question

Я создал простой шахматный движок в C# в течение последнего месяца и добился неплохих успехов на нем. Он использует простой алгоритм Alpha-Beta.

Чтобы исправить эффект Horizon, я попытался реализовать Quiescence Search (и не удалось выполнить несколько раз, прежде чем он сработал). Сила двигателя, похоже, немного улучшилась, но это ужасно медленно!

Раньше я мог искать глубину в 6 слоев примерно за 160 секунд (где-то в midgame state), при спокойном поиске требуется около 80 секунд для перехода на глубину поиска 3!

Счетчик узлов грубой силы составляет около 20000 узлов на глубине 3, а счетчик покоя - до 20 миллионов!

Поскольку это мой первый шахматный движок, я действительно не знаю, являются ли эти цифры нормальными или если я допустил ошибку в моем алгоритме покоя. Я был бы признателен, если бы кто-то более опытный мог рассказать мне, каково обычно отношение узлов BF Nodes/Quiescent.

Btw, просто чтобы посмотреть на: (этот метод называется деревом BF когда searchdepth является 0)

public static int QuiescentValue(chessBoard Board, int Alpha, int Beta) 
    { 
     QuiescentNodes++; 

     int MinMax = Board.WhoseMove; // 1 = maximierend, -1 = minimierend 
     int Counter = 0; 
     int maxCount; 


     int tempValue = 0; 
     int currentAlpha = Alpha; 
     int currentBeta = Beta; 
     int QuietWorth = chEvaluation.Evaluate(Board); 

     if(MinMax == 1) //Max 
     { 
      if (QuietWorth >= currentBeta) 
       return currentBeta; 
      if (QuietWorth > currentAlpha) 
       currentAlpha = QuietWorth; 
     } 

     else   //Min 
     { 
      if (QuietWorth <= currentAlpha) 
       return currentAlpha; 
      if (QuietWorth < currentBeta) 
       currentBeta = QuietWorth; 
     } 




     List<chMove> HitMoves = GetAllHitMoves(Board); 
     maxCount = HitMoves.Count; 

     if(maxCount == 0) 
      return chEvaluation.Evaluate(Board); 


     chessBoard tempBoard; 

     while (Counter < maxCount) 
     { 
      tempBoard = new chessBoard(Board); 
      tempBoard.Move(HitMoves[Counter]); 
      tempValue = QuiescentValue(tempBoard, currentAlpha, currentBeta); 

      if (MinMax == 1) //maximierend 
      { 
       if (tempValue >= currentBeta) 
       { 
        return currentBeta; 
       } 

       if (tempValue > currentAlpha) 
       { 
        currentAlpha = tempValue; 
       } 

      } 

      else   //minimierend 
      { 
       if (tempValue <= currentAlpha) 
       { 
        return currentAlpha; 
       } 
       if (tempValue < currentBeta) 
       { 
        currentBeta = tempValue; 
       } 
      } 

      Counter++; 
     } 

     if (MinMax == 1) 
      return currentAlpha; 
     else 
      return currentBeta; 

    } 

Answer 1

Я не familliar с английской терминологии - это HitMove шаг где вы удаляете кусок с доски?

В этом случае мне кажется, что вы используете GetAllHitMoves, чтобы получить список «шумных» ходов для поиска покоя, которые затем оцениваются дальше, чем обычные 3 или 6 слоев. Это называется рекурсивно, так что вы оцениваете это снова и снова, пока есть возможные остатки HitMoves. Предоставление предела вашему поиску покоя должно исправить ваши проблемы с производительностью.

Что касается выбора предела для форсированного - вики гласят:

Modern chess engines may search certain moves up to 2 or 3 times deeper than the minimum.