Question

Using Java please implement a 4x4 Tic-Tac-Toe with Minimax with alpha-beta pruning. Please comment code heavily so I can follow along and understand the steps. Also, inlcude a screenshot of the final output. Do not include code for GUI, a GUI is not needed. Thank you

Answer 1

The recursive algorithm for "minimax with alpha-beta pruning" is as follows:

minimax(level, player, alpha, beta)  // player may be "computer" or "opponent"
if (gameover || level == 0)
   return score
children = all valid moves for this "player"
if (player is computer, i.e., max's turn)
   // Find max and store in alpha
   for each child
      score = minimax(level - 1, opponent, alpha, beta)
      if (score > alpha) alpha = score
      if (alpha >= beta) break;  // beta cut-off
   return alpha
else (player is opponent, i.e., min's turn)
   // Find min and store in beta
   for each child
      score = minimax(level - 1, computer, alpha, beta)
      if (score < beta) beta = score
      if (alpha >= beta) break;  // alpha cut-off
   return beta

// Initial call with alpha=-inf and beta=inf
minimax(2, computer, -inf, +inf)

The relevant changes (over the AIPlayerMinimax.java) are:

   /** 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};
      }
   }