如何加快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算法？

回答

相关问题