Alpha-beta move ordering

Question

나는 알파 베타 제거의 기본 구현을 가지고 있지만 이동 순서를 개선하는 방법을 모른다. 나는 그것이 얕은 검색, 반복적 인 심화 또는 bestMoves to Transition 테이블을 가지고 수행 될 수 있다는 것을 읽었다.

이 알고리즘에서 이러한 개선 사항 중 하나를 구현하는 방법에 대한 제안이 있으십니까? 얕은 검색을 재정렬

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

• 노드는 간단하다 : 반복적으로 그들 확인하기 전에 상태 의 각 자녀에 대한 발견 값을 계산합니다. 그런 다음이 상태의 값을 정렬합니다 (최대 정점은 , 최소 정점은 오름차순). 정렬 된 목록에서 알고리즘을 재귀 적으로 호출합니다. 생각은 - 상태가 양호한 경우 얕은 깊이로, 깊은 상태에서도 좋을 가능성이 더 높습니다. 그리고 이것이 사실이라면 더 많은 가지 치기를 얻을 수 있습니다.

  소팅을 [두 if 및 else 절에서]이 전에 을 이루어 이동 기억

  for (Move move : children) {

• 도 사소한되어야

  - 많은 국가 두번 계산되며 을 모든 상태를 계산을 완료 할 때 , 그것을 저장할 [ 의 깊이와 함께! 그것은 improtant이다!] HashMap에서. 먼저 버텍스에서 계산을 시작할 때 을 수행합니다. 이미 계산 된 것이면 인지 확인하고, 그렇지 않으면 캐싱 된 값을 반환합니다. 뒤에있는 아이디어는 다른 경로에서 도달 할 수있는 상태가 많기 때문에이 길 - 중복 계산을 제거 할 수 있습니다.

  변경 사항은 [if (cache.contains((new State(board,depth,player)) return cache.get(new State(board,depth,player))과 같은 형식으로] [우아함과 효율성 부족으로 실례합니다. 여기에 아이디어를 설명하십시오] 두 줄에서 모두 변경해야합니다.
  각 return 문 앞에 cache.put(...)을 추가해야합니다.

Answer 2

먼저 알파 베타 제거 알고리즘에서 이동 순서의 추론을 이해해야합니다. Alpha-beta는 minimax와 동일한 결과를 산출하지만 많은 경우에 관련없는 분기를 검색하지 않기 때문에 더 빨리 수행 할 수 있습니다.

사실, 더 나쁜 경우에는 전혀 제거하지 않고 minimax와 동일한 트리를 절대적으로 검색하고/b 값으로 인해 더 느려지는 경우에도 프룬을 보장 할 수 없으므로 항상 더 빠르지는 않습니다. 유지. 가장 좋은 경우 (최대 가지 치기)에서는 동시에 두 번 깊은 나무를 검색 할 수 있습니다. 랜덤 트리의 경우 동일한 시간 동안 4/3 배 더 깊이 검색 할 수 있습니다.

이동 순서는 몇 가지 방법으로 구현 될 수있다 :

1. 당신은 당신에게 이동 더 나은 무엇인지 제안을 제공하는 도메인 전문가가 있습니다. 예를 들어 폰 (pawn)의 체스 판촉에서 낮은 가치의 조각으로 높은 가치의 조각을 포착하는 것은 좋은 움직임입니다. 체커에서는 이동 중에 체커를 더 많이 죽이고 체커를 줄이는 것이 좋습니다. 여왕을 만드는 것이 좋습니다.따라서 이동 생성 함수가 더 나은 움직임을 반환하기 전에
2. 당신은 깊이 1 단계에서 위치를 평가하는 것에서부터 이동이 얼마나 얕은 지 (당신의 얕은 검색/반복적 인 심화) 얼마나 좋은 지에 대한 경험적 방법을 얻을 수 있습니다. 깊이 n-1에서 평가를 계산하고, 움직임을 정렬 한 다음 깊이 n에서 평가합니다.

언급 한 두 번째 방법은 이동 순서와 아무 관련이 없습니다. 평가 기능이 값 비싸고 많은 직책이 여러 번 평가된다는 사실과 관련이 있습니다. 이 값을 무시하기 위해 계산 한 후 해쉬로 위치 값을 저장하고 나중에 재사용 할 수 있습니다.