Minimax algorithm for connect 4 producing a losing move

Question

The algorithm appears to produce the correct moves when the depth is set to 4 but when I increase it to 5 it gets unexpectedly worse. In this particular case it's recommending that column 0 is the next best move when I believe the 3rd one is. I may very well not fully understand the minimax algorithm so I'm asking for your help to solve this as I've been trying for days with no success. Also any suggestions to improve the readability of the code will be appreciated.

Here is a link to the game: http://connect4.getforge.io/ - forgive the poor UI (wip). It's default to 4 levels deep, please observe the difference in play when you increase the AI_DEPTH.

Here is the grid and it's the AI's turn to play as G (the maximizing player).

 ''  '' ''   ''  ''  '' ''
 ''  '' ''   ''  ''  '' ''
 ''  '' ''   ''  ''  '' ''
 ''  '' 'G'  'R' 'G' '' 'G'
 'G' '' 'R'  'R' 'R' '' 'R'
 'G' '' 'R'  'R' 'G' '' 'G'

This is the code, as extracted from my project:

const GRID_ROW_COUNT = 6;
const GRID_COL_COUNT = 7;
const GRID_ROW_MID = 3;
const GRID_COL_MID = 3;

const WIN_SCORE = 1000;

const rotateGrid = grid => grid.reduce((newGrid, gridRow) => {
  return newGrid.map((column, i) => column.concat(gridRow[i]));
}, [...Array(grid[0].length)].map(_ => []));

function* getValidMoves(grid, player) {
  for(let col = 0; col < grid[0].length; col++){
    for(let row = grid.length; row > 0; row--){
      if(!grid[row - 1][col]){
        const tempGrid = JSON.parse(JSON.stringify(grid));
        tempGrid[row - 1][col] = player;
        yield [tempGrid, col];
        break;
      }
    }
  }
}

const isDrawn = function(grid){
  for(let row = GRID_ROW_COUNT; row > 0; row--){
    if(grid[row - 1].filter(Boolean).length < GRID_COL_COUNT){
      return false;
    }
  }
  return true;
}

const countInRow = (target, row, index, count) => {
  if(count == 0 || !row[index] || row[index] != target){
    return index;
  }
  return countInRow(target, row, index - 1, count - 1);
}

const countInDiagonal = (target, grid, row, col, count) => {
  const colModulus = Math.abs(col);
  if(count == 0 || row < 0 || !grid[row][colModulus] || grid[row][colModulus] != target){
    return row;
  }
  return countInDiagonal( target, grid, row - 1, col - 1, count - 1 );
};

const countInCounterDiagonal = (target, grid, row, col, count) => countInDiagonal(target, grid, row, -col, count); 

function scoreGridPosition(grid, player, count = 4){
  let score = 0; 
  
  function checkWinOnHorizontals(grid, count){
    const GRID_ROW_COUNT = grid.length;
    const GRID_COL_COUNT = grid[0].length;    
    const GRID_COL_MID = player ? 0 : Math.floor(GRID_COL_COUNT/2);

    for(let row = GRID_ROW_COUNT - 1; row >= 0; row--){
      for(let col = GRID_COL_COUNT - 1; col >= GRID_COL_MID; col--){
        const cell = grid[row][col];
        if(!cell){ continue; }

        const colIndex = countInRow(cell, grid[row], col - 1, count - 1);
        
        if(col - colIndex == count){ return WIN_SCORE; }

        if(player){
          const weight = col - 1 - colIndex;
          if(cell == player){
            score += weight;
          } else {
            score -= weight * 2;         
          }
        } 

        col = colIndex + 1;
      }
    }
    return 0;
  }

  const checkWinOnVerticals = (grid, count) => checkWinOnHorizontals(rotateGrid(grid), count);

  function checkWinOnDiagonals(grid, count){
    const _GRID_ROW_MID = player ? 0 : GRID_ROW_MID;

    for(let row = GRID_ROW_COUNT - 1; row >= _GRID_ROW_MID; row--){
      for(let col = GRID_COL_COUNT - 1; col >= 0; col--){
        const cell = grid[row][col];
        if(!cell){ continue; }
        
        let rowIndexL = row, rowIndexR = row;
        
        if(col >= GRID_COL_MID){
          rowIndexL = countInDiagonal(cell, grid, row - 1, col - 1, count - 1);
        }
        if(col <= GRID_COL_MID){
          rowIndexR = countInCounterDiagonal(cell, grid, row - 1, col + 1, count - 1);
        }
        
        if(row - rowIndexL == count || row - rowIndexR == count){ return WIN_SCORE; }

        if(player){
          const weight = (row - rowIndexL) + (row - rowIndexR);
          if(cell == player){
            score += weight
          } else {
            score -= weight;
          }
        }
      }
    }
    return 0;
  }
    
  return [
    checkWinOnHorizontals(grid, count) ||
    checkWinOnVerticals(grid, count) ||
    checkWinOnDiagonals(grid, count),
    score
  ];
}

const alphaBetaAI = (grid, depth = 5, alpha = -Infinity, beta = Infinity, isMaxPlayer = true) => {
  let value = isMaxPlayer ? -Infinity : Infinity;
  let move = null;

  if(isDrawn(grid)){ return [0, move]; }

  const player = isMaxPlayer ? 'G' : 'R';
  const [terminalScore, score] = scoreGridPosition(grid, player);
  
  if(terminalScore){
                       // -1000            1000  
    return [isMaxPlayer ? -terminalScore : terminalScore, move]
  }
  if(depth == 0){ return [score, move]; }

  if(isMaxPlayer){
    for(let [newGrid, column] of getValidMoves(grid, player)){
      let [tempVal] = alphaBetaAI(newGrid, depth - 1, alpha, beta, !isMaxPlayer);
      if(tempVal > value){
        value = tempVal;
        move = column;
      }
      alpha = Math.max(value, alpha);
      if(beta <= alpha){ break; }
    }
  } else {
    for(let [newGrid, column] of getValidMoves(grid, player)){
      let [tempVal] = alphaBetaAI(newGrid, depth - 1, alpha, beta, !isMaxPlayer);
      if(tempVal < value){
        value = tempVal;
        move = column;
      }
      beta = Math.min(value, beta);
      if(beta <= alpha){ break; }
    }
  }
  return [value, move];
}

// here is the grid
let g = [
  ['', '', '', '', '', '', ''],
  ['', '', '', '', '', '', ''],
  ['', '', '', '', '', '', ''],
  ['', '', 'G', 'R', 'G', '', 'G'],
  ['G', '', 'R', 'R', 'R', '', 'R'],
  ['G', '', 'R', 'R', 'G', '', 'G']
];

console.log('Move: ', alphaBetaAI(g)[1]); // 0 - I was expecting 3

Answer 1

As Ouroborus pointed out, at depth 5 it sees that it loses no matter what move it plays. So now it choses the first move in your list of possible moves since all results return -1000.

If you want it to always find the longest route to lose then you need to return -1000 + depth if you lose, and 1000 - depth if you win. Then your AI will always chose the longest route to losing (and the quickest to winning if there are more than 1 way to win).