Gomoku (Connect Five) Minimax algorithm not finding obvious win

Question

I'm developing a very simple connect five (gomoku) AI for fun in Javascript using minimax and alpha beta pruning. I've just been following some tutorials online, but for some reason I can't quite get it to work. I think I have a logical bug somewhere, because in the following code, there is a fork if the AI places a piece in the second row and third column, but it's not being found as the bestMove.

Weirdly enough, if I set a breakpoint, that position (row: 1, col: 2) is often found as the winningMove, but for whatever reason, the minimax function never calculates bestMove to be that move, even though I believe it clearly should be. That is, if the AI places a piece there, it's basically an immediate win next turn, because it causes a win in multiple directions.

That is, if the AI places a move at the white 2, then there can either be a vertical win, or a horizontal win, in the next AI move, because the human could only block one of them:

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

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

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;
}

let bestMove = Number.MIN_SAFE_INTEGER;

function minimax(board, depth, alpha, beta, player, latestRow, latestCol) {
  if (depth === 0) {
    return evaluatePlayerBoard(board, player, player === COMP ? HUMAN : COMP, latestRow, latestCol);
  }

  if (isWinningMove(board, player, latestRow, latestCol)) {
    return 1000000;
  }

  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);
        board[idx] = tileValue;

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

        alpha = Math.max(alpha, evaluation);

        if (beta <= alpha) {
          return maxEval;
        }
      }
    }

    return maxEval;
  } 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);
        board[idx] = tileValue;

        if (evaluation < minEval) {
          minEval = evaluation;
        }

        beta = Math.min(beta, evaluation);

        if (beta <= alpha) {
          return minEval;
        }
      }
    }

    return minEval;
  }
}

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

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

  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, you, opponent, latestRow, latestCol) {
  return evaluatePlayerBoard(grid, you, latestRow, latestCol) - evaluatePlayerBoard(grid, opponent, latestRow, latestCol);
}

const exampleBoard = [
  0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 2, 0, 2, 2, 1, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 2, 0, 0, 0, 0, 0, 0,
  0, 0, 2, 0, 0, 0, 0, 0, 0,
  0, 0, 2, 0, 0, 0, 0, 0, 0,
  0, 0, 1, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0,
];

minimax(exampleBoard, 2, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, COMP, -1, -1);

console.log(bestMove);

You can run the snippet above and see that 20 is logged instead of 11, even though 11 is clearly the better move as it causes an immediate win.

Answer 1

There are several issues:

• With const val = evaluatePlayerBoard(board, player, player === COMP ? HUMAN : COMP, latestRow, latestCol); you pass 2 player arguments, while the function only expects one player argument. So the arguments are misinterpreted by the function and the result is useless.

• Probably related to the above: you have a function evaluateBoard which is never called, but which does expect two player arguments. I guess you intended to call that function from minimax.

• Still evaluateBoard returns a score that is relative to the first player argument (positive is better), but since you have a maximizing player and minimizing player, the sign of the score should not be dynamically determined by the arguments to this function, but "hard-coded" in such a way that COMP always gets the positive score, and HUMAN the negative. So evaluateBoard should actually get no player argument at all, and just make the first call to evaluatePlayerBoard with COMP as argument, and the second one with HUMAN as argument.

• minimax calls isWinningMove with the wrong player argument. It should be the opponent that played the last move, since that is the move that is passed as argument.

• With depth starting at 2, you only allow for a move of COMP and a return move of HUMAN. Then you evaluate the position. At that time there is no win yet. You should start with a depth of at least 3

• As bestMove is a global variable, you'll sometimes get the best move of the deeper move of COMP, since no matter what the depth is, you will overwrite it. But this deeper move is not the move you want to identify. Best practice is to not use a global variable for this. Instead, make minimax return both the found value as the corresponding move. You can combine both in an array (or plain object), like this: return [maxEval, bestMove]. This means you have to change your code in several places: all return statements in minimax should return an array now, and all calls of minimax should expect an array as return value, and pick the part they are interested in (either the value or the move).

• When minimax sees the depth is zero, and detects a win by calling isWinningMove, it always returns 1000000, but it should return -1000000 if the last move was played by HUMAN. So move this logic inside both if and else blocks.

• Less an issue, but it only requires one more line so that minimax can also return the best move for when HUMAN would be the initial caller. I would just add it.

Here is a corrected version of your code:

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

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

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;
}

// Removed global bestMove definition from here

function minimax(board, depth, alpha, beta, player, latestRow, latestCol) {
  if (depth === 0) {
    // Fixed: Call different function and don't pass player arguments:
    const val = evaluateBoard(board, latestRow, latestCol);
    return [val, -1]; // Now returns a pair (value, move)
  }

  const opponent = player === COMP ? HUMAN : COMP; // Moved this expression here
  let bestMove = -1; // Is now a local variable -- not a global.
  if (player === COMP) {
    // Fixed: player argument should be opponent, and return statement should be different per player
    if (isWinningMove(board, opponent, latestRow, latestCol)) {
      // Minimax returns an array now: value, move
      return [1000000, -1]; // Positive for COMP, negative for HUMAN.
    }
    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;
        // As minimax returns an array now, get the first element of it
        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) {
          // Minimax returns an array now: value, move
          return [maxEval, bestMove];
        }
      }
    }
    // Minimax returns an array now: value, move
    return [maxEval, bestMove];
  } else {
    // Fixed: player argument should be opponent, and return statement should be different per player
    if (isWinningMove(board, opponent, latestRow, latestCol)) {
      // Minimax returns an array now: value, move
      return [-1000000, -1]; // Positive for COMP, negative for HUMAN.
    }
    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;
        // As minimax returns an array now, get the first element of it
        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) {
          // Minimax returns an array now: value, move
          return [minEval, bestMove];
        }
      }
    }
    // Minimax returns an array now: value, move
    return [minEval, bestMove];
  }
}

function evaluatePlayerBoard(grid, who, latestRow, latestCol) {
  let idx = 0;
  let score = 0;
  if (isWinningMove(grid, who, latestRow, latestCol)) {
    return 1000000;
  }
  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) { // Removed player paramaters
  // Hardcoded the player arguments, as COMP is maximizing, and HUMAN is minimizing.
  return evaluatePlayerBoard(grid, COMP, latestRow, latestCol) 
       - evaluatePlayerBoard(grid, HUMAN, latestRow, latestCol);
}

const exampleBoard = [
  0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 2, 0, 2, 2, 1, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 2, 0, 0, 0, 0, 0, 0,
  0, 0, 2, 0, 0, 0, 0, 0, 0,
  0, 0, 2, 0, 0, 0, 0, 0, 0,
  0, 0, 1, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0,
];

// The depth should be set at least at 3 to detect the win.
// As minimax returns an array now, get the move part of it (at index 1)
const bestMove = minimax(exampleBoard, 3, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, COMP, -1, -1)[1];    
console.log(bestMove); // 11

Disclaimer: I only verified your code to resolve the question you asked about. There might still be other issues you need to fix.