Minimax Algorithm Scoring Mechanism

Question

I'm basically trying to understand the chronology/sequence of the algorithm and where should I call the scoring mechanism function that calculates the score of each move and returns an int. For example, this code is an implementation of the Minimax algorithm in the Tic-Tac-Toe game:

function bestMove() {
// AI to make its turn
let bestScore = -Infinity;
let move;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
  // Is the spot available?
  if (board[i][j] == '') {
    board[i][j] = ai;
    let score = minimax(board, 0, false);
    board[i][j] = '';
    if (score > bestScore) {
      bestScore = score;
      move = { i, j };
    }
  }
}
}
board[move.i][move.j] = ai;
currentPlayer = human;
}

let scores = {
X: 10,
O: -10,
tie: 0
};

  function minimax(board, depth, isMaximizing) {
  let result = checkWinner();
  if (result !== null) {
  return scores[result];
  }

  if (isMaximizing) {
  let bestScore = -Infinity;
  for (let i = 0; i < 3; i++) {
  for (let j = 0; j < 3; j++) {
    // Is the spot available?
    if (board[i][j] == '') {
      board[i][j] = ai;
      let score = minimax(board, depth + 1, false);
      board[i][j] = '';
      bestScore = max(score, bestScore);
    }
  }
}
return bestScore;
} else {
let bestScore = Infinity;
for (let i = 0; i < 3; i++) {
  for (let j = 0; j < 3; j++) {
    // Is the spot available?
    if (board[i][j] == '') {
      board[i][j] = human;
      let score = minimax(board, depth + 1, true);
      board[i][j] = '';
      bestScore = min(score, bestScore);
    }
  }
}
return bestScore;
}
}

The only implementation of the scoring mechanism is when the board identifies a win situation for one of the players. In complex games there are too many combinations so the depth will be restricted to let's say 3. the scoring mechanism needs to be called for each "move" that is being examined, otherwise we will get back 0 for each move, and the algorithm will just go for the next open spot, since the depth doesn't reach a possible wining series of moves.

If I planned a scoring mechanism function that compensate and "punishes" each move (for every i,j) minimax goes through and returns an int (the score), how should I fit it correctly in the algorithm?

It sounds simple but honestly nothing makes sense to me at this point...

P.S My game is pretty complex to explain and would take a long time, therefore, I'm looking for the more logic answer so I can implement it myself.

Thanks in advance, Omer

Answer 1

You invoke your scoring method anytime you are not recursing further into the game tree.

That could be when you've reached an end state, like in the Tic-Tac-Toe case, in which case you can score the move with total certainty about who benefits most from this outcome.

It can also be when you've hit your recursion limit:

In complex games there are too many combinations so the depth will be restricted to let's say 3

So you will recurse three times. Then when you arrive at a new unevaluated game state at a depth of 3 and can't recurse any further to evaluate it based on future moves, you fall back on a scoring heuristic.

Here you score the game state using some estimation of who has an advantage in this state — like which player has more powerful pieces on the board, or the most health, or the most victory points or resources, etc.

This estimation is crude, but it's just one data point in your search — it benefits from aggregation with all the other recursive branches you tried. So the deeper you can recurse before falling back on the scoring heuristic, the better the judgments you'll tend to reach by this method.