minimax를 사용한 간단한 tic-tac-toe AI

재귀 알고리즘에 대해 더 많이 배우면서 minimax에 대해 알게 되었습니다.
minimax에 대해 더 알고 싶다면 적극 추천합니다.

tic-tac-toe의 규칙은 다음과 같습니다.

3x3 보드와 2명의 플레이어가 있습니다.

각 사각형은 3가지 다른 상태에 있을 수 있습니다.
플레이어 1의 경우 'X', 플레이어 2의 경우 'O' 또는 공백일 수 있습니다.

이기려면 같은 기호 3개를 수평선, 수직선 또는 대각선으로 정렬해야 합니다. 이것은 정사각형당 3개의 옵션이 있고 9개의 정사각형이 있음을 의미합니다.

3⁹ = 19,683 가능한 보드 상태.

즉, minimax를 사용하여 컴퓨터에 게임 방법을 가르칠 수 있습니다.

우리는 모든 움직임을 시도하고 최선의 선택이 무엇인지 알아냄으로써 최선의 움직임을 결정할 수 있습니다.

먼저 웹 페이지를 만들어야 합니다.
보드를 보여주기 위해 아주 기본적인 웹사이트를 만들었습니다.

내 Github에서 완성된 코드를 살펴볼 수 있습니다.



JavaScrip을 사용하여 모든 사각형에 이벤트 리스너를 추가하고 사각형을 클릭하면 해당 사각형을 채울 것입니다.
9개의 이벤트 리스너를 작성하고 싶지 않으므로 for 루프로 추가할 것입니다.

const posList = [
  document.querySelector(".pos-1"),
  document.querySelector(".pos-2"),
  document.querySelector(".pos-3"),
  document.querySelector(".pos-4"),
  document.querySelector(".pos-5"),
  document.querySelector(".pos-6"),
  document.querySelector(".pos-7"),
  document.querySelector(".pos-8"),
  document.querySelector(".pos-9"),
];


for (let i = 0; i < posList.length; i++) {
  posList[i].addEventListener("click", function () {
    insertLetter(user, i);
    botMove();
  });
}

추가 루프를 사용하지 않기 위해 사용자가 움직일 때마다 botMove() 함수를 호출하고 있으며 이벤트 루프로만 작업하고 있습니다.

이제 모든 이벤트 리스너가 준비되었으므로 알고리즘을 생성하거나 최소화해야 합니다.

이렇게 하려면 몇 가지 도우미 함수를 만들어야 합니다.insertLetter botMove checkwin 및 checkwinmark와 같은

function is_free(position) {
  if (board[position] == " ") {
    return true;
  } else {
    return false;
  }
}

function check_draw() {
  for (let i = 0; i < board.length; i++) {
    if (board[i] == " ") {
      return false;
    }
  }
  return true;
}

function check_win() {
  if (board[0] == board[1] && board[0] == board[2] && board[0] != " ") {
    return true;
  } else if (board[3] == board[4] && board[3] == board[5] && board[3] != " ") {
    return true;
  } else if (board[6] == board[7] && board[6] == board[8] && board[6] != " ") {
    return true;
  } else if (board[0] == board[3] && board[0] == board[6] && board[0] != " ") {
    return true;
  } else if (board[1] == board[4] && board[1] == board[7] && board[1] != " ") {
    return true;
  } else if (board[2] == board[5] && board[2] == board[8] && board[2] != " ") {
    return true;
  } else if (board[0] == board[4] && board[0] == board[8] && board[0] != " ") {
    return true;
  } else if (board[6] == board[4] && board[6] == board[2] && board[6] != " ") {
    return true;
  } else {
    return false;
  }
}

function check_win_mark(mark) {
  if (board[0] == board[1] && board[0] == board[2] && board[0] == mark) {
    return true;
  } else if (board[3] == board[4] && board[3] == board[5] && board[3] == mark) {
    return true;
  } else if (board[6] == board[7] && board[6] == board[8] && board[6] == mark) {
    return true;
  } else if (board[0] == board[3] && board[0] == board[6] && board[0] == mark) {
    return true;
  } else if (board[1] == board[4] && board[1] == board[7] && board[1] == mark) {
    return true;
  } else if (board[2] == board[5] && board[2] == board[8] && board[2]) {
    return true;
  } else if (board[0] == board[4] && board[0] == board[8] && board[0] == mark) {
    return true;
  } else if (board[6] == board[4] && board[6] == board[2] && board[6] == mark) {
    return true;
  } else {
    return false;
  }
}

function showWin() {
  resultModal.style.display = "block";
  resultText.innerHTML = "You Won";
  initialText.style.display = "none";
}

function showLost() {
  resultModal.style.display = "block";
  resultText.innerHTML = "You Lost";
  initialText.style.display = "none";
}

function showDraw() {
  resultModal.style.display = "block";
  resultText.innerHTML = "Draw";
  initialText.style.display = "none";
}

function insertLetter(letter, position) {
  if (is_free(position)) {
    board[position] = letter;
    posList[position].innerHTML = letter;
    if (check_draw()) {
      console.log("Draw");
      showDraw();
    }
    if (check_win()) {
      if (letter == "X") {
        showLost();
        console.log("BOT WINS");
      } else {
        console.log("User wins");
      }
    }
    return;
  } else {
    console.log("That space is not avaialble");
    return;
  }
}

function botMove() {
  var best_score = -800;
  var best_move = 0;

  for (let i = 0; i < board.length; i++) {
    if (board[i] == " ") {
      board[i] = bot;
      var score = minimax(board, 0, false);
      board[i] = " ";
      if (score > best_score) {
        best_score = score;
        best_move = i;
      }
    }
  }
  console.log(score);
  console.log(best_move);
  console.log(board);
  insertLetter(bot, best_move); // Here we insert the final move
  return;
}

이제 우리는 minimax 알고리즘에 뛰어들 필요가 있습니다.

우리의 minimax 알고리즘은 보드에서 가능한 모든 이동 조합을 반복하고 사용 가능한 최상의 이동을 선택합니다.

우리는 이동 결과가 손실일 때 -800을 할당하고 이동 결과가 승리할 때 800을 할당합니다.

가능한 모든 위치를 반복하려면 사용자 이동에 지능을 추가해야 합니다.

우리는 여분을 사용하여 이것을하고 있습니다var board = [" ", " ", " ", " ", " ", " ", " ", " ", " "];이 보드는 해당 요소에 더 쉽게 액세스할 수 있는 방식으로 보드를 나타내는 데만 사용됩니다.

일반적으로 minimax를 사용하면 검색의 깊이를 정의해야 하지만 보드가 있을 수 있는 상태가 많지 않습니다. 그래서 우리는 깊이를 사용하지 않고 벗어날 수 있습니다.

function minimax(board, depth, is_maximizing) {
  if (check_win_mark(bot)) {
    return 1;
  } else if (check_win_mark(user)) {
    return -1;
  } else if (check_draw()) {
    return 0;
  }

  if (is_maximizing) {
    var best_score = -800;
    for (let i = 0; i < board.length; i++) {
      if (board[i] == " ") {
        board[i] = bot;
        var score = minimax(board, 0, false);
        board[i] = " ";
        if (score > best_score) {
          best_score = score;
        }
      }
    }
    return best_score;
  } else {
    best_score = 800;
    for (let i = 0; i < board.length; i++) {
      if (board[i] == " ") {
        board[i] = user;
        score = minimax(board, 0, true);
        board[i] = " ";
        if (score < best_score) {
          best_score = score;
        }
      }
    }
    return best_score;
  }
}

라이브 버전here!을 살펴볼 수 있습니다.

행복한 해킹!
카를로 먼로이.