Alfa-beta move ordering

Question

Mam podstawową implementację przycinania alfa-beta, ale nie mam pojęcia, jak poprawić porządek przenoszenia. Czytałem, że można to zrobić za pomocą płytkiego wyszukiwania, iteracyjnego pogłębiania lub przechowywania tabeli bestMoves to transition.

Wszelkie sugestie, jak wdrożyć jedną z tych ulepszeń w tym algorytmie?

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

• Węzeł reorganizację płytkie wyszukiwania jest trywialny: obliczyć wartość heurystyczną dla każdego dziecka państwa przed rekurencyjnie im sprawdzenia. Następnie posortuj wartości tych stanów [zstępujące dla maksymalnego wierzchołka i rosnąco dla min vertex] i rekurencyjnie wywołaj algorytm na posortowanej liście. Chodzi o to, że - jeśli stan jest dobry na płytkiej głębokości, to jest również bardziej prawdopodobne, że jest dobry również w głębokim stanie, , a jeśli to prawda, dostaniesz więcej przycinania.

  Sortowanie należy zrobić przed tym [w obu if i else klauzul]

  for (Move move : children) {

• przechowywania ruchów jest trywialny - wiele państw obliczane są dwukrotnie po zakończeniu obliczania dowolny stan , zapisz [z głębokością obliczeń! to jest improtant!] w HashMap. Pierwszą rzeczą, którą robisz po rozpoczęciu obliczania na wierzchołku - jest sprawdzenie, czy jest on już obliczony - i jeśli tak, to zwrócił wartość buforowaną. Idea stojąca za polega na tym, że wiele stanów jest dostępnych z różnych ścieżek, więc ten sposób pozwala wyeliminować zbędne obliczenia.

  Zmiany należy wprowadzić zarówno w pierwszym wierszu metody [coś w stylu: if (cache.contains((new State(board,depth,player)) return cache.get(new State(board,depth,player))] [przepraszam za brak elegancji i skuteczności - po prostu wyjaśnienie tutaj].
  Powinieneś także dodać cache.put(...) przed każdym oświadczeniem return.

Answer 2

Przede wszystkim należy zrozumieć uzasadnienie zamawiania ruchów w algorytmie przycinania alfa-beta. Alpha-beta daje taki sam wynik, jak minimax, ale w wielu przypadkach może to zrobić szybciej, ponieważ nie przeszukuje nieistotnych gałęzi.

Nie zawsze jest szybszy, ponieważ nie gwarantuje przycinania, jeśli w najgorszym wypadku nie będzie przycinał w ogóle i przeszukuje absolutnie to samo drzewo co minimax i będzie wolniejszy z powodu wartości a/b konserwacja. W najlepszym przypadku (maksymalne przycinanie) pozwala przeszukiwać drzewo 2 razy głębiej w tym samym czasie. Dla losowego drzewa może przeszukiwać 4/3 razy głębiej w tym samym czasie.

Move zamawiania mogą być realizowane w kilku sposobów:

1. masz eksperta domeny, który daje sugestię co ruchy są lepsze. Na przykład w szachy promocja pionka, przechwytywanie wysokiej wartości sztuk o niższej wartości kawałek są średnio dobre ruchy. W warcaby lepiej jest zabić więcej warcabów w ruchu, a następnie mniej checker i lepiej jest stworzyć królową.Tak więc funkcja generowania ruchu zwraca lepsze ruchy, zanim uzyskasz heurystykę tego, jak dobry jest ruch od oceny pozycji na 1 poziomie głębokości mniejszej (twoje płytkie wyszukiwanie/iteracyjne pogłębienie). Obliczono ocenę na głębokości n-1, posortowano ruchy, a następnie oceniano na głębokości n.

Drugie podejście, o którym wspomniałeś, nie ma nic wspólnego z zamówieniem przeniesienia. Ma to związek z faktem, że funkcja oceny może być droga, a wiele pozycji jest ocenianych wielokrotnie. Aby ominąć to, możesz zapisać wartości pozycji w haszcie po jej obliczeniu i użyć ponownie później.