javascriptartificial-intelligenceminimaxgomoku

Gomoku (Connect Five) Minimax algorithm not finding obvious win


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:

enter image description here

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.


Solution

  • There are several issues:

    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.