需要帮助调试connect four minimax代码的alpha-beta修剪

Question

我正在使用minimax算法为connect four编写AI。为了增加深度，我正在使用alpha-beta修剪。然而，我的代码得到了错误的结果。我很难找出哪里出了问题。

    /**
  * Makes a turn. Edit this method to make your bot smarter.
  *
  * @return The column where the turn was made.
  */
 public double[] makeTurn(int[][] board, int id, int depth, double alpha, double beta) {
     //Round is the turn number. For the first couple of turns, I just place the disc in the center.
     double empty = 3;
     if(round == 1){
         double[] def = {3, 0};
         return def;
     }

     else if (round <4){

         if(board[4][3]==0){
             empty = 3;
         }
         else if(board[5][4]==0){
             empty = 4;
         }
         else{
             empty =2;
         }

         double[] def = {empty, 0};
         return def;
     }

     if(field.isFull(board)){

         //If the board is full return 0 - no one has an advantage
         double[] def = {0, 0};
         return def;
     }


     //System.out.println(field.toString());

     //best column for maximizing player
     double maxCol = 0;

     //best column for minimizing player
     double minCol = 0;

     //variables to store my score and opponents score in the current state
     double myScore = 0;
     double opponentScore = 0;

     for(int i = 0; i < 7;i++){

         //if column is full ignore it
         if(field.isColumnFull(i, board)){
             //System.out.println("is full");
         }
         else{

             //System.out.println(this.mCols + " " + this.mRows);
             int[][] tempBoard =  new int[this.mRows][this.mCols];
             for(int j = 0; j < mRows; j++){
                 tempBoard[j] = Arrays.copyOf(board[j], mCols);

             }

             //add disc to current column
             this.addDisc(i, id, tempBoard);


             /*If the depth is 0, we are at a leaf,
              * and we just run the heuristic function and
              * return the results.
              */
             if(depth == 0){
                 //System.out.println("here");

                 /*run the heuristic function twice,
                  * once for each player
                  */
                 myScore = getScore(tempBoard, this.myId);
                 opponentScore = getScore(tempBoard, this.opponentId);

                 //System.out.println(myScore + " " + opponentScore);
                 //System.out.println(myScore + " " + opponentScore);

                 /*If the game has ended,
                  * return the scores
                  */
                 if(id == this.myId && myScore ==Integer.MAX_VALUE){
                     myScore = Integer.MAX_VALUE/(maxDepth-depth+1);
                 }
                 else if(opponentScore == Integer.MIN_VALUE && id==this.opponentId){
                     myScore = Integer.MIN_VALUE/(maxDepth+1-depth);
                 }

                 /*If there is no winner in the current state
                  * the difference between the two players score
                  * is the score of the state
                  */
                 else{
                     myScore = (myScore - opponentScore);
                 }

                 //System.out.println(myScore + " " + i);
                 //System.out.println(myScore + " " + opponentScore);

             }

             /*If it is not a leaf node, check if the game has ended,
              * otherwise run a recursive call by decreasing the depth
              */
             else{
                 //System.out.println(depth);
                 if(id==this.myId){
                     if(getScore(tempBoard, this.myId)==Integer.MAX_VALUE){

                         double[] temp = {i, Integer.MAX_VALUE/(maxDepth+1-depth)};
                         //System.out.println(depth + " " + temp[1] + " " +i);
                         return temp;
                     }
                 }

                 else{
                     if(getScore(tempBoard, this.opponentId)==Integer.MIN_VALUE){
                         double[] temp = {i, Integer.MIN_VALUE/(maxDepth+1-depth)};
                         //System.out.println(depth + " " + temp[1] + " " +i);
                         return temp;
                     }
                 }


                 //the score and the respective column is returned
                 double[] res = makeTurn(tempBoard, id%2+1, depth-1, alpha , beta);
                 myScore = res[1];
             }

             if(depth==maxDepth){
                //System.out.println(myScore + " " +  maxCol +" " + i);
                 if(myScore>0){
                     //printBoard(tempBoard);
                 }
             }

             Random r = new Random();
             int prob = r.nextInt(10);


             /*If it is the maximizing players turn
              * update alpha
              */
             if (myScore > alpha && this.myId == id){
                 alpha = myScore;
                 maxCol = i;
             }
             else if(myScore == alpha && maxCol<4 && this.myId == id){
                 if(prob>4){
                     maxCol = i;

                 }
             }

             /*
              * Otherwise update beta
              */
             if(myScore < beta && this.opponentId == id){
                beta = myScore;
                minCol = i;
             }
             else if(myScore == beta && minCol < 4 && this.opponentId == id){
                 if(prob>4){
                     minCol = i;
                 }
             }


             /*This is where the pruning should occur. 
              * Without this the minimax algorithm runs correctly, but there
              * is no pruning. When I add this line, i get improved performance but 
              * incorrect results
              * 
              */
             if (beta<=alpha){
                 break;
             }


         }


     }

     //System.out.println(endTime - startTime);
     //System.out.println("opp max " + opponentMaxScore);
     //System.out.println("my max " + maxScore);
     //System.out.println("max diff " + maxScoreDiff);



     /*
      * Return best value according to player
      */
     double[] ans = new double[2];

     if(id ==  this.myId){
         ans[0] = maxCol;
         ans[1] = alpha;
     }

     else{
         ans[0] = minCol;
         ans[1] = beta;
     }

     //ans[0]= maxCol;
     //ans[1] = myScore;
     return ans;
 }

Answer 1

我对alpha-beta的理解是，两个玩家都需要检查alpha和beta，并且返回值需要受到alpha和beta的限制。即：

if (this.myId == id && myscore >= beta){
  alpha = beta;
  break;
}
else if (myScore > alpha && this.myId == id){
  alpha = myScore;
  maxCol = i;
}
else ...

...

if(this.opponentId == id && myScore <= alpha){
  beta = alpha;
  break;
}
else if(this.opponentId == id && myScore < beta){
  beta = myScore;
  minCol = i;
}
else ...