Alpha-Beta Pruning Minimax Algorithm Not Providing Correct Optimal Move in Tic-Tac-Toe AI

Question

I'm working on a Tic-Tac-Toe AI implementation using the Alpha-Beta Pruning Minimax algorithm. The goal is to find the optimal move for the AI player (X) on the given board. However, I'm encountering an issue where the algorithm is not returning the correct optimal move index.

The optimal move for the AI player (X) should be at index 4, but my minimax function is returning bestAIMove.index = 8.

Here is my code:

let humanPlayer = "O";
let aiPlayer = "X";
let origBoard = ["X", "O", 2, "X", 4, 5, "O", 7, 8];
let MAX = {index: 99, score: 1000};
let MIN = {index: 99, score: -1000}
let fc = 0;

function checkAvailableMoves(board) {
    return board.filter(s => s !== "O" && s !== "X");
  }

function winning(board, player) {
    const winningCombinations = [
      [0, 1, 2],
      [3, 4, 5],
      [6, 7, 8],
      [0, 3, 6],
      [1, 4, 7],
      [2, 5, 8],
      [0, 4, 8],
      [2, 4, 6]
    ];
    return winningCombinations.some(combination =>
      combination.every(cell => board[cell] === player)
    );
  }

function max(a,b) {return a.score > b.score ? a : b;}
function min(a,b) {return a.score < b.score ? a : b;}

function minimax(newBoard, depth, player, alpha, beta) {
    const availableMoves = checkAvailableMoves(newBoard);
    let theBestMove = {};
    fc++
    if (winning(newBoard, humanPlayer)) {return { score: -10 + depth }}
    else if (winning(newBoard, aiPlayer)) {return { score: 10 - depth }}
    else if (availableMoves.length === 0) {return { score: 0 }};

    if (player === aiPlayer) {
      for (let i = 0; i < availableMoves.length; i++) {
        const index = availableMoves[i];
        newBoard[index] = player;
        let result = minimax(newBoard, depth + 1, humanPlayer, alpha, beta);
        result.index = index;
        alpha = max(alpha,result)
        newBoard[index] = index;
        if (alpha.score >= beta.score) {break}
      }
      theBestMove = alpha;
    } else if (player === humanPlayer) {
      for (let i = 0; i < availableMoves.length; i++) {
        const index = availableMoves[i];
        newBoard[index] = player;
        let result = minimax(newBoard, depth + 1, aiPlayer, alpha, beta);
        result.index = index;
        beta = min(beta, result);
        newBoard[index] = index;
        if (alpha.score >= beta.score){break}
      }
      theBestMove = beta;
    }
    return theBestMove;
  }

  bestAIMove = minimax(origBoard,0,aiPlayer,MIN,MAX)
  console.log(bestAIMove)
  console.log(fc)

What might be causing the problem?

Answer 1

There are two related issues in your code:

1. The min and max functions will choose b when the score is equal. But as you call min and max with result as second argument, this always gives precedence to a newer score. As you may get the same score back because of alpha beta pruning, you should give precedence to the move that "set the bar", i.e. to alpha or beta. So either swap the arguments you pass to min and max or change those functions so they choose a in case of equal scores.

2. result.index = index mutates an object that potentially is alpha or beta. You don't want this to happen. Deal with these objects as immutable. So instead do result = {...result, index}

With these two fixes it will work.

Demo

Here is your corrected code, with human player playing first, in an interactive snippet:

const humanPlayer = "X";
const aiPlayer = "O";
const MAX = {
  index: 99,
  score: 1000
};
const MIN = {
  index: 99,
  score: -1000
}

function checkAvailableMoves(board) {
  return board.filter(s => s !== "O" && s !== "X");
}

function winning(board, player) {
  const winningCombinations = [
    [0, 1, 2],
    [3, 4, 5],
    [6, 7, 8],
    [0, 3, 6],
    [1, 4, 7],
    [2, 5, 8],
    [0, 4, 8],
    [2, 4, 6]
  ];
  return winningCombinations.some(combination =>
    combination.every(cell => board[cell] === player)
  );
}

function max(a, b) {
  return a.score > b.score ? a : b;
}

function min(a, b) {
  return a.score < b.score ? a : b;
}

function minimax(newBoard, depth, player, alpha, beta) {
  const tab = "  ".repeat(depth);
  const availableMoves = checkAvailableMoves(newBoard);
  let theBestMove = {};
  if (winning(newBoard, humanPlayer)) {
    return {
      score: -10 + depth
    }
  } else if (winning(newBoard, aiPlayer)) {
    return {
      score: 10 - depth
    }
  } else if (availableMoves.length === 0) {
    return {
      score: 0
    }
  };

  if (player === aiPlayer) {
    for (let i = 0; i < availableMoves.length; i++) {
      const index = availableMoves[i];
      newBoard[index] = player;
      let result = minimax(newBoard, depth + 1, humanPlayer, alpha, beta);
      result = { ...result,
        index
      }; // don't mutate
      alpha = max(result, alpha) // args swapped
      newBoard[index] = index;
      if (alpha.score >= beta.score) {
        break
      }
    }
    theBestMove = alpha;
  } else if (player === humanPlayer) {
    for (let i = 0; i < availableMoves.length; i++) {
      const index = availableMoves[i];
      newBoard[index] = player;
      let result = minimax(newBoard, depth + 1, aiPlayer, alpha, beta);
      result = { ...result,
        index
      }; // don't mutate
      beta = min(result, beta); // args swapped
      newBoard[index] = index;
      if (alpha.score >= beta.score) {
        break
      }
    }
    theBestMove = beta;
  }
  return theBestMove;
}

// Added helper function
const gameOver = (board) => winning(board, "X") ? "X" :
  winning(board, "O") ? "O" :
  checkAvailableMoves(board).length ? "" :
  "-";

// I/O handling

function display(board) {
  document.querySelectorAll("td").forEach((td, i) => {
    td.textContent = isNaN(board[i]) ? board[i] : "";
  });
  document.querySelector("div").textContent = {
    [humanPlayer]: "You won!!!",
    [aiPlayer]: "CPU won!!!",
    "-": "It's a draw"
  }[gameOver(board)] || "";
}

function play(board, index) {
  if (gameOver(board)) return true;
  board[index] = "OX" [checkAvailableMoves(board).length % 2];
  display(board);
  return gameOver(board);
}

function playAiMove(board) {
  const {
    index
  } = minimax(board, 0, aiPlayer, MIN, MAX);
  if (!play(board, index)) listen(board);
}

function listen(board) {
  document.querySelector("table").addEventListener("click", e => {
    const td = e.target;
    if (td.tagName != 'TD') return listen(board);
    const index = td.cellIndex + 3 * td.parentNode.rowIndex;
    if (isNaN(board[index])) return listen(board); // User should retry...
    if (play(board, index)) return; // Game is over
    setTimeout(() => playAiMove(board), 500);
  }, {
    once: true
  });
}

function game() {
  const board = [...Array(9).keys()];
  if (aiPlayer === "X") playAiMove(board);
  else listen(board);

}
game();

table {
  border-collapse: collapse
}

td {
  border: 1px solid;
  width: 25px;
  height: 25px;
  text-align: center
}

<table>
  <tr>
    <td></td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td></td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td></td>
    <td></td>
    <td></td>
  </tr>
</table>
<div></div>