Minimax에서 최선의 움직임을 추적하십시오.

Question

나는 이런 종류의 질문이 전에 물어 왔지만, 나는 의심을 해결할 수 없었다. 나는 bestFound 인스턴스 변수를 가지고 내 의심의 여지가 이유를 가지고있다

import java.util.*; 
import java.util.concurrent.*; 

public class MinimaxOthello implements Runnable 
{ 
    private CountDownLatch doneSignal;  
    private int maxDepth; 
    private int calls;  
    private OthelloMove bestFound; 
    private OthelloBoard board; 
    private static float INFINITY = Float.MAX_VALUE/1000;  
    private boolean solve = false; 
    private Comparator<OthelloMove> comparator = Collections.reverseOrder(new MoveComparator()); 

public MinimaxOthello (OthelloBoard board, int maxDepth, CountDownLatch doneSignal, boolean solve) 
{ 
    this.board = board;   
    this.bestFound = new OthelloMove(); 
    bestFound.setPlayer(board.getCurrentPlayer()); 
    this.maxDepth = maxDepth; 
    this.doneSignal = doneSignal;     
    this.solve = solve; 
} 

public OthelloMove getBestFound() 
{  
    return this.bestFound; 
} 
public void run() 
{   
    float val = minimax(board, bestFound, -INFINITY, INFINITY, 0); 
    System.out.println("calls: " + calls); 
    System.out.println("eval: " + val); 
    System.out.println(); 
    doneSignal.countDown();   
} 

private float minimax(OthelloBoard board, OthelloMove best, float alpha, float beta, int depth) 
{ 
    calls++;    
    OthelloMove garbage = new OthelloMove();    
    int currentPlayer = board.getCurrentPlayer(); 

    if (board.checkEnd()) 
    {       
     int bd = board.countDiscs(OthelloBoard.BLACK); 
     int wd = board.countDiscs(OthelloBoard.WHITE); 

     if ((bd > wd) && currentPlayer == OthelloBoard.BLACK) 
     {     
      return INFINITY/10; 
     } 
     else if ((bd < wd) && currentPlayer == OthelloBoard.BLACK) 
     {     
      return -INFINITY/10; 
     } 
     else if ((bd > wd) && currentPlayer == OthelloBoard.WHITE) 
     {     
      return -INFINITY/10; 
     } 
     else if ((bd < wd) && currentPlayer == OthelloBoard.WHITE) 
     {     
      return INFINITY/10; 
     } 
     else 
     {     
      return 0.0f; 
     } 
    } 
    if (!solve) 
    { 
     if (depth == maxDepth) 
      return OthelloHeuristics.eval(currentPlayer, board); 
    } 

    ArrayList<OthelloMove> moves = board.getAllMoves(currentPlayer); 
    if (moves.size() > 1) 
    { 
     OthelloHeuristics.scoreMoves(moves);   
     Collections.sort(moves, comparator); 
    } 

    for (OthelloMove mv : moves) 
    {          
     board.makeMove(mv);    
     float score = - minimax(board, garbage, -beta, -alpha, depth + 1);   
     board.undoMove(mv);    

     if(score > alpha) 
     { 
      alpha = score;     
      best.setFlipSquares(mv.getFlipSquares()); 
      best.setIdx(mv.getIdx());   
      best.setPlayer(mv.getPlayer());        
     } 

     if (alpha >= beta) 
      break;     

    }    
    return alpha; 
} 
} 

: 나는 최고의 움직임을 얻기 위해 아래의 클래스를 사용하는 간단한 오델로 엔진 (실제로 아주 잘한다),이 전화

OthelloMove garbage = new OthelloMove(); 

을 전달하면됩니까? 코드는 작동하지만 나에게는 매우 이상하게 보입니다!

최선의 방법이나 교장 변이를 얻는 '더 좋은 방법'이 있습니까? 정말 재귀 전문가가 아니며 디버깅 및 시각화가 매우 어렵습니다. 감사합니다.

** PS : 당신은 https://github.com/fernandotenorio/

Answer 1

당신이 minimax에 best 매개 변수를 없애하여 garbage에 대한 필요성을 제거 할 수 있습니다처럼 보이는 그것을 복제 한 다음 this.bestFound와 best을 대체 할 수 있습니다. 깊이 = 0 인 경우에만 bestFound의 속성을 설정하십시오.

초기에 빈 목록으로 this.bestFound을 생성하여 주요 변형을 가져올 수 있습니다. moves 루프가 실행되기 전에 새로운 이동을 만듭니다. if (score > alpha) 부분에서 지금까지와 같은 속성을 설정하십시오. 루프가 끝나면 목록으로 이동하십시오. 주요 변형은 목록의 반대가됩니다.

• run에 그것을 로컬 변수를 확인 인스턴스 변수로 bestFound 목록을 저장하는 대신과 : 그것은 중요 경우

  , 다음은 클래스의 다중 threadability을 개선하기 위해 할 수있는 몇 가지 변경 사항은 minimax

• 을 수정하지 말고 이동을 적용한 보드의 새 인스턴스를 반환하십시오. this을 돌연변이시키는 대신 보드를 복제하고 복제 코드에 복제 코드를 적용하여 구현할 수 있습니다. 그런 다음 복제 된 보드를 다음 minimax 호출에 전달하십시오.

Answer 2

minimax의 두 번째 인수는 최상의 이동을 반환하는 데 사용됩니다.

garbage의 비즈니스는 각 차례마다 최상의 이동을 유지하는 데 사용됩니다. 당신이 제공 한 코드로, 이것은 중요하지 않습니다. 그러나 현재 보드에서 게임 끝까지 일련의 동작을 만들고 싶다면 별도의 이동 객체로 만들어야합니다.

각 턴마다 가장 좋은 이동 객체를 사용하면 스레딩을 통해 여러 가지 트릭을 수행 할 수 있습니다. 첫째, Othello 인공 지능의 사고 시간을 제한하고 싶을 수도 있습니다. 각 단계별로 최고의 움직임을 개별적으로 추적하면 지금까지 가능한 최선의 움직임이 항상 있음을 의미합니다. 또한 보드에 대한 최선의 움직임을 캐싱하고 향후 minimax 검색에서이를 볼 수 있음을 의미합니다.

둘째, 최상의 이동을 병렬로 검색 할 수 있습니다. 각 미니 맥 호출이 독립적 일 때이를 구현하는 것은 간단합니다.