java - Minimax算法陷入无限循环

Question

所以我在这个问题上已经有一段时间了。我正在尝试实现 minimax 算法来玩一个名为 mancala 的游戏。据我所知，我的代码应该可以工作，但是由于某种原因，当函数递归调用自身时，即使我知道它达到了游戏结束状态并返回了一些值，它也会继续评估为 0。我也知道它的计算结果为 0，因为 maxval 的初始数字是 0。如果有人能帮我弄清楚这一点，我会非常感激。

下面是实现的极小极大算法。请忽略深度参数，初始状态调用的棋盘包含数字 3 直到 12 并且不包括 6，maxTurntrue（最大优先）move -1，alpha -1和beta 37（最高可能分数为 36）

private int[] miniMax(int[] board, boolean maxTurn, int move, int alpha, int beta, int depth){
   int[] newState = new int[board.length];

   if(endGame(board) == true){
      int[] endReturn = new int[2];
      for(int i = 0; i < 6; i++){ board[6] += board[i];}
      endReturn[0] = board[6];  System.out.println("end state value: " + board[6]);
      endReturn[1] = move;
      return endReturn;
   }
   if(maxTurn == true){
      int[] maxEval = new int[2];
      maxEval[0] = -1;
      for(int i = 0; i < 6; i++){
         newState = Arrays.copyOf(board, board.length);
         boolean goAgain = false;
         if(board[i] == 0) continue;
         int j = newState[i];
         newState[i] = 0;
         int k = i + 1;
         while(j > 0){
            if(k == 13)k = 0;
            newState[k]++;
            j--;
            k++;
         }
         if(k == 6) goAgain = true;

         if(k < 6 && newState[12 - k] > 0 && newState[k] == 1){
            newState[6] = newState[6] + newState[12 - k] + 1;
            newState[12 - k] = 0;
            newState[k] = 0;
         }

         int[] eval = new int[2];
         eval = miniMax(newState, goAgain, i, alpha, beta, depth--);

         System.out.println("eval value: " + eval[0]);
         if(eval[0] > alpha){
            alpha = eval[0];
         }
         System.out.println("alpha value: " + alpha);
         if(beta <= alpha) break;

         if(eval[0] > maxEval[0]){
            maxEval[0] = eval[0];   System.out.println("move given: " + i);
            maxEval[1] = i;
         }

      }   //System.out.println("maxEval given moveValue: " + maxEval[1]);
      return maxEval;

   }
   else{
      int[] minEval = new int[2];
      for(int i = 7; i < 13; i++){
         newState = Arrays.copyOf(board, board.length);
         boolean max = true;
         if(board[i] == 0) continue;
         int  j = newState[i];//  System.out.println("this is j: " + j);
         newState[i] = 0;
         int k = i;
         while(j > 0){
            k++;
            if(k == 6)k = 7;
            if(k == 14)k = 0;
            j--;
            newState[k]++;
         }
         if(k == 13) max = false;

         if(k > 6 && k<13 && newState[12 - k] > 0 && newState[k] == 1){
            newState[13] = newState[13] + newState[12 - k] + 1;
            newState[12 - k] = 0;
            newState[k]--;
         }
         int[] eval = new int[2];
         eval = miniMax(newState, max, i, alpha, beta, depth--);
         if(minEval[0] > eval[0]){
            minEval[0] = eval[0];
            minEval[1] = i;
         }
         if(eval[0] < beta){
            beta = eval[0]; System.out.println("beta: " + beta);
         }
         if(beta <= alpha) break;

      }//System.out.println("maxEval given moveValue: " + maxEval[1]);
      return minEval;
   }
}

标签： javaminimaxalpha-beta-pruning