content: package com.almasb.fxglgames.tictactoe.ai;
  
  import com.almasb.fxgl.dsl.FXGL;
  import com.almasb.fxgl.entity.Entity;
  import com.almasb.fxglgames.tictactoe.TicTacToeApp;
  import com.almasb.fxglgames.tictactoe.TileValue;
  import com.almasb.fxglgames.tictactoe.TileViewComponent;
  
  import java.util.ArrayList;
  import java.util.List;
  
  /**
   * The minimax algorithm is adapted from
   * https://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html
   *
   * @author Almas Baimagambetov (almaslvl@gmail.com)
   */
  public class MinimaxService extends TicTacToeAIService {
  
      private TileValue mySeed = TileValue.O;
      private TileValue oppSeed = TileValue.X;
      private TileValue[][] cells = new TileValue[3][3];
  
      @Override
      public void makeMove() {
          Entity[][] board = FXGL.<TicTacToeApp>getAppCast().getBoard();
  
          // the algorithm uses [row][col]
          for (int y = 0; y < 3; y++) {
              for (int x = 0; x < 3; x++) {
                  cells[y][x] = board[x][y].getComponent(TileViewComponent.class).getValue();
              }
          }
  
          int[] result = minimax(2, mySeed); // depth, max turn
  
          board[result[2]][result[1]].getComponent(TileViewComponent.class).mark(mySeed);
      }
  
      /**
       * Recursive minimax at level of depth for either maximizing or minimizing player.
       *
       * @return int[3] of {score, row, col}
       */
      private int[] minimax(int depth, TileValue player) {
          // 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 bestScore = (player == mySeed) ? Integer.MIN_VALUE : Integer.MAX_VALUE;
          int currentScore;
          int bestRow = -1;
          int bestCol = -1;
  
          if (nextMoves.isEmpty() || depth == 0) {
              // Gameover or depth reached, evaluate score
              bestScore = evaluate();
          } else {
              for (int[] move : nextMoves) {
                  // Try this move for the current "player"
                  cells[move[0]][move[1]] = player;
                  if (player == mySeed) {  // mySeed (computer) is maximizing player
                      currentScore = minimax(depth - 1, oppSeed)[0];
                      if (currentScore > bestScore) {
                          bestScore = currentScore;
                          bestRow = move[0];
                          bestCol = move[1];
                      }
                  } else {  // oppSeed is minimizing player
                      currentScore = minimax(depth - 1, mySeed)[0];
                      if (currentScore < bestScore) {
                          bestScore = currentScore;
                          bestRow = move[0];
                          bestCol = move[1];
                      }
                  }
                  // Undo move
                  cells[move[0]][move[1]] = TileValue.NONE;
              }
          }
          return new int[] {bestScore, bestRow, bestCol};
      }
  
      /**
       * Find all valid next moves.
       *
       * @return List of moves in int[2] of {row, col} or empty list if gameover
       */
      private List<int[]> generateMoves() {
          List<int[]> nextMoves = new ArrayList<int[]>(); // allocate List
  
          // If gameover, i.e., no next move
          if (hasWon(mySeed) || hasWon(oppSeed)) {
              return nextMoves;   // return empty list
          }
  
          // Search for empty cells and add to the List
          for (int row = 0; row < 3; ++row) {
              for (int col = 0; col < 3; ++col) {
                  if (cells[row][col] == TileValue.NONE) {
                      nextMoves.add(new int[] {row, col});
                  }
              }
          }
          return nextMoves;
      }
  
      /**
       * The heuristic evaluation function for the current board
       *
       * @return +100, +10, +1 for EACH 3-, 2-, 1-in-a-line for computer.
       *      -100, -10, -1 for EACH 3-, 2-, 1-in-a-line for opponent.
       *      0 otherwise
       */
      private int evaluate() {
          int score = 0;
          // Evaluate score for each of the 8 lines (3 rows, 3 columns, 2 diagonals)
          score += evaluateLine(0, 0, 0, 1, 0, 2);  // row 0
          score += evaluateLine(1, 0, 1, 1, 1, 2);  // row 1
          score += evaluateLine(2, 0, 2, 1, 2, 2);  // row 2
          score += evaluateLine(0, 0, 1, 0, 2, 0);  // col 0
          score += evaluateLine(0, 1, 1, 1, 2, 1);  // col 1
          score += evaluateLine(0, 2, 1, 2, 2, 2);  // col 2
          score += evaluateLine(0, 0, 1, 1, 2, 2);  // diagonal
          score += evaluateLine(0, 2, 1, 1, 2, 0);  // alternate diagonal
          return score;
      }
  
      /**
       * The heuristic evaluation function for the given line of 3 cells
       *
       * @return +100, +10, +1 for 3-, 2-, 1-in-a-line for computer.
       *      -100, -10, -1 for 3-, 2-, 1-in-a-line for opponent.
       *      0 otherwise
       */
      private int evaluateLine(int row1, int col1, int row2, int col2, int row3, int col3) {
          int score = 0;
  
          // First cell
          if (cells[row1][col1] == mySeed) {
              score = 1;
          } else if (cells[row1][col1] == oppSeed) {
              score = -1;
          }
  
          // Second cell
          if (cells[row2][col2] == mySeed) {
              if (score == 1) {   // cell1 is mySeed
                  score = 10;
              } else if (score == -1) {  // cell1 is oppSeed
                  return 0;
              } else {  // cell1 is empty
                  score = 1;
              }
          } else if (cells[row2][col2] == oppSeed) {
              if (score == -1) { // cell1 is oppSeed
                  score = -10;
              } else if (score == 1) { // cell1 is mySeed
                  return 0;
              } else {  // cell1 is empty
                  score = -1;
              }
          }
  
          // Third cell
          if (cells[row3][col3] == mySeed) {
              if (score > 0) {  // cell1 and/or cell2 is mySeed
                  score *= 10;
              } else if (score < 0) {  // cell1 and/or cell2 is oppSeed
                  return 0;
              } else {  // cell1 and cell2 are empty
                  score = 1;
              }
          } else if (cells[row3][col3] == oppSeed) {
              if (score < 0) {  // cell1 and/or cell2 is oppSeed
                  score *= 10;
              } else if (score > 1) {  // cell1 and/or cell2 is mySeed
                  return 0;
              } else {  // cell1 and cell2 are empty
                  score = -1;
              }
          }
          return score;
      }
  
      private int[] winningPatterns = {
              0b111000000, 0b000111000, 0b000000111, // rows
              0b100100100, 0b010010010, 0b001001001, // cols
              0b100010001, 0b001010100               // diagonals
      };
  
      /**
       * @return true if thePlayer wins
       */
      private boolean hasWon(TileValue thePlayer) {
          int pattern = 0b000000000;  // 9-bit pattern for the 9 cells
          for (int row = 0; row < 3; ++row) {
              for (int col = 0; col < 3; ++col) {
                  if (cells[row][col] == thePlayer) {
                      pattern |= (1 << (row * 3 + col));
                  }
              }
          }
          for (int winningPattern : winningPatterns) {
              if ((pattern & winningPattern) == winningPattern) return true;
          }
          return false;
      }
  }
  