1

我正在上一门人工智能课程，我们需要创建一个玩井字游戏的人工智能。

指导员指定在放置下一步时对 AI 的决策过程使用 alpha-beta 修剪。我现在遇到的问题是人工智能创建决策树并采取行动所需的时间。普通的 3x3 很好，3x4 和 4x3 需要一点时间，但是 4x4 第一步需要几分钟，而且我还没有从更大的游戏板上得到结果。

我使用的源代码：

  /** Get next best move for computer. Return int[2] of {row, >col} */ 
  @Override 
  int[] move() {
     int[] result = minimax(2, mySeed, Integer.MIN_VALUE, >Integer.MAX_VALUE);
        // depth, max-turn, alpha, beta
     return new int[] {result[1], result[2]};   // row, col
  }

  /** Minimax (recursive) at level of depth for maximizing or >minimizing player
      with alpha-beta cut-off. Return int[3] of {score, row, col}  >*/    
  private int[] minimax(int depth, Seed player, int alpha, int >beta) {
     // Generate possible next moves in a list of int[2] of {row, >col}.
     List<int[]> nextMoves = generateMoves();

     // mySeed is maximizing; while oppSeed is minimizing
     int score;
     int bestRow = -1;
     int bestCol = -1;

     if (nextMoves.isEmpty() || depth == 0) {
        // Gameover or depth reached, evaluate score
        score = evaluate();
        return new int[] {score, bestRow, bestCol};
     } else {
        for (int[] move : nextMoves) {
           // try this move for the current "player"
           cells[move[0]][move[1]].content = player;
           if (player == mySeed) {  // mySeed (computer) is >maximizing player
              score = minimax(depth - 1, oppSeed, alpha, beta)[0];
              if (score > alpha) {
                 alpha = score;
                 bestRow = move[0];
                 bestCol = move[1];

              }
           } else {  // oppSeed is minimizing player
              score = minimax(depth - 1, mySeed, alpha, beta)[0];
              if (score < beta) {
                 beta = score;
                 bestRow = move[0];
                 bestCol = move[1];
              }
           }
           // undo move
           cells[move[0]][move[1]].content = Seed.EMPTY;
           // cut-off
           if (alpha >= beta) break;
        }
        return new int[] {(player == mySeed) ? alpha : beta, >bestRow, bestCol};
     }
 }

如果需要，请提供源链接

导师还建议使用迭代加深搜索，但我是一个不知道怎么做的傻瓜。

4

0 回答 0