Using Game Theory and Minimax

function nimGame(stones, playerTurn) {
  if (stones === 0) return playerTurn === 'computer' ? 'player wins' : 'computer wins';

  const moves = [1, 2, 3].filter(move => move <= stones);
  const bestMove = moves.reduce((best, move) => {
    const newState = { stones: stones - move, currentPlayer: playerTurn === 'player' ? 'computer' : 'player' };
    return minimax(newState, false) > minimax(best, true) ? move : best;
  }, moves[0]);

  return `Player takes ${bestMove} stones`;
}

function mex(s) {
    let i = 0;
    while (s.has(i)) i++;
    return i;
}

function calculateGrundy(state) {
    if (state.isTerminal()) return 0;

    let reachable = state.getMoves();
    let grundyNumbers = new Set();

    for (let move of reachable) {
        let next = state.applyMove(move);
        grundyNumbers.add(calculateGrundy(next));
    }

    return mex(grundyNumbers);
}

// Example: Nim game state with 3 piles [1, 2, 3]
let nimState = new NimState([1, 2, 3]);
let grundy = calculateGrundy(nimState);
console.log(grundy); // Output: 0 (losing position)

function mex(set) {
  let mex = 0;
  while (set.has(mex)) mex++;
  return mex;
}

function grundy(state, memo = new Map()) {
  if (memo.has(state)) return memo.get(state);
  
  const reachable = getReachableStates(state);
  const mexSet = new Set();
  
  for (const nextState of reachable) {
    mexSet.add(grundy(nextState, memo));
  }
  
  const result = mex(mexSet);
  memo.set(state, result);
  return result;
}

// Example: Nim game with heaps [1, 2, 3]
const nimState = [1, 2, 3];
const grundyValue = grundy(nimState);
console.log(grundyValue); // Output: 0 (losing position for current player)

function isWinningPosition(state) {
  const grundyValue = grundy(state);
  return grundyValue !== 0;
}

function optimalMove(state) {
  const reachable = getReachableStates(state);
  const grundyValue = grundy(state);
  
  for (const nextState of reachable) {
    const nextGrundy = grundy(nextState);
    if ((grundyValue ^ nextGrundy) === 0) {
      return nextState;
    }
  }
  
  // If no winning move found, make any valid move
  return reachable[0];
}

// Example usage:
const game = [2, 3, 4];
if (isWinningPosition(game)) {
  console.log("Current player can force a win");
  const move = optimalMove(game);
  console.log("Optimal move:", move);
} else {
  console.log("Current player is in a losing position");
}

function stoneGameIII(stoneValue) {
    const n = stoneValue.length;
    const dp = new Array(n + 1).fill(0);
    
    for (let i = n - 1; i >= 0; i--) {
        dp[i] = stoneValue[i] + dp[i + 1];
        if (i + 1 < n) {
            dp[i] = Math.max(dp[i], stoneValue[i] + stoneValue[i + 1] + dp[i + 2]);
        }
        if (i + 2 < n) {
            dp[i] = Math.max(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] + dp[i + 3]);
        }
    }

    return dp[0];
}

const board = [
  ["", "", ""],
  ["", "", ""],
  ["", "", ""]
];

// AI plays as "O"
const bestMove = findBestMove(board);
console.log(bestMove); // {row: 1, col: 1}

const gameTree = {
  value: null,
  children: [
    { value: 3, children: [] },
    { value: 5, children: [] },
    { value: 2, children: [
      { value: 1, children: [] },
      { value: 4, children: [] }
    ]},
    { value: 8, children: [] }
  ]
};

// Evaluate with depth = 2, alpha = -Infinity, beta = Infinity
const result = alphabeta(gameTree, 2, -Infinity, Infinity, true);
console.log(result); // Output: 5

function canWinBashGame(n, m) {
    // If n is divisible by (m + 1), the current player is in a losing position
    return n % (m + 1) !== 0;
}

// Example usage:
console.log(canWinBashGame(5, 2)); // true - First player can win
console.log(canWinBashGame(4, 2)); // false - First player is in a losing position

function minimaxWithAlphaBeta(board, depth, alpha, beta, isMaximizing) {
  const score = evaluateBoard(board);
  
  if (depth === 0 || isGameOver(board)) {
    return score;
  }

  if (isMaximizing) {
    let maxEval = -Infinity;
    for (let move of getValidMoves(board)) {
      board[move] = 'X';
      const eval = minimaxWithAlphaBeta(board, depth - 1, alpha, beta, false);
      board[move] = ' ';
      maxEval = Math.max(maxEval, eval);
      alpha = Math.max(alpha, eval);
      if (beta <= alpha) break;
    }
    return maxEval;
  } else {
    let minEval = Infinity;
    for (let move of getValidMoves(board)) {
      board[move] = 'O';
      const eval = minimaxWithAlphaBeta(board, depth - 1, alpha, beta, true);
      board[move] = ' ';
      minEval = Math.min(minEval, eval);
      beta = Math.min(beta, eval);
      if (beta <= alpha) break;
    }
    return minEval;
  }
}

function evaluateBoard(board) {
  const wins = [
    [0,1,2], [3,4,5], [6,7,8],
    [0,3,6], [1,4,7], [2,5,8],
    [0,4,8], [2,4,6]
  ];
  
  for (let win of wins) {
    const [a, b, c] = win;
    if (board[a] === board[b] && board[b] === board[c]) {
      if (board[a] === 'X') return 10;
      if (board[a] === 'O') return -10;
    }
  }
  return 0;
}

function isGameOver(board) {
  return evaluateBoard(board) !== 0 || !board.includes(' ');
}

function expectiminimax(node, depth) {
  if (depth === 0 || node.isTerminal()) {
    return node.evaluate();
  }

  if (node.type === 'MAX') {
    let maxEval = -Infinity;
    for (const child of node.getChildren()) {
      const eval = expectiminimax(child, depth - 1);
      maxEval = Math.max(maxEval, eval);
    }
    return maxEval;
  } else if (node.type === 'MIN') {
    let minEval = Infinity;
    for (const child of node.getChildren()) {
      const eval = expectiminimax(child, depth - 1);
      minEval = Math.min(minEval, eval);
    }
    return minEval;
  } else if (node.type === 'CHANCE') {
    let expectedValue = 0;
    const children = node.getChildren();
    for (const child of children) {
      const probability = child.getProbability();
      const eval = expectiminimax(child, depth);
      expectedValue += probability * eval;
    }
    return expectedValue;
  }
}

const gameState = [1, 2, 3, 4, 5];
const currentPlayer = 0;
const scores = [0, 0];

function minimax(state, depth, isMaximizing) {
  if (depth === 0 || state.length === 0) {
    return evaluate(state);
  }

  if (isMaximizing) {
    let maxEval = -Infinity;
    for (let i = 0; i < state.length; i++) {
      const newState = state.slice(0, i).concat(state.slice(i + 1));
      const eval = minimax(newState, depth - 1, false);
      maxEval = Math.max(maxEval, eval);
    }
    return maxEval;
  } else {
    let minEval = Infinity;
    for (let i = 0; i < state.length; i++) {
      const newState = state.slice(0, i).concat(state.slice(i + 1));
      const eval = minimax(newState, depth - 1, true);
      minEval = Math.min(minEval, eval);
    }
    return minEval;
  }
}

function nimMove(heaps) {
  const xor = heaps.reduce((a, b) => a ^ b, 0);
  if (xor === 0) return null; // Losing position
  for (let i = 0; i < heaps.length; i++) {
    const target = heaps[i] ^ xor;
    if (target < heaps[i]) {
      return { heap: i, amount: heaps[i] - target };
    }
  }
  return null;
}