卡住用alpha beta修剪的minmax算法

Question

我正在尝试用alpha beta修剪在java的tic tac toe游戏中实现minmax算法。当我编写代码时，我立即发现了一个例外，因此我试图让一些终端输出自己找到错误，并且发现它是由于最终返回中的错误结果导致的：算法最终返回[-1][-1]，得分-2147483646，当代码的其余部分尝试移动并将坐标放在字段中时，会导致异常。我做了一些方案来模拟一些动作和一些可能的树，但我找不到错误。

/* 
    * int field[][] is the board array, it may contains 0(empty), 1(opponent's seed), 2(computer's seed) 
    * nComputer = 2 (computer's seed) 
    * nPlayer = 1 (opponent's seed) 
    * computerMove = new int[3] 
    * remainingMoves has been calculated before the main call 
    */ 

    // Main call 
    computerMove = cMove(remainingMoves, nComputer,Integer.MIN_VALUE + 1, Integer.MAX_VALUE - 1); 
    field[computerMove[1]][computerMove[2]] = nComputer; // This line cause the exception!! 
    // MinMax alpha-beta pruning algorithm 
    private static int[] cMove(int depth, int player, int alpha, int beta) { 

     int[][] moveList = new int[3][10]; 
     moveList = generateMoves(field); // See below for details 

     int temp; 
     int score; 
     int bestR = -1; 
     int bestC = -1; 

     // check function retunrns 1(opponent wins), 2(computer wins), 0(draw) or -1(nothing) 
     if(moveList[0][0] == 0 || depth == 0) { 
      score = cScore(player); 

      return new int[] { score, bestR, bestC }; 
     } else { 
      for (int i = 1;i < moveList[0][0]; i++) { 
       // Trying to make a move 
       field[moveList[1][i]][moveList[2][i]] = player; 

       if(player == nComputer) { // Maximazing player 
        score = cMove(depth -1, nPlayer, alpha, beta)[0]; 
        if(score > alpha) { 
         alpha = score; 
         bestR = moveList[1][i]; 
         bestC = moveList[2][i]; 
        } 
       } else { // Minimizing player 
        score = cMove(depth -1, nComputer, alpha, beta)[0]; 
        if(score < beta) { 
         beta = score; 
         bestR = moveList[1][i]; 
         bestC = moveList[2][i]; 
        } 
       } 

       field[moveList[1][i]][moveList[2][i]] = 0; // Undo move 
       if(alpha >= beta) i = 10; // Cut-off 
      } 

      if(player == nComputer) temp = alpha; 
      else temp = beta; 

      return new int[] { temp, bestR, bestC }; 

     } 
    } 

    /* 
    * generateMoves function returns an array 3x10 where [0][0] is the number 
    * of possible moves and [0,1,2][1-9] are the score and the 
    * coordinates(rows and columns) of all the possible moves 
    */ 
    private static int[][] generateMoves(int[][] field) { 
     int[][] result = new int[3][10]; 
     int k = 0; 

     if(check(4) != -1) { 
      return result; 
     } 

     for (int i = 0; i < field.length; i++) { 
      for (int j = 0; j < field[0].length; j++) { 
       if (field[i][j] == 0) { 
        k++; 
        result[1][k] = i; 
        result[2][k] = j; 
       } 
      } 
     } 

     result[0][0] = k; 

     return result; 
    } 

    // cScore function assign a score for the actual node with an heuristic evaluation 
private static int cScore(int p) { 
    int score = 0; 
    score += cRow(p, 0, 0, 0, 1, 0, 2); 
    score += cRow(p, 1, 0, 1, 1, 1, 2); 
    score += cRow(p, 2, 0, 2, 1, 2, 2); 
    score += cRow(p, 0, 0, 1, 0, 2, 0); 
    score += cRow(p, 0, 1, 1, 1, 2, 1); 
    score += cRow(p, 0, 2, 1, 2, 2, 2); 
    score += cRow(p, 0, 0, 1, 1, 2, 2); 
    score += cRow(p, 0, 2, 1, 1, 2, 0); 
    return score; 
} 

private static int cRow(int player, int rOne, int cOne, int rTwo, int cTwo, int rThr, int cThr) { 
    int score = 0; 

    if (field[rOne][cOne] == nComputer) { 
     score = 1; 
    } else if (field[rOne][cOne] == nPlayer) { 
     score = -1; 
    } 

    if (field[rTwo][cTwo] == nComputer) { 
     if (score == 1) { 
      score = 10; 
     } else if (score == -1) { 
      return 0; 
     } else { 
      score = 1; 
     } 
    } else if (field[rTwo][cTwo] == nPlayer) { 
     if (score == -1) { 
      score = -10; 
     } else if (score == 1) { 
      return 0; 
     } else { 
      score = -1; 
     } 
    } 

    if (field[rThr][cThr] == nComputer) { 
     if (score > 0) { 
      score *= 10; 
     } else if (score < 0) { 
      return 0; 
     } else { 
      score = 1; 
     } 
    } else if (field[rThr][cThr] == nPlayer) { 
     if (score < 0) { 
      score *= 10; 
     } else if (score > 1) { 
      return 0; 
     } else { 
      score = -1; 
     } 
    } 

    return score; 
} 

我被困在这个问题上一个星期，我要疯了！ 在此先感谢和抱歉的英语不好，但它不是我的主要语言，我慢慢地想学习它

--------------------- - - - - - - - - - - - - - - - - - - - - - - 编辑 - - - --------------------------------------------------根据要求-----

添加校验功能：

// check function first check the state of 5 cells that needs to be filled to won([0,0][0,1][0,2][1,0][2,0]) 
public static int check(int nMove) { 
    int state = -1; 

    if(field[0][0] != 0) { 
     state = col(0,1); 
     if(state == 1 || state == 2) return state; // Win on first col 
     state = row(0,1); 
     if(state == 1 || state == 2) return state; // Win on first row 
     state = diagonal(1); 
     if(state == 1 || state == 2) return state; // Win on first diagonal 
    } 
    if (field[0][1] != 0) { 
     state = col(1,2); 
     if(state == 1 || state == 2) return state; // Win on second col 
    } 
    if (field[0][2] != 0) { 
     state = col(2,3); 
     if(state == 1 || state == 2) return state; // Win on third col 
     state = diagonal(2); 
     if(state == 1 || state == 2) return state; // Win on second diagonal 
    } 
    if (field[1][0] != 0) { 
     state = row(1,2); 
     if(state == 1 || state == 2) return state; // Win on second row 
    } 
    if (field[2][0] != 0) { 
     state = row(2,3); 
     if(state == 1 || state == 2) return state; // Win on third row 
    } 

    if(nMove == 8) return 0; // Draw 

    return state; 
} 
// Check if the entire row is filled (check rows from starting to n points) 
private static int row(int start, int n) { 
    int s = -1; 
    int k = 0; 
    int h = 0; 

    for (int i = start; i < n; i++) { 
     for (int j = 0; j < (field[0]).length; j++) { 
      if(field[i][j] == 1) { 
       k++; 
       if(k==3) s = 1; 
      } else if(field[i][j] == 2) { 
        h++; 
        if(h==3) s = 2; 
      } 
     } 
     k=0; 
     h=0; 
    } 

    return s; 
} 
// Check if the entire col is filled (check cols from starting to n points) 
private static int col(int start, int n) { 
    int s = -1; 
    int k = 0; 
    int h = 0; 

    for (int i = start; i < n; i++) { 
     for (int j = 0; j < (field).length; j++) { 
      if(field[j][i] == 1) { 
       k++; 
       if(k==3) s = 1; 
      } else if(field[j][i] == 2) { 
        h++; 
        if(h==3) s = 2; 
      } 
     } 
     k=0; 
     h=0; 
    } 

    return s; 
} 
// Check if the entire diagonal is filled (check first diagonal if n=1 and second diagonal if n=2) 
private static int diagonal(int n) { 
    int s = -1; 
    int k = 0; 
    int h = 0; 

    if(n == 1) { 
     for (int i = 0; i < (field).length; i++) { 
      int j = i; 
      if(field[i][j]== 1) { 
       k++; 
       if(k==3) s = 1; 
      } else if(field[i][j] == 2) { 
       h++; 
       if(h==3) s = 2; 
      } 
     } 
    } else if (n == 2) { 
     int j = 2; 
     for (int i = 0; i < (field).length; i++) { 
      if(field[i][j] == 1) { 
       k++; 
       if(k==3) s = 1; 
      } 
      else if(field[i][j] == 2) { 
       h++; 
       if(h==3) s = 2; 
      } 
      j--; 
     } 
    } else { } 

    return s; 
} 

Answer 1

假设你的板子比3×3大，否则蜱粘性脚趾有4个为中奖条件并没有什么太大的意义，你的例外将在这里引起：

for (int i = 0; i < field.length; i++) { 
     for (int j = 0; j < field[0].length; j++) { 
      if (field[i][j] == 0) { 
       k++; 
       result[1][k] = i; // out of bounds 
       result[2][k] = j; // out of bounds 
      } 
     } 
    } 

对于大小为A×B的字段，当板卡为空时，k将变得与A*B - 1一样大。对于A = B = 7，这将变为48，大于9，这是result[i]中允许的最大索引。

//编辑==================== =============
我有点困惑和不确定，你试图优化什么（计算机或玩家的最佳分数？），但我找到了解释结果的东西。

在每次递归调用中，您都有一个变量player。
根据其值更新alpha或beta。
在递归步骤结束时，您根据player的值返回alpha或beta。
但是，您更新alpha如果player == 2

if(player == 2) { // Maximazing player 
    score = cMove(depth -1, nPlayer, alpha, beta)[0]; 
    if(score > alpha) { 

但返回beta如果player == 2

if(player == 1) temp = alpha; 
    else temp = beta; 

所以，你总是alpha或MAX_VALUE - 1返回MIN_VALUE + 1为beta。
因此，if(score < alpha) {或if(score < beta) {对于每个步骤都将是错误的，不会调用基本情况。 你的递归看起来是这样的：

• 深度= 4，调用深度= 3
  • 深度= 3，调用深度= 2
    • 深度= 2，PLAYER1夺得，成绩是42
  • 深度= 3，更新阿尔法= 42，返回的β= MAX_VALUE - 1作为得分
• 深度= 4，call3返回MAX_VALUE - 1这是我测试所以没有什么改变，bestR和bestC逗留-1