Ordine di spostamento alfa-beta

Question

Ho un'implementazione di base di potatura alfa-beta ma non ho idea di come migliorare l'ordine di spostamento. Ho letto che può essere fatto con una ricerca superficiale, approfondimento iterativo o memorizzazione dei migliori passaggi alla tabella di transizione.

Qualche suggerimento su come implementare uno di questi miglioramenti in questo algoritmo?

public double alphaBetaPruning(Board board, int depth, double alpha, double beta, int player) { 
    if (depth == 0) { 
     return board.evaluateBoard(); 
    } 

    Collection<Move> children = board.generatePossibleMoves(player); 
    if (player == 0) { 
     for (Move move : children) { 
      Board tempBoard = new Board(board); 
      tempBoard.makeMove(move); 
      int nextPlayer = next(player); 
      double result = alphaBetaPruning(tempBoard, depth - 1, alpha,beta,nextPlayer); 
      if ((result > alpha)) { 
       alpha = result; 
       if (depth == this.origDepth) { 
        this.bestMove = move; 
       } 
      } 
      if (alpha >= beta) { 
       break; 
      } 
     } 
     return alpha; 
    } else { 
     for (Move move : children) { 
      Board tempBoard = new Board(board); 
      tempBoard.makeMove(move); 
      int nextPlayer = next(player); 
      double result = alphaBetaPruning(tempBoard, depth - 1, alpha,beta,nextPlayer); 
      if ((result < beta)) { 
       beta = result; 
       if (depth == this.origDepth) { 
        this.bestMove = move; 
       } 
      } 
      if (beta <= alpha) { 
       break; 
      } 
     } 
     return beta; 
    } 
} 

public int next(int player) { 
    if (player == 0) { 
     return 4; 
    } else { 
     return 0; 
    } 
} 

Answer 1

• Nodo riordino con la ricerca poco profonda è banale: calcolare il valore euristico per ogni bambino dello stato prima ricorsivamente controllandoli. Quindi, ordina i valori di questi stati [decrescente per il vertice massimo e ascendente per il vertice minimo] e richiama ricorsivamente l'algoritmo nell'elenco ordinato. L'idea è: se uno stato è buono alla profondità minima di , è più probabile che sia buono anche allo stato profondo, e, se è vero, otterrai più pronte.

  L'ordinamento deve essere fatto prima questo [in entrambi i if e else clausole]

  for (Move move : children) {

• memorizzazione mosse è anche banale - molti stati sono calcolati due volte, quando si è terminato il calcolo qualsiasi stato , memorizzalo [con la profondità di il calcolo! è improtant!] in un HashMap. La prima cosa da fare quando si avvia il calcolo su un vertice - è controllare se è già calcolato - e se lo è, restituito il valore memorizzato. L'idea alla base di è che molti stati sono raggiungibili da percorsi diversi, quindi questo modo - è possibile eliminare calcoli ridondanti.

  Le modifiche devono essere eseguite sia nella prima riga del metodo [qualcosa come if (cache.contains((new State(board,depth,player)) return cache.get(new State(board,depth,player))] [mi scuso per mancanza di eleganza ed efficienza - solo spiegando un'idea qui].
  È inoltre necessario aggiungere cache.put(...) prima di ogni istruzione return.

Answer 2

Prima di tutto si deve capire il ragionamento dietro l'ordine di spostamento in un algoritmo di potatura alfa-beta. Alpha-beta produce lo stesso risultato di un minimax ma in molti casi può farlo più velocemente perché non ricerca attraverso i rami irrilevanti.

Non è sempre più veloce, perché non garantisce di potare, se nel peggiore dei casi non si potenzierà affatto e cercherà assolutamente lo stesso albero di minimax e sarà più lento a causa di un libro valori/b keeping. Nel migliore dei casi (potatura massima) consente di cercare un albero 2 volte più profondo allo stesso tempo. Per un albero casuale può cercare 4/3 volte più a fondo per lo stesso tempo.

Spostare ordinazione può essere implementato in un paio di modi:

1. voi hanno un esperto di dominio che ti dà il suggerimento di ciò che si muove sono migliori. Per esempio nella promozione degli scacchi di un pedone, catturare pezzi di alto valore con pezzi di valore inferiore sono in media mosse buone. Nelle pedine è meglio uccidere più pedine in una mossa quindi meno checker ed è meglio creare una regina.Quindi la tua funzione di generazione del movimento restituisce mosse migliori prima dello
2. ottieni l'euristica di quanto è buono il passaggio dalla valutazione della posizione al livello 1 di profondità inferiore (ricerca superficiale/approfondimento iterativo). Hai calcolato la valutazione alla profondità n-1, hai ordinato le mosse e poi valutato alla profondità n.

Il secondo approccio citato non ha nulla a che fare con l'ordine di spostamento. Ha a che fare con il fatto che la funzione di valutazione può essere costosa e molte posizioni vengono valutate molte volte. Per bypassare questo è possibile memorizzare i valori della posizione in hash una volta calcolato e riutilizzato in seguito.