Javascript Соединение 4 минимакс и альфа-бета-обрезка не работает

Question

Я пытаюсь запрограммировать Connect 4, используя минимаксный алгоритм AI и отсечение альфа-бета. Это весь код, но три функции, в которых, как мне кажется, проблема может заключаться в ie, это bestMove(), minimax() и useHeuristic(). Я заранее прошу прощения, если его нелегко прочитать.

let board = [
  ['empty', 'empty', 'empty', 'empty', 'empty', 'empty'],
  ['empty', 'empty', 'empty', 'empty', 'empty', 'empty'],
  ['empty', 'empty', 'empty', 'empty', 'empty', 'empty'],
  ['empty', 'empty', 'empty', 'empty', 'empty', 'empty'],
  ['empty', 'empty', 'empty', 'empty', 'empty', 'empty'],
  ['empty', 'empty', 'empty', 'empty', 'empty', 'empty'],
  ['empty', 'empty', 'empty', 'empty', 'empty', 'empty']
];

// Initializing drawing variables

let holeDiameter = 60;
let holeRadius = holeDiameter / 2;
let xBorder = 15;
let yBorder = 10;

let isMouseMoved = false;

// Available spots

let available = [];


// Initializing the players

let ai = 'red';
let human = 'yellow';
let currentPlayer = human;

function setup() {
  createCanvas(540, 430);
  for (let i = 0; i < 7; i++) {
    for (let j = 0; j < 6; j++) {
      available.push(board[i][j]);
    }
  }
}

function equals4(a, b, c, d) {
  return (a == b && b == c && c == d && (a != 'empty'));
}

function equals3(a, b, c) {
  return (a == b && b == c && (a != 'empty'));
}

function equals2(a, b) {
  return (a == b && (a != 'empty'));
}

function checkWinner() {

  let aiFours = checkFours(ai);
  let humanFours = checkFours(human);

  // tracks available spots

  let openSpots = 0;
  for (let i = 0; i < 7; i++) {
    for (let j = 0; j < 6; j++) {
      if (board[i][j] == 'empty') {
        openSpots++;
      }
    }
  }

  if (aiFours > 0) {
    return ai;
  } else if (humanFours > 0) {
    return human;
  } else if (openSpots == 0) {
    return 'tie';
  }

}

function checkFours(player) {

  let numOfFours = 0;

  for (let i = 0; i < 7; i++) {
    for (let j = 0; j < 6; j++) {

      if ((i < 4) && equals4(board[i][j], board[i + 1][j], board[i + 2][j], board[i + 3][j]) && board[i][j] == player) {

        numOfFours++;

        // vertical checking

      } else if ((j < 3) && equals4(board[i][j], board[i][j + 1], board[i][j + 2], board[i][j + 3]) && board[i][j] == player) {

        numOfFours++

        // diagonal 1 checking

      } else if ((i < 4) && (j < 3) && equals4(board[i][j], board[i + 1][j + 1], board[i + 2][j + 2], board[i + 3][j + 3]) && board[i][j] == player) {

        numOfFours++;

        // diagonal 2 checking

      } else if ((i > 2) && (j < 3) && equals4(board[i][j], board[i - 1][j + 1], board[i - 2][j + 2], board[i - 3][j + 3]) && board[i][j] == player) {

        numOfFours++

      }
    }
  }
  return numOfFours;

}

function checkThrees(player) {

  let numOfThrees = 0;

  for (let i = 0; i < 7; i++) {
    for (let j = 0; j < 6; j++) {

      if ((i < 5) && equals3(board[i][j], board[i + 1][j], board[i + 2][j]) && board[i][j] == player) {

        numOfThrees++;

        // vertical checking

      } else if ((j < 4) && equals3(board[i][j], board[i][j + 1], board[i][j + 2]) && board[i][j] == player) {

        numOfThrees++

        // diagonal 1 checking

      } else if ((i < 5) && (j < 4) && equals3(board[i][j], board[i + 1][j + 1], board[i + 2][j + 2]) && board[i][j] == player) {

        numOfThrees++;

        // diagonal 2 checking

      } else if ((i > 1) && (j < 4) && equals3(board[i][j], board[i - 1][j + 1], board[i - 2][j + 2]) && board[i][j] == player) {

        numOfThrees++

      }
    }
  }
  return numOfThrees;
}

function checkTwos(player) {

  let numOfTwos = 0;

  for (let i = 0; i < 7; i++) {
    for (let j = 0; j < 6; j++) {

      if ((i < 6) && equals2(board[i][j], board[i + 1][j]) && board[i][j] == player) {

        numOfTwos++;

        // vertical checking

      } else if ((j < 5) && equals2(board[i][j], board[i][j + 1]) && board[i][j] == player) {

        numOfTwos++

        // diagonal 1 checking

      } else if ((i < 6) && (j < 5) && equals2(board[i][j], board[i + 1][j + 1]) && board[i][j] == player) {

        numOfTwos++;

        // diagonal 2 checking

      } else if ((i > 0) && (j < 5) && equals2(board[i][j], board[i - 1][j + 1]) && board[i][j] == player) {

        numOfTwos++

      }
    }
  }
  return numOfTwos;
}


function nextSpace(i) {
  let col = i;
  for (let j = 5; j >= 0; j--) {
    if (board[col][j] == 'empty') {
      return j;
    }
  }
}

function aiMove() {
  let row = floor(random(1) * 7);
  board[row][nextSpace(row)] = ai;
  currentPlayer = human;
}

function bestMove() {
  let bestScore = -Infinity;
  let move = [];

  for (let i = 0; i < 7; i++) {
    for (let j = 0; j < 6; j++) { //let j = nextSpace(i);

      if (nextSpace(i) == j) {

      if (checkTwos(human) == 0 && checkTwos(ai) == 0) {
        let col = floor(random(1) * 7);
        let row = nextSpace(col);

        move = [col, row];
      } else {
        board[i][nextSpace(i)] = ai;
        let score = minimax(board, 5, -Infinity, Infinity, false);

        board[i][nextSpace(i) + 1] = 'empty';

        if (score > bestScore) {
          bestScore = score;
          move = [
            i,
            j
          ];
        }

      }
      }
    }
  }

  board[move[0]][nextSpace(move[0])] = ai;
  currentPlayer = human;
}

let scores = {
  red: +100000,
  yellow: -100000,
  tie: 0
}

function useHeuristic() {

  let aiFours = checkFours(ai);
  let humanFours = checkFours(human);

  let aiThrees = checkThrees(ai) * 1000;
  let humanThrees = checkThrees(human) * 1000;

  let aiTwos = checkTwos(ai) * 10;
  let humanTwos = checkTwos(human) * 10;

  if (aiFours > 0) {
    return 100000;
  }

  if (humanFours > 0) {
    return -100000;
  }

  let heuristicScore = aiThrees + aiTwos - humanThrees - humanTwos;

  console.log('heuristicScore: ' + heuristicScore);
  return heuristicScore;
}

function minimax(board, depth, alpha, beta, isMaximizing) {
  let result = checkWinner();

  if (result != null) {
    return scores[result];
  }

  if (depth == 0) {
    let eval = useHeuristic();

    return eval;
  }

  if (isMaximizing) {

    let bestScore = -Infinity;
    for (let i = 0; i < 7; i++) {
      for (let j = 0; j < 6; j++) {
        if (nextSpace(i) == j) {
          board[i][j] = ai;
          let score = minimax(board, depth - 1, alpha, beta, false);
          board[i][j] = 'empty';
          bestScore = max(score, bestScore);
          alpha = max(alpha, score);
          if (beta <= alpha) {
            break;
          }
        }
      }
    }
    return bestScore;
  } else {

    let bestScore = -Infinity;
    for (let i = 0; i < 7; i++) {
      for (let j = 0; j < 6; j++) {
        if (nextSpace(i) == j) {
          board[i][j] = human;
          let score = minimax(board, depth - 1, alpha, beta, true);
          board[i][j] = 'empty';
          bestScore = min(score, bestScore);
          beta = min(beta, score);
          if (beta <= alpha) {
            break;
          }
        }
      }
    }
    return bestScore;
  }
}

function mouseMoved() {

  isMouseMoved = true;

}

function mousePressed() {

  // Drop piece for human player

  if (currentPlayer == human) {
    let i = floor(abs(((mouseX + 30) - 3 * xBorder) / (xBorder + holeDiameter)));

    board[i][nextSpace(i)] = human;
    currentPlayer = ai;
    setTimeout(bestMove, 500);
  }

  // Remove taken spots from available

  for (let i = 0; i < available.length; i++) {
    if (available[i] !== '') {
      available.splice(i, 1);
    }
  }
}


function draw() {

  // Board background drawing

  background(0, 150, 255);

  for (let i = 0; i < 7; i++) {
    for (let j = 0; j < 6; j++) {

      // Draw the holes

      let holeX = (i + 3) * xBorder + ((2 * i)) * holeRadius;
      let holeY = (j + 4) * yBorder + ((2 * j)) * holeRadius;

      fill(color(255, 255, 255));
      noStroke();
      ellipse(holeX, holeY, holeDiameter);

      // Pieces

      let spot = board[i][j];

      if (spot == ai) {
        fill(color(255, 0, 0));
        ellipse(holeX, holeY, holeDiameter);
      } else if (spot == human) {
        fill(color(255, 255, 0));
        ellipse(holeX, holeY, holeDiameter);
      }
    }
  }

  if (isMouseMoved) {
    let i = floor(abs(((mouseX + 30) - 3 * xBorder) / (xBorder + holeDiameter)));

    let j = nextSpace(i);

    noFill();
    stroke(color(255, 255, 0));
    strokeWeight(10);

    ellipse((i + 3) * xBorder + ((2 * i)) * holeRadius, (j + 4) * yBorder + ((2 * j)) * holeRadius, 60);
  }
  // Recording Result of Game

  let result = checkWinner();
  if (result != null) {
    console.log(result);
    noLoop();
  }
}

Проблема: Когда я запускаю код и наступает очередь ИИ, происходят две вещи. Некоторое время он размышляет, замедляя работу моего браузера, а затем выдает мне одну из двух ошибок. Либо он говорит, что в моем коде есть проблема бесконечной рекурсии, либо он говорит, что «перемещение» в строке 235 не определено (от второй до последней строки bestMove()).

То, что я пробовал: Я попытался записать на консоль множество элементов, включая глубину в minimax() (чтобы убедиться, что программа достигает глубины 0), значение heuristi c в конце useHeuristic() (чтобы убедиться, что оно использует heuristi c) и переместиться в конце bestMove() (чтобы увидеть, действительно ли оно не определено, что, по-видимому, и есть).

Также, чтобы уточнить, сначала я получал ошибку бесконечной рекурсии, но потом она переключилась на перемещение - неопределенная ошибка, без каких-либо изменений кода. Я нахожу это очень странным, и я действительно надеюсь, что кто-то может мне помочь. Спасибо!

ОБНОВЛЕНИЕ: Я изменил вторую строку bestMove() на эту: let move = [];, которая, кажется, исправила и бесконечную ошибку рекурсии, я еще немного повозился и разобрался что программа думает move[0], от второй до последней строки bestMove() не определено. Я не уверен, почему это так.

Ссылка на эскиз: https://editor.p5js.org/aaravshah18/sketches/KDAykjkZY