Gomoku (Connect Five) Minimax algorithm AI doesn't care about losing

Question

This is a continuation from my previous question.

So, I think I've made a lot of progress. The AI now seems to generally make the best move, and go for wins, but one last problem I'm having is that it doesn't seem to care about losing. That is, if it has a fork, or 4 in a row, it will go for the win, but if the HUMAN player has 3 (or 4) in a row, it won't make a move that would stop them from winning.

Even weirder, sometimes if I set the depth to a lower value, it will prevent the loss, but not if I increase the depth. Here's my current code, with an example board where it fails to find the best move (to prevent the loss next turn):

const ROWS = 9;
const COLS = 9;
const LEN = 5;

const EMPTY = 0;
const HUMAN = 1;
const COMP = 2;

const WINNING_MOVE = 100000;

function checkDirection(grid, who, currChain, sRow, sCol, incRow, incCol) {
  let newChain = 0;

  while (currChain + newChain < LEN) {
    const row = sRow + (incRow * (newChain + 1));
    const col = sCol + (incCol * (newChain + 1));

    if (grid[row * COLS + col] !== who) {
      break;
    }
    
    newChain++;
  }

  return newChain;
}

function lineCheck(grid, who, sRow, sCol, mRow, mCol) {
  let chain = 1;

  chain += checkDirection(grid, who, 0, sRow, sCol, mRow, mCol);
  chain += checkDirection(grid, who, chain, sRow, sCol, -mRow, -mCol);

  return chain >= LEN;
}

function isWinningMove(grid, who, row, col) {    
  return lineCheck(grid, who, row, col, 1, 0) || 
         lineCheck(grid, who, row, col, 0, 1) || 
         lineCheck(grid, who, row, col, 1, 1) || 
         lineCheck(grid, who, row, col, -1, 1);
}

function getTile(grid, row, col) {
  if (row < 0 || col < 0 || row >= ROWS || col >= COLS) {
    return -1;
  }

  return grid[row * COLS + col];
}

function hasNeighbor(board, row, col) {
  if (getTile(board, row - 1, col - 1) > 0) { return true; }
  if (getTile(board, row - 1, col + 1) > 0) { return true; }
  if (getTile(board, row + 1, col - 1) > 0) { return true; }
  if (getTile(board, row + 1, col + 1) > 0) { return true; }

  if (getTile(board, row - 1, col) > 0) { return true; }
  if (getTile(board, row + 1, col) > 0) { return true; }

  if (getTile(board, row, col - 1) > 0) { return true; }
  if (getTile(board, row, col + 1) > 0) { return true; }

  return false;
}

function minimax(board, depth, alpha, beta, player, latestRow, latestCol) {
  if (depth === 0) {
    const val = evaluateBoard(board, latestRow, latestCol);

    return [ val, latestRow * COLS + latestCol ]; // returns a pair (value, move)
  }

  const opponent = player === COMP ? HUMAN : COMP;

  // player argument should be opponent, and return statement should be different per player
  if (isWinningMove(board, opponent, latestRow, latestCol)) {
    const multiplier = player === COMP ? 1 : -1;

    return [ WINNING_MOVE * multiplier, latestRow * COLS + latestCol ];
  }

  let bestMove = -1;

  if (player === COMP) {
    let maxEval = Number.MIN_SAFE_INTEGER;

    for (let row = 0; row < ROWS; row++) {
      for (let col = 0; col < COLS; col++) {
        const idx = row * COLS + col;
        const tileValue = board[idx];

        if (tileValue > 0 || !hasNeighbor(board, row, col)) { continue; }

        board[idx] = player;
        const evaluation = minimax(board, depth - 1, alpha, beta, HUMAN, row, col)[0];
        board[idx] = tileValue;

        if (evaluation > maxEval) {
          maxEval = evaluation;
          bestMove = idx;
        }

        alpha = Math.max(alpha, evaluation);

        if (beta <= alpha) {
          return [ maxEval, bestMove ];
        }
      }
    }

    return [ maxEval, bestMove ];
  } else {
    let minEval = Number.MAX_SAFE_INTEGER;

    for (let row = 0; row < ROWS; row++) {
      for (let col = 0; col < COLS; col++) {
        const idx = row * COLS + col;
        const tileValue = board[idx];

        if (tileValue > 0 || !hasNeighbor(board, row, col)) { continue; }

        board[idx] = player;
        const evaluation = minimax(board, depth - 1, alpha, beta, COMP, row, col)[0];
        board[idx] = tileValue;

        if (evaluation < minEval) {
          minEval = evaluation;
          bestMove = idx; // Also track best move for HUMAN.
        }

        beta = Math.min(beta, evaluation);

        if (beta <= alpha) {
          return [ minEval, bestMove ];
        }
      }
    }

    return [ minEval, bestMove ];
  }
}

function evaluatePlayerBoard(grid, who, latestRow, latestCol) {
  let idx = 0;
  let score = 0;

  if (isWinningMove(grid, who, latestRow, latestCol)) {
    return WINNING_MOVE;
  }

  for (let row = 0; row < ROWS; row++) {
    for (let col = 0; col < COLS; col++) {
      if (grid[idx] !== who) { idx++; continue; }

      if (getTile(grid, row - 1, col - 1) === who) { score++; }
      if (getTile(grid, row - 1, col + 1) === who) { score++; }
      if (getTile(grid, row + 1, col - 1) === who) { score++; }
      if (getTile(grid, row + 1, col + 1) === who) { score++; }

      if (getTile(grid, row - 1, col) === who) { score++; }
      if (getTile(grid, row + 1, col) === who) { score++; }

      if (getTile(grid, row, col - 1) === who) { score++; }
      if (getTile(grid, row, col + 1) === who) { score++; }
      
      // if (getTile(grid, row, col) === who) { score++; }

      idx++;
    } 
  }

  return score;
}

function evaluateBoard(grid, latestRow, latestCol) {
  return evaluatePlayerBoard(grid, COMP, latestRow, latestCol) // COMP is maximizing
       - evaluatePlayerBoard(grid, HUMAN, latestRow, latestCol); // HUMAN is minimizing
}

function getBestMove(board, maxDepth) {
  for (let depth = 1; depth <= maxDepth; depth++) {
    const [ evaluation, move ] = minimax(board, depth, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, COMP, -1, -1);

    // if we found a winning move already, return early
    // otherwise, keep iterating until we reach max depth
    if (evaluation > 10000 || depth === maxDepth) {
      return move;
    }
  }

  return 0; // should never run
}

const exampleBoard = [
  0, 0, 0, 0, 0, 0, 0, 0, 0, // 0-8
  0, 0, 0, 0, 0, 0, 0, 0, 0, // 9-17
  0, 0, 0, 0, 0, 0, 2, 0, 0, // 18-26
  0, 0, 2, 2, 0, 1, 0, 0, 0, // 27-35
  0, 0, 0, 2, 1, 0, 0, 0, 0, // 36-44
  0, 0, 0, 1, 0, 0, 0, 0, 0, // 45-53
  0, 0, 1, 0, 0, 0, 0, 0, 0, // 54-62
  0, 0, 0, 0, 0, 0, 0, 0, 0, // 63-71
  0, 0, 0, 0, 0, 0, 0, 0, 0, // 72-80
];

console.log(getBestMove(exampleBoard, 3));

I believe it should be logging 64 (to prevent the loss next turn), but it is instead logging 20

score 1 · Accepted Answer · answered Jul 20 '23 at 13:57

1

You have a logical error in this part of the code:

  // player argument should be opponent, and return statement should be different per player
  if (isWinningMove(board, opponent, latestRow, latestCol)) {
    const multiplier = player === COMP ? 1 : -1;

    return [ WINNING_MOVE * multiplier, latestRow * COLS + latestCol ];
  }

When this block is entered, we know that it was the opponent that won, not player, and so the multiplier should be based on opponent. If the opponent is the maximizing player, we should multiply with 1, otherwise with -1.

Not an issue, but it makes no sense to return latestRow * COLS + latestCol as the best move, because the current player has no best move (they lost the game), and latestRow * COLS + latestCol is certainly not their move, so it is irrelevant. (The same remark can be made for the depth == 0 block)

Fix:

  // player argument should be opponent, and return statement should be different per player
  if (isWinningMove(board, opponent, latestRow, latestCol)) {
    const multiplier = opponent === COMP ? 1 : -1;

    return [ WINNING_MOVE * multiplier, -1 ];
  }

answered Jul 20 '23 at 13:57

trincot

317,000
35
244
286

1

Ahhh what a silly mistake!! Thank you so much for catching that! It seems to work great now! Hooray! Thanks so much! – John Smith Jul 20 '23 at 14:08
Bleh, this did help a lot, but for some reason the AI now only works when depth is at least 4. Any idea why that might be? When the depth is 1 through 3, you can just immediately win right at the start by making a single line of 5, and the computer doesn't even try to stop you. On the plus side, the AI when the depth is 4 or 5 is actually pretty good! I tried a bunch of different ways to win and they all failed – John Smith Jul 20 '23 at 14:26
I understand you want it to work perfectly, but Stack Overflow is not the right place to present a piece of code and expect that all bugs be identified in an answer. Just keep at it, using a good debugger, and unit tests. If you cannot make it work, and want to rely on this community, then I can just say: ask a new question about a specific problem you encounter. – trincot Jul 20 '23 at 14:31
Okie dokie. Thanks for all the help! – John Smith Jul 20 '23 at 14:34

Gomoku (Connect Five) Minimax algorithm AI doesn't care about losing

1 Answers1