0
\$\begingroup\$

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

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you so much! So, I am starting to connect the dots.. When I'm reaching my maximum depth and I'm not recursing further in, I am basically looping to go through all spots (to evaluate the board) and, if I understand how this algorithm works, the minimizing player will end up taking the lowest score possible from this evaluation, and the maximizing player will end up taking the highest score possible? Should I add an if statement saying if maximizing / if minimizing and consistently check for the lowest/highest score like in the minimax itself, where we have the isMaximizing == true/false? \$\endgroup\$ Oct 3, 2020 at 13:12
  • 1
    \$\begingroup\$ Your score function evaluation becomes the single number you report as the score for this leaf of the search tree. Once you've scored all the children of a particular parent node (by hitting an end state, using your heuristic, or recursing), then the parent node's score becomes either the min or the max of all its children's scores (depending on whether that parent node represents the minimizing or maximizing player's turn). Now this parent node has a score, that can bubble up to its parent node to choose the max or min of its children, etc. \$\endgroup\$
    – DMGregory
    Oct 3, 2020 at 13:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .