javascriptalgorithmp5.jstic-tac-toeminimax

I'm struggling with minimax algorithm in tic-tac-toe game


I'm currently trying to make a tic-tac-toe game using minimax algorithm. I'm using JavaScript with p5js framework for this project.

Here is the sketch.js code:

var rows = 3;
var cols = 3;
var scl = 1;
var board_width = cols * 100 * scl;
var board_height = rows * 100 * scl;
var board;
let player = 'x';
let ai = 'o';
let playerTurn;
let winner;

var resetBtn;

function setup() {
  
  createCanvas(400, 300);

  resetGame();

  resetBtn = createButton("Reset");
  resetBtn.position(320, 50);
  resetBtn.size(60, 20);
}

function draw() {

  resetBtn.mouseClicked(resetGame);

  winner = checkWinner();

  
  if (winner == 'x' || winner == 'o') {
    console.log(winner);
  }
  else if (winner == 't') {
    console.log("Tie");
  }
  else {
    if (playerTurn == false) {
      aiMove();
      playerTurn = true;
    }
  }

  drawBoard();
  
  
}

function mousePressed() {
  if (playerTurn == true) {
    for (let i = 0; i < rows; i++) {
      for (let j = 0; j < cols; j++) {
        if (mouseX > j * 100 && mouseX < (j * 100 + 100) && mouseY > i * 100 && mouseY < (i * 100 + 100)) {
          board[i][j] = player;
          playerTurn = false;
        }
      }
    }
  }
}

function aiMove() {
  let bestScore = -2;
  let score;
  let moveSpot = [];

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (board[i][j] == ' ') {
        board[i][j] = ai;
        score = miniMax(board, false);
        board[i][j] = ' ';
        if (score > bestScore) {
          bestScore = score;
          moveSpot = {i, j};
        }
      }
    }
  }
  board[moveSpot.i][moveSpot.j] = ai;

}

function miniMax(board, isMaximizing) {
  let result = checkWinner();

  if (result == 'x') {
    return -1;
  }
  else if (result == 'o') {
    return 1;
  }
  else if (result == 't') {
    return 0;
  }

  else if (isMaximizing) {
    let bestScore = -2;
    let score;
    for (let i = 0; i < rows; i++) {
      for (let j = 0; j < cols; j++) {
        if (board[i][j] == ' ') {
          board[i][j] = ai;
          score = miniMax(board, false);
          board[i][j] = ' ';
          bestScore = max(score, bestScore);
        }
      }
    }
    return bestScore;
  }
  else {
    let bestScore = 2;
    let score;
    for (let i = 0; i < rows; i++) {
      for (let j = 0; j < cols; j++) {
        if (board[i][j] == ' ') {
          board[i][j] = player;
          score = miniMax(board, true);
          board[i][j] = ' ';
          bestScore = min(score, bestScore);
        }
      }
    }
    return bestScore;
  }

}

function checkWinner() {
  
  let w = null;
  
  if (board[0][0] == 'x' && board[0][1] == 'x' && board[0][2] == 'x' ||
            board[1][0] == 'x' && board[1][1] == 'x' && board[1][2] == 'x' ||
            board[2][0] == 'x' && board[2][1] == 'x' && board[2][2] == 'x' ||
            board[0][0] == 'x' && board[1][0] == 'x' && board[2][0] == 'x' ||
            board[0][1] == 'x' && board[1][1] == 'x' && board[2][1] == 'x' ||
            board[0][2] == 'x' && board[1][2] == 'x' && board[2][2] == 'x' ||
            board[0][0] == 'x' && board[1][1] == 'x' && board[2][2] == 'x' ||
            board[2][0] == 'x' && board[1][1] == 'x' && board[0][2] == 'x') {
                return 'x';
        }
        else if (board[0][0] == 'o' && board[0][1] == 'o' && board[0][2] == 'o' ||
            board[1][0] == 'o' && board[1][1] == 'o' && board[1][2] == 'o' ||
            board[2][0] == 'o' && board[2][1] == 'o' && board[2][2] == 'o' ||
            board[0][0] == 'o' && board[1][0] == 'o' && board[2][0] == 'o' ||
            board[0][1] == 'o' && board[1][1] == 'o' && board[2][1] == 'o' ||
            board[0][2] == 'o' && board[1][2] == 'o' && board[2][2] == 'o' ||
            board[0][0] == 'o' && board[1][1] == 'o' && board[2][2] == 'o' ||
            board[2][0] == 'o' && board[1][1] == 'o' && board[0][2] == 'o') {
                return 'o';
        }

        let full = 0;
        for (let i = 0; i < 3; i++) {
            for (let j = 0; j < 3; j++) {
                if (board[i][j] == 'x' || board[i][j] == 'o') {
                    full ++;
                }
            }
        }

        if (full == 9) {
            return 't';
        }

        return w;
    
  return w;
}

function drawBoard() {
  // draw board
  stroke(0);
  strokeWeight(7);
  line(board_width / 3, 0, board_width / 3, board_height);
  line(board_width / 3 * 2, 0, board_width / 3 * 2, board_height);
  line(0, board_height / 3, board_width, board_height / 3);
  line(0, board_height / 3 * 2, board_width, board_height / 3 * 2);

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (board[i][j] == 'o') {
        circle(j * 100 + 50, i * 100 + 50, 80);
      }
      else if (board[i][j] == 'x') {
        line(j * 100 + 10, i * 100 + 10, j * 100 + 80, i * 100 + 80);
        line(j * 100 + 80, i * 100 + 10, j * 100 + 10, i * 100 + 80);
      }
    }
  }
}

function resetGame() {
  clear();
  winner = null;
  board = [];
  playerTurn = true;
  background(255);

  for (let i = 0; i < rows; i++) {
    let row = [];
    for (let j = 0; j < cols; j++) {
      row[j] = ' ';
    }
    board.push(row);
  }
}

The problem is shown in the picture. As you, the player make first move, if you choose spot 2 then 4 then 6, the ai doesn't go to spot 9 to win but go to spot 3 instead. screenshot

I tried this tactic in an example on this website:

https://www.freecodecamp.org/news/how-to-make-your-tic-tac-toe-game-unbeatable-by-using-the-minimax-algorithm-9d690bad4b37/

and got similar result.

Is this a problem with the algorithm implementation or something else?


Solution

  • The algorithm is correct. For the example you gave, the third move for player O may not look good, but it is actually a winning move. Not the fastest win, but still ensuring a win. Your algorithm does not have any notion of preferring faster wins over slower wins, so that may give the false impression that the minimax algorithm is not doing it right -- but it does.

    To favour faster wins over slower wins, make these changes:

    Here is the relevant code with those changes made (comments indicate where):

    function miniMax(board, isMaximizing) {
      let result = checkWinner();
      if (result == 'x') {
        return -9; // extreme
      }
      else if (result == 'o') {
        return 9; // extreme
      }
      else if (result == 't') {
        return 0;
      }
    
      else if (isMaximizing) {
        let bestScore = -10; // extreme
        let score;
        for (let i = 0; i < rows; i++) {
          for (let j = 0; j < cols; j++) {
            if (board[i][j] == ' ') {
              board[i][j] = ai;
              score = miniMax(board, false);
              board[i][j] = ' ';
              bestScore = Math.max(score, bestScore);
            }
          }
        }
        // Diminish the magnitude of the score by one point 
        return bestScore - Math.sign(bestScore);
      }
      else {
        let bestScore = 10; // extreme
        let score;
        for (let i = 0; i < rows; i++) {
          for (let j = 0; j < cols; j++) {
            if (board[i][j] == ' ') {
              board[i][j] = player;
              score = miniMax(board, true);
              board[i][j] = ' ';
              bestScore = Math.min(score, bestScore);
            }
          }
        }
        // Diminish the magnitude of the score by one point 
        return bestScore - Math.sign(bestScore);
      }
    }
    

    Now the AI will play a win-in-1 move in the example game.