Ricerca di quiescenza di scacchi è troppo estesa

Question

Ho creato un semplice motore di scacchi in C# nell'ultimo mese e ho fatto alcuni progressi. Sta usando un semplice algoritmo Alpha-Beta.

Per correggere l'effetto Horizon, ho cercato di implementare la ricerca di Quiescence (e ho fallito diverse volte prima che funzionasse). La forza del motore sembra essersi migliorata un po ', ma è terribilmente lenta!

Prima, potevo cercare una profondità di 6 strati in circa 160 secondi (da qualche parte in uno stato di metà campo), con la ricerca di riposo, il computer impiega circa 80 secondi per ottenere una mossa sulla profondità di ricerca 3!

Il contatore nodo forza bruta si trova a circa 20000 nodi a profondità 3, mentre il contatore nodo inattivo è fino a 20 milioni!

Dato che questo è il mio primo motore di scacchi, non so davvero se quei numeri sono normali o se potrei aver fatto un errore nel mio algoritmo di quiescenza. Gradirei se qualcuno più esperto potesse dirmi quale sia la solita proporzione di nodi BF/nodi di quiescenza.

Btw, solo per avere uno sguardo a: (Questo metodo viene chiamato l'albero BF ogni volta che il 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

Non sono familliar con la terminologia inglese - è un HitMove una mossa dove rimuovi un pezzo dal tabellone?

In tal caso, mi sembra che si usi GetAllHitMoves per ottenere un elenco delle mosse "rumorose" per la ricerca di quiescenza che vengono poi valutate oltre i normali 3 o 6 strati. Questo è chiamato in modo ricorsivo, quindi lo valutate più e più volte finché ci sono gli HitMover rimasti. Fornire un limite alla ricerca della quiescenza dovrebbe risolvere i problemi di prestazioni.

Per quanto riguarda la scelta del limite per la ricerca quiescenza - afferma wiki:

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