Upgrading Filler AI with Minimax and Alpha-Beta Pruning

Certainly! Implementing Minimax with Alpha-Beta pruning is a great way to improve the AI's performance without making it overly complex. Let's outline the changes we'll make to the existing code:

1. Minimax with Alpha-Beta Pruning

We'll replace the current findBestMove function with a minimax implementation. Here's how we can do it:

function findBestMove(depth = 3) {
  let bestScore = -Infinity;
  let bestMove = null;

  for (let color = 0; color < COLORS.length; color++) {
    if (color === aiColor || color === humanColor) continue;
    
    let newBoard = JSON.parse(JSON.stringify(board));
    floodFillSimulation(BOARD_SIZE-1, BOARD_SIZE-1, aiColor, color, newBoard);
    
    let score = minimax(newBoard, depth - 1, false, -Infinity, Infinity, color, humanColor);
    
    if (score > bestScore) {
      bestScore = score;
      bestMove = color;
    }
  }

  return bestMove;
}

function minimax(simBoard, depth, isMaximizing, alpha, beta, aiColor, humanColor) {
  if (depth === 0 || isGameOver(simBoard)) {
    return evaluateBoard(simBoard, aiColor, humanColor);
  }

  if (isMaximizing) {
    let maxEval = -Infinity;
    for (let color = 0; color < COLORS.length; color++) {
      if (color === aiColor || color === humanColor) continue;
      let newBoard = JSON.parse(JSON.stringify(simBoard));
      floodFillSimulation(BOARD_SIZE-1, BOARD_SIZE-1, aiColor, color, newBoard);
      let eval = minimax(newBoard, depth - 1, false, alpha, beta, color, humanColor);
      maxEval = Math.max(maxEval, eval);
      alpha = Math.max(alpha, eval);
      if (beta <= alpha) break;
    }
    return maxEval;
  } else {
    let minEval = Infinity;
    for (let color = 0; color < COLORS.length; color++) {
      if (color === aiColor || color === humanColor) continue;
      let newBoard = JSON.parse(JSON.stringify(simBoard));
      floodFillSimulation(0, 0, humanColor, color, newBoard);
      let eval = minimax(newBoard, depth - 1, true, alpha, beta, aiColor, color);
      minEval = Math.min(minEval, eval);
      beta = Math.min(beta, eval);
      if (beta <= alpha) break;
    }
    return minEval;
  }
}

function isGameOver(simBoard) {
  let aiScore = countConnectedCells(BOARD_SIZE-1, BOARD_SIZE-1, aiColor, simBoard);
  let humanScore = countConnectedCells(0, 0, humanColor, simBoard);
  return aiScore + humanScore === BOARD_SIZE * BOARD_SIZE;
}

2. Improved Evaluation Function

Let's enhance the evaluation function to consider more factors:

function evaluateBoard(simBoard, aiColor, humanColor) {
  let aiScore = countConnectedCells(BOARD_SIZE-1, BOARD_SIZE-1, aiColor, simBoard);
  let humanScore = countConnectedCells(0, 0, humanColor, simBoard);
  
  // Consider control of corners
  let cornerControl = 0;
  cornerControl += (simBoard[0][BOARD_SIZE-1] === aiColor) ? 1 : (simBoard[0][BOARD_SIZE-1] === humanColor) ? -1 : 0;
  cornerControl += (simBoard[BOARD_SIZE-1][0] === aiColor) ? 1 : (simBoard[BOARD_SIZE-1][0] === humanColor) ? -1 : 0;
  
  // Consider potential for expansion
  let aiPotential = countAdjacentCells(simBoard, aiColor);
  let humanPotential = countAdjacentCells(simBoard, humanColor);
  
  return (aiScore - humanScore) * 2 + cornerControl * 5 + (aiPotential - humanPotential);
}

function countAdjacentCells(simBoard, color) {
  let count = 0;
  for (let i = 0; i < BOARD_SIZE; i++) {
    for (let j = 0; j < BOARD_SIZE; j++) {
      if (simBoard[i][j] === color) {
        count += countEmptyNeighbors(simBoard, i, j);
      }
    }
  }
  return count;
}

function countEmptyNeighbors(simBoard, x, y) {
  let count = 0;
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  for (let [dx, dy] of directions) {
    let nx = x + dx, ny = y + dy;
    if (nx >= 0 && nx < BOARD_SIZE && ny >= 0 && ny < BOARD_SIZE && 
        simBoard[nx][ny] !== aiColor && simBoard[nx][ny] !== humanColor) {
      count++;
    }
  }
  return count;
}

Implementation Notes

• The minimax function now looks ahead by a depth of 3 moves (adjustable via the depth parameter in findBestMove).
• Alpha-beta pruning is implemented to improve efficiency by cutting off branches that don't need to be explored.
• The evaluation function now considers:
  • The difference in controlled cells
  • Control of important corners
  • Potential for future expansion
• You may need to adjust the weights in the evaluation function to fine-tune the AI's behavior.

To implement these changes, replace the existing findBestMove and evaluateBoard functions with the new versions provided above, and add the new helper functions (isGameOver, countAdjacentCells, countEmptyNeighbors).

This implementation should significantly improve the AI's performance while keeping the computation time reasonable for a web-based game. You can adjust the depth parameter in findBestMove to balance between AI strength and response time.