如何加快Java中的minimax算法？

我想弄清楚如何提高這個算法的速度。它完美適用於兩款遊戲（2人遊戲，CPU vs人類），但問題是當我分配三個以上的樁（包含許多寶石，因此每個玩家可以拾取多於一個），計算機播放器永遠需要計算的招式：如何加快Java中的minimax算法？

public Object[] minimax(int depth, int player) { 

     if(hasPlayer1Won(player)){ 
      return new Object[]{get_default_input(1),1}; 
     }else if(hasPlayer2Won(player)){ 
      return new Object[]{get_default_input(1),-1}; 
     } 
     List<T> movesAvailable = getNextStates(); 

     if(movesAvailable.isEmpty()){ 
      return new Object[]{get_default_input(0), 0}; 
     } 
     int min = Integer.MAX_VALUE; 
     int max = Integer.MIN_VALUE; 
     T computersMove = getNextStates().get(0); 
     int i = 0; 
     for (T move: movesAvailable) { 
      makeAMove(move, player); 
      Object[] result = minimax(depth + 1, player == G.PLAYER1 ? G.PLAYER2 : G.PLAYER1); 
      int currentScore = (int)result[1]; 

      if(player == G.PLAYER1){ 
       max = Math.max(currentScore, max); 

       if(currentScore >= 0 && depth == 0) { 
        computersMove = move; 
       } 
       if(currentScore == 1){ 
        resetMove(move); 
        break; 
       } 
       if(i==movesAvailable.size() - 1 && max < 0){ 
        if (depth == 0){ 
         computersMove = move; 
        } 
       } 
      }else{ 
       min = Math.min(currentScore, min); 
       if(min == -1) { 
        resetMove(move); 
        break; 
       } 
      } 
      i++; 
      resetMove(move); 
     } 

     return new Object[]{computersMove, player == G.PLAYER1 ? max: min}; 
    }

來源

2016-04-29 Lapis Music

你知道[alpha-beta修剪]（https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning）嗎？ –

改進minimax算法的經典方法是用alpha-beta修剪 https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning – TheFooBarWay

好的問題，但「永遠」多久？ – djechlin

我已經成功測試了改進極小極大以下方法（用它玩井字棋和霸氣）：

Alpha beta pruning - 使用一種特殊這種類型的修剪的變體，結合Lazy evaluation - 基本上，而不是生成整個樹，我只是生成一個優化在每個層次上移動，併爲其他狀態行爲對保留懶惰持有者（應用懶惰評估方法，通過使用供應商並在與我持有的行動不同時調用它）調用它。
Heuristic pruning - 請參閱該書中有關啓發式的章節。我基本上只生成樹的第一個d分支，而不是確定性結果，我將該書中描述的啓發式函數應用到當前狀態以確定啓發式結果。無論何時移動（d + 1），我都會使用相同的方法生成另一個分支。這裏，d是你選擇的級別（最安全的方法是通過測試）
Parallel computing也看看這個，你可能會發現很難實現，但付出總有回報

第2選項給我帶來了大量的計算時間節省，這樣我就能夠最大限度地發揮Dominoering達到5x5的棋盤和啓發式達10x10（根據你想要它發揮多好，它可以更好）。

來源

2016-04-29 18:24:48

如何加快Java中的minimax算法？

回答

相關問題