Minimax in Tic-Tac-Toe not returning correct value

Question

I'm trying to write a Tic-Tac-Toe game and decided to use the MiniMax algorithm, but I'm having trouble implementing it. For example: on a

  board = [
          "E", "E", "X",
          "E", "E", "X",
          "E", "O", "O"
          ];

It's the AI's turn and the function returns AiMove { score: -10, coordinates: 0 } as the best move. I've been trying to debug for quite some time now, but the recursive nature of the function and the amount of possible game trees, early game states in particular, are quite hard to follow and debug.

Could someone lend a hand?

https://jsfiddle.net/LdLqk1z8/4/

var factions = {
  AIplayer: "X",
  humanPlayer: "O"
};

var gameResults = {
  winner: ""
};

var emptyCells = function(board) { //check for empty cells and return an array with the number of empty cells
  var indices = [];
  for (var itr = 0; itr < 9; itr++) {
    if (board[itr] === "E") {
      indices.push(itr);
    }
  }
  return indices;
};

var isGameOver = function(board) {
  var tile = board;

  //check for victory conditions
  for (var i = 0; i <= 6; i = i + 3) {
    if (tile[i] !== "E" && tile[i] === tile[i + 1] && tile[i + 1] === tile[i + 2]) {
      if (factions.AIplayer === tile[i]) {
        gameResults.winner = "AIplayer";
      } else if (tile[i] === factions.humanPlayer) {
        gameResults.winner = "humanPlayer";
      }
      return true;
    }
  }

  for (var i = 0; i <= 2; i++) {
    if (tile[i] !== "E" && tile[i] === tile[i + 3] && tile[i + 3] === tile[i + 6]) {
      if (factions.AIplayer === tile[i]) {
        gameResults.winner = "AIplayer";
      } else if (tile[i] === factions.humanPlayer) {
        gameResults.winner = "humanPlayer";
      }
      return true;
    }
  }

  for (var i = 0, j = 4; i <= 2; i = i + 2, j = j - 2) {
    if (tile[i] !== "E" && tile[i] === tile[i + j] && tile[i + j] === tile[i + 2 * j]) {
      if (factions.AIplayer === tile[i]) {
        gameResults.winner = "AIplayer";
      } else if (tile[i] === factions.humanPlayer) {
        gameResults.winner = "humanPlayer";
      }
      return true;
    }
  }

  var check = emptyCells(board); //check if the game ended with a draw
  if (check.length === 0) {
    gameResults.winner = "draw";
    return true;
  } else {
    return false; //if no condition is matched the game has not concluded
  }
};

var getBestMove = function(board, player) {

  // return an AiMove object initialized to 10 if the AI player wins, -10 if the human player wins and 0 if the game is a draw
  if (isGameOver(board)) {
    if (gameResults.winner === "AIplayer") {
      return new AiMove(10);
    } else if (gameResults.winner === "humanPlayer") {
      return new AiMove(-10);
    } else if (gameResults.winner === "draw") {
      return new AiMove(0);
    }
  }

  var moves = []; //array to store all moves
  var currentPlayer = player;
  for (var i = 0, l = board.length; i < l; i++) { //iterate over the board
    if (board[i] == "E") { //if the tile is empty
      var move = new AiMove; //create new AiMove object and assign a coordinate
      move.coordinates = i;
      board[i] = currentPlayer; //update board
      //call getBestMove recursively with the next player
      if (currentPlayer === factions.AIplayer) {
        move.score = getBestMove(board, factions.humanPlayer).score;
      } else if (currentPlayer === factions.humanPlayer) {
        move.score = getBestMove(board, factions.AIplayer).score;
      }
      moves.push(move);

      board[i] = "E"; //clear tile after move is pushed in to the moves array
    }
  }

  //if it's the AI player's turn select biggest value from the moves array, if it's the human player's turn select the smallest value
  if (currentPlayer === factions.AIplayer) {
    var bestMove = 0;
    var bestScore = -10000;
    for (var i = 0; i < moves.length; i++) {
      if (moves[i].score > bestScore) {
        bestScore = moves[i].score;
        bestMove = i;
      }
    }
  } else if (currentPlayer === factions.humanPlayer) {
    var bestMove = 0;
    var bestScore = 10000;
    for (var i = 0; i < moves.length; i++) {
      if (moves[i].score < bestScore) {
        bestMove = i;
        bestScore = moves[i].score;
      }
    }
  }
  return moves[bestMove]; //return best move
};

var board = [
              "E", "E", "X",
              "E", "E", "X",
              "E", "O", "O"
              ];

function AiMove(score) {
  this.coordinates,
    this.score = score;
}

console.log(getBestMove(board, factions.AIplayer))

EDIT: Could it be that, since the board set up is unwinnable, and the AI is fatalistic, it "gives-up"? Would implementing the concept of "depth" solve this?

Answer 1

The idea of introducing depth in the equation is indeed the right one.

Before doing moves.push(move) add the following line:

  move.score = Math.sign(move.score) * (Math.abs(move.score) - 1);

This will make the score 1 point less grave (-10 becomes -9, 10 becomes 9, ...etc). It expresses the idea that the further away a loss is, the less grave it is, and the closer a win is, the better it is.

In the sample board set up you provided, this will return 6 as the best move, which circumvents the immediate win of the human player. Of course, the AI will still lose against best play, as the game will continue like this:

. . X     . . X     . . X     X . X     X O X
. . X  →  . . X  →  . O X  →  . O X  →  . O X
. O O     X O O     X O O     X O O     X O O

For better debugging possibilities, I would write a function that prints the board to the console. For instance:

function printBoard(board) {
    console.log(board.slice(0, 3).join (' ').replace(/E/g, '.'));
    console.log(board.slice(3, 6).join (' ').replace(/E/g, '.'));
    console.log(board.slice(6, 9).join (' ').replace(/E/g, '.'));
    console.log('');
}

You could also look into making the code more object oriented, writing methods on a Game object, ...etc.