[Algorithm] 미니맥스 / 알파-베타 가지치기 알고리즘 톺아보기

미니맥스 알고리즘

---

개념

💡 제로섬 게임은 한 플레이어가 이득을 얻으면 다른 플레이어는 그만큼 손해를 보는 게임을 가리킨다.

 

미니맥스 알고리즘은 틱택토, 체스처럼 2명이 참여하는 제로섬 게임에서 가장 널리 사용하는 알고리즘으로, 모든 플레이어가 최선의 수를 둔다고 가정하고 가능한 모든 수를 고려하여 승리할 수 있는 전략을 도출할 때 사용한다. X 플레이어는 승리하기 위해 최대 점수를 얻으려 하고, O 플레이어는 패배하지 않기 위해 최소 점수를 얻으려 하는 상황에서 최적의 해를 찾는 방법이다.

 

 

현재 X 플레이어 차례이고, X 플레이어가 선택할 수 있는 곳은 1, 4, 5번 인덱스(Zero-Based)라고 가정해 본다. X가 이기면 +100점, O가 이기면 -100점을 획득한다. 보드의 모든 수를 뒀지만 무승부일 경우엔 0점이 된다.

 

1. X 플레이어가 1번 인덱스를 선택할 경우 → -100점
   • 다음 턴에서 O 플레이어가 선택할 수 있는 곳은 4, 5번 인덱스
     • O 플레이어가 4번 인덱스를 선택하면 O가 승리해서 -100점
     • O 플레이어가 5번 인덱스를 선택하면 X가 승리해서 +100점
   • O 플레이어는 최소 점수를 획득할 수 있는 4번 인덱스 선택
2. X 플레이어가 4번 인덱스를 선택할 경우 → +100점
3. X 플레이어가 5번 인덱스를 선택할 경우 → -100점
   • 다음 턴에서 O 플레이어가 선택할 수 있는 곳은 1, 4번 인덱스
     • O 플레이어가 1번 인덱스를 선택하면 X가 승리해서 +100점
     • O 플레이어가 4번 인덱스를 선택하면 O가 승리해서 -100점
   • O 플레이어는 최소 점수를 획득할 수 있는 4번 인덱스 선택

 

위 평가 과정을 통해 X 플레이어는 4번 인덱스를 선택함으로써 최대 점수를 획득하고 승리할 수 있다는 결론에 도달한다. 이처럼 미니맥스 알고리즘은 자신의 점수를 최대화하는 단계와 상대방의 점수를 최소화하는 단계를 재귀적으로 반복하여 가능한 모든 움직임을 평가한 후 최선의 위치를 선택한다.

 

구현

💡 미니맥스 알고리즘은 일반적으로 board, isMaximizing, depth 3개 파라미터를 받는 방식으로 구현한다. 아래 코드에선, 플레이어의 순서를 바꾸거나 승리 조건을 변경하는 등의 옵션 때문에 추가적인 파라미터가 필요한 점 참고. 승리 여부를 평가하는 evaluateWinning 함수(참고 포스팅)는 마지막 수를 둔 곳을 기준으로 가로/세로/대각선으로 검사하기 때문에 lastIndex 파라미터가 필요하다.

export const evaluateWinning = (
  board: TBoard,
  winCondition: number,
  lastIndex: number,
  identifier: BasePlayer | null = null,
  resultType: 'position' | 'winner' = 'position',
) => {
  const player = identifier ?? board[lastIndex].identifier;
  if (!player) return null;

  const size = getBoardSize(board);
  const { row: lastRow, col: lastCol } = getCoordinates(lastIndex, size);

  const directions = [
    { deltaRow: 0, deltaCol: 1 }, // 가로
    { deltaRow: 1, deltaCol: 0 }, // 세로
    { deltaRow: 1, deltaCol: 1 }, // 우하 대각선
    { deltaRow: 1, deltaCol: -1 }, // 좌하 대각선
  ];

  for (const { deltaRow, deltaCol } of directions) {
    const winningIndexes = checkDirection(
      board,
      winCondition,
      player,
      size,
      { lastRow, lastCol },
      { deltaRow, deltaCol },
    );

    // 승리한 위치의 인덱스 배열 반환
    if (winningIndexes) {
      if (resultType === 'winner') return player;
      else
        return winningIndexes.map(({ row, col }) =>
          getLinearIndex(row, col, size),
        );
    }
  }

  return null;
};

const checkDirection = (
  board: TBoard,
  winCondition: number,
  identifier: BasePlayer,
  size: number,
  { lastRow, lastCol }: RowColPair<'lastRow' | 'lastCol'>,
  { deltaRow, deltaCol }: RowColPair<'deltaRow' | 'deltaCol'>,
) => {
  const searchDirection = (deltaRow: number, deltaCol: number) => {
    const winningIndexes = [];

    // 마지막 놓았던 위치는 제외하기 위해 i = 1 부터 시작
    for (let i = 1; i < winCondition; i++) {
      const curRow = i * deltaRow + lastRow;
      const curCol = i * deltaCol + lastCol;

      // 보드 범위를 벗어났으면 검사 중지
      if (!isWithinBounds(size, curRow, curCol)) break;
      // 기호가 일치하지 않으면 검사 중지
      if (getIdentifierFromRowCol(board, size, curRow, curCol) !== identifier)
        break;

      winningIndexes.push({ row: curRow, col: curCol });
    }

    return winningIndexes;
  };

  // 양쪽 방향으로 연속된 마크 검사
  const forwardWinningIndexes = searchDirection(deltaRow, deltaCol);
  const backwardWinningIndexes = searchDirection(-deltaRow, -deltaCol);

  const combinedIndexes = [{ row: lastRow, col: lastCol }]; // 마지막 놓았던 위치 저장
  combinedIndexes.push(...forwardWinningIndexes, ...backwardWinningIndexes);

  return combinedIndexes.length >= winCondition ? combinedIndexes : null;
};

 

미니맥스 알고리즘은 기본적으로 DFS(깊이 우선 탐색) 방식으로 진행된다. findBestMove 함수는 최선의 위치를 찾기 위해 보드, 승리 조건, 플레이어 기호를 받아 아직 수를 두지 않은 곳부터 미니맥스 함수를 호출한다.

 

미니맥스 함수 내부에선, 최대화 단계일 땐 하위 노드 중 가장 큰 값을 bestScore로 설정하고, 최소화 단계일 땐 가장 작은 값을 bestScore로 설정한다. 이 과정은 승리한 플레이어가 나오거나 무승부(보드의 모든 칸을 채움)가 될 때까지 하위 노드를 재귀적으로 탐색한다.

const minimax = (
  board: TBoard, // 게임 보드
  winCondition: number, // 승리하기 위해 필요한 연속된 기호의 개수 (3x3 보드에선 3)
  isMaximizing: boolean, // 최대화 단계 여부
  lastIndex: number, // 마지막 수를 둔 인덱스
  player: BasePlayer, // 최대 점수를 얻으려는 플레이어의 식별자 e.g. 'X'
  opponent: BasePlayer, // 최소 점수를 얻으려는 플레이어의 식별자 e.g. 'O'
): number => {
  // evaluateWinning 함수는 보드를 평가하여 승리한 플레이어의 기호 "O"|"X" 혹은 null을 반환한다
  const winner = evaluateWinning(
    board,
    winCondition,
    lastIndex,
    null,
    'winner',
  );

  // 승, 패 또는 무승부에 대한 점수 반환
  if (winner) return winner === player ? Score.Win : Score.Lose; // 100 | -100
  if (!hasAvailableMove(board)) return Score.Draw; // 무승부 0

  // bestScore 및 compare 함수 초기화
  let bestScore = isMaximizing ? -Infinity : Infinity;
  const compareFn = isMaximizing ? Math.max : Math.min;
  const nextPlayer = isMaximizing ? player : opponent;

  // 가능한 모든 수를 탐색하고 점수 계산
  for (let i = 0; i < board.length; i++) {
    if (board[i].identifier === null) {
      board[i].identifier = nextPlayer; // 플레이어 기호로 채움
      const score = minimax(
        board,
        winCondition,
        !isMaximizing,
        i,
        player,
        opponent,
      );
      board[i].identifier = null; // 원상복귀

      bestScore = compareFn(score, bestScore);
    }
  }

  return bestScore;
};

const findBestMove = (
  board: TBoard,
  winCondition: number,
  player: BasePlayer, // 'X' | 'O'
): number | null => {
  // 미니맥스 알고리즘은 일반적으로 최대화 단계부터 시작한다. 함수를 호출하면 최대화 단계가 시작된다
  // 최대화 단계에선 가장 큰 값을 찾기 위해 가장 작은 수(-Infinity)를 기본값으로 설정한다
  let bestScore = -Infinity;
  let bestMove = null;
  const opponent = getOpponent(player);

  for (let i = 0; i < board.length; i++) {
    // 빈 칸을 현재 플레이어 기호로 채운 후 계산된 점수 중 가장 큰 곳의 위치를 bestMove로 설정한다
    if (board[i].identifier === null) {
      board[i].identifier = player;
      // 다음 호출은 최소화 단계이므로 isMaximizing 파라미터는 false로 넘긴다
      const score = minimax(board, winCondition, false, i, player, opponent);
      board[i].identifier = null;

      if (score > bestScore) {
        bestScore = score;
        bestMove = i;
      }
    }
  }

  return bestMove;
};

 

빠른 승리, 느린 패배

빠른 승리

현재 플레이어 X가 0, 2번 인덱스를 선택하면 승리할 수 있다고 가정해 보자. findBestMove 함수 내부에선 score > bestScore 상황일 때만 bestMove 인덱스를 갱신한다. 0, 2번 인덱스에 대한 점수는 모두 100점이므로 결과적으로 먼저 계산했던 0번 인덱스를 선택하게 된다. 하지만 2번 인덱스를 선택했다면 더 적은 턴으로 승리할 수 있기 때문에 0번 인덱스보다 더 좋은 선택으로 볼 수 있다.

 

턴 수를 게임 점수에 반영하지 않았을 때 기보

만약 턴 수를 게임 점수에 반영한다면, 더 적은 턴을 선택해서 빠른 승리를 선호하도록 만들 수 있다. 턴 수는 탐색 깊이를 의미하므로 최대화 단계일 땐 100 - 깊이, 최소화 단계일 땐 깊이 - 100 방식으로 계산할 수 있다. 턴 수를 게임 점수에 반영했을 때 0번 인덱스는 97점, 2번 인덱스는 99점이 되고, 부모 노드에선 가장 큰 점수를 낸 2번 인덱스를 선택하게 된다.

 

턴 수를 게임 점수에 반영했을 때 기보

 

느린 패배

턴 수를 게임 점수에 반영하면 더 느린 패배를 선호하게 된다. 아래 이미지는 X 플레이어가 어떤 이동을 선택하든 패배하는 상황이다. 턴 수를 점수에 반영하지 않았다면 0, 2, 3, 4 인덱스에 대한 점수는 모두 -100점이 돼서 가장 처음에 계산했던 0번 인덱스를 선택하게 된다. 반면, 점수에 턴 수를 반영하면 게임을 진행할수록 상대방 점수도 그만큼 감소하기 때문에 결과적으로 최대한 많은 턴을 끌고 갈 수 있는 인덱스를 선택해서 패배가 지연된다.

 

턴 수를 게임 점수에 반영해서 패배를 지연시키는 기보 (일부 가능한 수 생략)

위 이미지를 보면 상대편 기호 O가 5, 8번 인덱스에 연속해서 2개 배치돼 있다. 실제 사람 플레이어라면 즉시 패배하는 것을 방지하기 위해 2번 인덱스를 선택해서 방어할 것이다. 턴 수를 점수에 반영하면 상대편 승리를 최대한 늦추기 때문에 실제 사람이 생각하고 플레이하는 것처럼 만들 수 있다.

 

코드 수정

minimax() 함수 파라미터에 턴 수를 나타내는 depth 를 추가하고 점수 계산에 depth를 반영한다(최대화 단계: 점수 - 턴 수, 최소화 단계: -점수 + 턴 수). minimax() 함수를 호출할 때마다 다음 턴으로 넘어가기 때문에 함수 호출 시엔 현재 depth + 1을 인자로 넘긴다.

const minimax = (
  board: TBoard,
  winCondition: number,
  depth: number,
  isMaximizing: boolean,
  lastIndex: number,
  player: BasePlayer,
  opponent: BasePlayer,
): number => {
  const winner = evaluateWinning(
    board,
    winCondition,
    lastIndex,
    null,
    'winner',
  );
  // 현재 턴 수(depth)를 점수에 반영한다
  if (winner) return winner === player ? Score.Win - depth : Score.Lose + depth;
  if (!hasAvailableMove(board)) return Score.Draw;

  let bestScore = isMaximizing ? -Infinity : Infinity;
  const compareFn = isMaximizing ? Math.max : Math.min;
  const nextPlayer = isMaximizing ? player : opponent;

  for (let i = 0; i < board.length; i++) {
    if (board[i].identifier === null) {
      board[i].identifier = nextPlayer;
      // minimax 함수를 호출할 때마다 다음 턴으로 넘어가므로 현재 depth에 1을 더한다
      const score = minimax(
        board,
        winCondition,
        depth + 1,
        !isMaximizing,
        i,
        player,
        opponent,
      );
      board[i].identifier = null;
      bestScore = compareFn(score, bestScore);
    }
  }

  return bestScore;
};

 

시간 복잡도

미니맥스 알고리즘은 게임 트리의 모든 가능한 수를 탐색하여 최적의 수를 찾는 전략이기 때문에 일반적으로 $O(b^d)$ 지수 시간 복잡도를 갖는다. $b(branch)$는 한 상태에서 선택할 수 있는 최대 가짓수, $d(depth)$는 리프 노드까지의 최대 깊이를 의미한다. 각 단계마다 $b$개의 선택지가 있고, 이러한 선택지들이 최대 $d$단계까지 계속될 경우, 탐색해야 할 총노드의 수는 대략 $b^d$가 된다.

 

예를 들어 게임 첫 단계에서 플레이어가 선택할 수 있는 가지 수가 A, B, C 3가지이고, 각 선택지에서 3가지 다른 선택을 할 수 있다면 시간 복잡도는 $b^d = 3^2 = 9$가 된다.

 

 

리팩토링

const minimax = (
  board: TBoard,
  winCondition: number,
  depth: number,
  lastIndex: number,
  roles: Roles,
) => {
  // ...생략

  // #3,5 로컬 컨텍스트를 반환하는 함수 분리
  let { isMaximizing, bestScore, compareFn } = getMinimaxContext(depth);

  for (let i = 0; i < board.length; i++) {
    if (board[i].identifier === null) {
      // #4 보드 평가 함수 분리
      const score = evaluateMove(board, winCondition, depth, i, roles);
      bestScore = compareFn(score, bestScore);
    }
  }

  return bestScore;
};

const findBestMove = (
  board: TBoard,
  winCondition: number,
  player: BasePlayer,
) => {
  // ...생략

  // #1 플레이어 파라미터 간소화
  const roles = { player, opponent: getOpponent(player) };
  // #2 bestScore, bestMove 각 변수를 하나의 객체로 관리
  const bestOutcome: BestOutcome = { score: -Infinity, move: null };

  for (let i = 0; i < board.length; i++) {
    if (board[i].identifier === null) {
      // #4 보드 평가 함수 분리
      const score = evaluateMove(board, winCondition, depth, i, roles);

      if (score > bestOutcome.score) {
        bestOutcome.score = score;
        bestOutcome.move = i;
      }
    }
  }

  return bestOutcome.move;
};

 

❶ 플레이어 파라미터 간소화

현재 플레이어(player), 상대 플레이어(opponent)를 각각 파라미터로 전달하는 대신, 두 역할을 포함하는 단일 객체로 만들어서 함수 파라미터를 간소화할 수 있다.

const roles = { player, opponent: getOpponent(player) };

 

❷ bestScore, bestMove 각 변수를 하나의 객체로 관리

const bestOutcome: BestOutcome = { score: -Infinity, move: null };

 

❸ isMaximizing 파라미터 제거

현재 턴 수(depth)가 홀수라면 항상 최소화 단계이므로, 굳이 파라미터로 넘길 필요 없이 depth를 인자로 받아 isMaximizing 불리언을 반환하는 함수로 분리해서 사용할 수 있다.

const isMaximizing = (depth: number) => depth % 2 === 0;

 

❹ 보드 평가 함수 evaluateMove 분리

하위 노드를 탐색한 후 평가한 점수를 반환하는 로직은 minimax findBestMove 두 함수에서 중복해서 사용하고 있으므로 별도 함수로 분리해서 재사용할 수 있다.

const evaluateMove = (
  board: TBoard,
  winCondition: number,
  depth: number,
  lastIndex: number,
  roles: Roles,
) => {
  board[lastIndex].identifier = isMaximizing(depth)
    ? roles.player
    : roles.opponent;
  const score = minimax(board, winCondition, depth + 1, lastIndex, roles); // Evaluate the board
  board[lastIndex].identifier = null;

  return score;
};

 

❺ 로컬 컨텍스트를 반환하는 함수 분리

각 단계마다 최대화 여부인지 확인하고, 이 값에 의존하는 bestScore, compareFn 로컬 변수가 필요하므로 depth를 인자로 받아 이들을 반환하는 함수로 분리하면 코드를 더 깔끔하게 만들 수 있다.

const getMinimaxContext = (depth: number) => {
  const isMax = isMaximizing(depth);
  return {
    isMaximizing: isMax,
    bestScore: isMax ? -Infinity : Infinity,
    compareFn: isMax ? Math.max : Math.min,
  };
};

 

 

알파-베타 가지치기

---

개념

미니맥스 알고리즘은 게임 트리의 모든 노드를 탐색해서 결과를 예측하지만, 꼭 모든 노드를 탐색할 필요는 없다. 아래 이미지를 기준으로 A → B → C → C1 노드까지 탐색했다고 가정해 보자. 현재 C1 노드는 -98점으로 평가된 상태다. 이제 C2 노드 점수에 따라 아래 2가지 상황을 예상해 볼 수 있다.

 

위에서 살펴본 미니맥스 빠른 승리 예시 보드를 도식화한 이미지

1. C2 노드가 C1(-98) 보다 작은 점수가(-100) 나왔을 때
   • 최소화 단계에 있는 C 노드는 C2(-100) 노드를 선택하고, C 노드의 점수는 -100점이 된다
   • 최대화 단계에 있는 루트 노드는 자식 노드 중 가장 높은 점수를 가진 B(99)를 선택한다
2. C2 노드가 C1(-98) 보다 큰 점수가(100) 나왔을 때
   • 최소화 단계에 있는 C 노드는 C1(-98) 노드를 선택하고, C 노드의 점수는 -98점이 된다
   • 최대화 단계에 있는 루트 노드는 자식 노드 중 가장 높은 점수를 가진 B(99)를 선택한다

 

C2 노드가 어떤 값이 나오든 루트 노드는 항상 B 노드를 선택한다

결과적으로 C2 노드가 어떤 값이 나오든 루트 노드에선 항상 B 노드를 선택하는 상황이 된다. 즉, C2 노드의 평가 결과가 B 노드를 선택하는데 전혀 영향을 미치지 않고 있다. 이런 상황에선 C2 노드를 탐색할 필요가 없어진다.

 

알파-베타 가지치기는 위 같은 원리를 이용해 미니맥스 알고리즘이 불필요한 탐색을 건너뛰도록 만드는 기법으로, 알파($\alpha$) 값과 베타($\beta$) 값을 이용해 남은 자식 노드의 탐색 여부를 결정한다.

 

• $\alpha$ 알파 : 현재 플레이어가 발견한 최대 점수
  • 가장 작은 수 $-\infin$ 를 초기값으로 지정
  • 최대화 노드에서만 업데이트
• $\beta$ 베타 : 상대 플레이어가 발견한 최소 점수
  • 가장 큰 수 $\infin$를 초기값으로 지정
  • 최소화 노드에서만 업데이트

 

C1 노드를 평가한 후 부모 노드 C의 최소 점수(베타)는 -98 점이 되고, 최대화 단계에 있는 루트 노드는 현재까지 확인된 최대 점수(알파)인 99점 보다 높은 점수를 발견하지 못하면 항상 B 노드(99)를 선택한다. 즉, C 노드에서 계산된 베타 값(-98)이 알파 값(99) 이하인 경우, 루트 노드는 항상 B 노드를 선택하게 되는 것이다.

 

어떤 노드에서 알파 값이 베타 값보다 크거나 같은 상황($\alpha \geq \beta$)이라면, 현재 노드의 최적 해를 이미 발견한 상태로 간주할 수 있고, 이는 자식 노드를 더 이상 탐색할 필요가 없음을 나타낸다.

 

알파, 베타 값은 하위 노드를 탐색하면서 아래 과정을 통해 업데이트 된다.

 

자식 노드를 탐색하면서 알파, 베타 값을 업데이트하는 과정

1. 루트 노드 : 알파, 베타 기본값 설정 → $[-\infty, \infty]$
2. A 노드 탐색
   • 하위 노드 탐색 후(이미지에선 생략) 평가 점수 97 반환(루트 노드 복귀)
   • 루트 노드는 최대화 단계이므로 알파 값 업데이트 $[-\infty, \infty]$ → $[97, \infty]$
3. B 노드 탐색
   • 하위 노드 탐색 후(이미지에선 생략) 평가 점수 99 반환(루트 노드 복귀)
   • 루트 노드는 최대화 단계이므로 알파 값 업데이트 $[97, \infty]$ → $[99, \infty]$
4. C 노드 탐색 : 부모 노드로부터 알파, 베타 값 $[99, \infty]$ 전달받음
   • C1 노드 탐색 후 평가 점수 -98 반환(C 노드 복귀)
   • C 노드는 최소화 단계이므로 베타 값 업데이트 $[99, \infty]$ → $[99, -98]$
   • 알파 값 99가 베타 값 -98보다 더 크므로 다음 노드(C2) 탐색 안 함 — ✂️ Pruning

 

예제

먼저 루트 노드에서 알파, 베타 기본값을 $[-\infty, \infty]$ 설정한 후 자식 노드로 전달한다. 각 자식 노드에선 전달받은 값을 로컬 변수로 관리하고, 하위 노드 평가 결과에 따라 업데이트한다. 최대화 단계에 있는 노드는 알파 값을, 최소화 단계에 있는 노드는 베타 값을 업데이트해서 남은 자식 노드의 탐색 여부를 결정한다.

 

A1 노드 알파, A 노드 베타 업데이트 과정

A - A1 노드 탐색

• Max | A1 : 가장 큰 자식 노드(A4) 값(3)으로 알파 변수 업데이트 $[-\infin, \infin]$ → $[3, \infin]$
• Min | A : A1 노드 값(3)으로 베타 변수 업데이트 $[-\infin, \infin]$ → $[-\infin, 3]$

 

A2 노드 알파, A 노드 베타 업데이트 과정

A - A2 노드 탐색

• Max | A2 : A5 노드 값(5)으로 알파 변수 업데이트 $[-\infin, 3]$ → $[5, 3]$
  ✂️ 업데이트한 알파 값(5)이 베타 값(3) 보다 크므로 더 이상 자식 노드 탐색 안 함
• Min | A : A1 노드(3) 보다 더 작은 값을 발견하지 못했으므로 베타 변수 유지 $[-\infin, 3]$
• Max | Root : A 노드 값(3)으로 알파 변수 업데이트 $[-\infin, \infin]$ → $[3, \infin]$

 

B1 노드 알파, B 노드 베타 업데이트 과정

B - B1 노드 탐색

• Max | B1 : 가장 큰 자식 노드(B4) 값(1)이 현재 알파 값(3) 보다 작으므로 알파 변수 유지 $[3,\infin]$
• Min | B : B1 노드 값(1)으로 베타 변수 업데이트 $[3, \infin]$ → $[3, 1]$
• ✂️ 알파 값(3)이 업데이트한 베타 값(1) 보다 크므로 더 이상 자식 노드 탐색 안 함

 

구현

const minimax = (
  board: TBoard,
  winCondition: number,
  depth: number,
  lastIndex: number,
  roles: Roles,
  cutBounds: CutBounds,
): number => {
  // Check if there is a winner
  const winner = evaluateWinning(
    board,
    winCondition,
    lastIndex,
    null,
    'winner',
  );
  // Return score for winning, losing, or draw (Prefer early wins or late losses)
  if (winner)
    return winner === roles.player ? Score.Win - depth : Score.Lose + depth;
  if (!hasAvailableMove(board)) return Score.Draw;

  // Initialize bestScore and compare function
  // eslint-disable-next-line prefer-const
  let { isMaximizing, bestScore, compareFn } = getMinimaxContext(depth);

  // Iterate through available moves and calculate scores
  for (let i = 0; i < board.length; i++) {
    if (board[i].identifier === null) {
      const score = evaluateMove(
        board,
        winCondition,
        depth,
        i,
        roles,
        cutBounds,
      );
      bestScore = compareFn(score, bestScore);
      // 자식 노드 평가 결과를 알파/베타 값에 반영
      updateCutBounds(cutBounds, score, isMaximizing);
      // 현재 노드의 최적해를 찾았는지 검사하고, 찾았다면 자식 노드 탐색 중지
      if (cutBounds.alpha >= cutBounds.beta) break;
    }
  }

  return bestScore;
};

const findBestMove = (
  board: TBoard,
  winCondition: number,
  player: BasePlayer,
): number | null => {
  // 미니맥스 알고리즘은 일반적으로 최대화 단계부터 시작한다. 함수를 호출하면 최대화 단계가 시작된다
  // 최대화 단계에선 가장 큰 값을 찾기 위해 가장 작은 수(-Infinity)를 기본값으로 설정한다
  const bestOutcome: BestOutcome = { score: -Infinity, move: null };
  const cutBounds = { alpha: -Infinity, beta: Infinity }; // 알파/베타 초기값 설정

  const roles = { player, opponent: getOpponent(player) };
  const depth = 0; // 최대화 단계부터 시작

  for (let i = 0; i < board.length; i++) {
    if (board[i].identifier === null) {
      // 빈 칸을 현재 플레이어 기호로 채운 후 계산된 점수 중 가장 큰 곳의 인덱스를 bestMove 값으로 설정한다
      const score = evaluateMove(
        board,
        winCondition,
        depth,
        i,
        roles,
        cutBounds,
      );

      if (score > bestOutcome.score) {
        bestOutcome.score = score;
        bestOutcome.move = i;
        // 자식 노드 평가 결과를 알파/베타 값에 반영 (업데이트된 값을 자식 노드로 전달해야 하므로)
        updateCutBounds(cutBounds, score, true);
      }
    }
  }

  return bestOutcome.move;
};

 

1. 루트 노드에서 알파/베타 초기값($-\infin,\infin$)을 설정한다 (cutBounds 객체)
2. 초기값 혹은 3번에서 업데이트한 알파/베타 값을 자식 노드로 전달한다
   • 사이드 이펙트 방지를 위해 알파/베타 값이 담긴 cutBounds 객체를 복사해서 전달한다
   • cutBounds 객체의 불변성 유지는 각 노드에서 알파/베타 값을 로컬 변수로 관리함을 의미한다
3. 자식 노드 평가 결과를 알파/베타 값에 반영한다
   • 최대화 단계 : 현재 노드에서 발견된 최대 값(bestScore)을 알파 값으로 설정
   • 최소화 단계 : 현재 노드에서 발견된 최소 값(bestScore)을 베타 값으로 설정
4. 현재 노드의 최적해를 찾았는지 검사
   • $\alpha >= \beta$ 최적해를 찾은 상태 : 자식 노드 탐색을 중지한다 — 가지치기 ✂️
   • $\alpha < \beta$ 최적해를 찾지 못한 상태 : 2번으로 돌아가서 탐색 반복

 

헬퍼 함수 업데이트 ▼

// #3 자식 노드 평가 결과인 score를 인자로 받아 알파/베타 값 업데이트
const updateCutBounds = (
  cutBounds: CutBounds,
  score: number,
  isMaximizing: boolean,
) => {
  if (isMaximizing) cutBounds.alpha = Math.max(cutBounds.alpha, score);
  else cutBounds.beta = Math.min(cutBounds.beta, score);
};

const evaluateMove = (
  board: TBoard,
  winCondition: number,
  depth: number,
  lastIndex: number,
  roles: Roles,
  cutBounds: CutBounds, // 알파/베타 파라미터 추가
): number => {
  board[lastIndex].identifier = isMaximizing(depth)
    ? roles.player
    : roles.opponent;
  // #2 사이드 이펙트 방지를 위해 알파/베타 값이 담긴 cutBounds 객체의 불변성을 유지한다
  const score = minimax(board, winCondition, depth + 1, lastIndex, roles, {
    ...cutBounds,
  });
  board[lastIndex].identifier = null;

  return score;
};

 

메인 함수 업데이트 ▼

const minimax = (
  board: TBoard,
  winCondition: number,
  depth: number,
  lastIndex: number,
  roles: Roles,
  cutBounds: CutBounds, // 알파/베타 파라미터 추가
): number => {
  // ...생략

  let { isMaximizing, bestScore, compareFn } = getMinimaxContext(depth);

  for (let i = 0; i < board.length; i++) {
    if (board[i].identifier === null) {
      // #2 알파/베타 값 자식 노드로 전달
      const score = evaluateMove(
        board,
        winCondition,
        depth,
        i,
        roles,
        cutBounds,
      );
      bestScore = compareFn(score, bestScore);
      // #3 자식 노드 평가 결과를 알파/베타 값에 반영
      updateCutBounds(cutBounds, score, isMaximizing);
      // #4 현재 노드의 최적해를 찾았는지 검사하고, 찾았다면 자식 노드 탐색 중지
      if (cutBounds.alpha >= cutBounds.beta) break;
    }
  }

  return bestScore;
};

const findBestMove = (
  board: TBoard,
  winCondition: number,
  player: BasePlayer,
) => {
  // ...생략

  // #1 알파/베타 초기값 설정
  const cutBounds = { alpha: -Infinity, beta: Infinity };

  for (let i = 0; i < board.length; i++) {
    if (board[i].identifier === null) {
      // #2 초기값 혹은 3번에서 업데이트한 알파/베타 값을 자식 노드로 전달
      const score = evaluateMove(
        board,
        winCondition,
        depth,
        i,
        roles,
        cutBounds,
      );

      if (score > bestOutcome.score) {
        bestOutcome.score = score;
        bestOutcome.move = i;
        // #3 자식 노드 평가 결과를 알파/베타 값에 반영 (업데이트된 값을 자식 노드로 전달해야 하므로)
        updateCutBounds(cutBounds, score, true);
      }
    }
  }

  return bestOutcome.move;
};

 

시간복잡도

미니맥스 알고리즘에 알파-베타 가지치기 기법을 적용하면, 더 이상 탐색할 필요가 없는 노드를 조기에 제외함으로써 시간 복잡도를 $O(b^{d/2})$까지 줄일 수 있다(최적의 경우). 특히 트리 깊이가 깊어질수록 알파-베타 가지치기 효과가 배가돼서 탐색 시간을 크게 단축시킬 수 있다.

 

하지만 체스나 바둑 같은 상태 공간이 매우 큰 게임에선 가능한 모든 상태를 탐색하는 것은 실질적으로 불가능하다. 이런 복잡한 게임에선 특정 깊이에 도달했을 때 탐색을 중단하고, 휴리스틱 평가 기법을 활용하여 현재 게임 상태의 추정치를 계산하는 방식으로 최적화해야 한다. 틱택토를 예로 들면…

 

• 중앙, 모서리 등에 높은 점수 부여
• 연속된 기호가 있는 곳에 높은 점수 부여
• 상대방의 승리를 방어하는 곳에 높은 점수 부여
• 등…

 

 

메모이제이션

---

틱택토 게임을 하다 보면 각 플레이어가 서로 다른 순서로 기호를 뒀음에도 불구하고 최종적으로 같은 보드 상태에 도달하는 경우가 자주 있다(아래 이미지 참고). 특히 미니맥스 알고리즘은 가능한 모든 수를 탐색하기 때문에 이미 평가했던 보드 상태를 다시 평가하는 경우가 자주 발생한다. 만약 이미 계산했던 보드 상태를 저장해 두고 재사용하면 중복 평가를 줄일 수 있기 때문에 알고리즘 효율을 크게 향상할 수 있다.

 

 

• 경로 A : X 중앙 → O 좌측 상단 → X 우측 하단
• 경로 B : X 우측 하단 → O 좌측 상단 → X 중앙

 

현재 보드 상태를 문자열로 변환하는 유틸 함수 ▼

const generateBoardKey = (board: TBoard, depth: number): string => {
  return `${board.map(({ identifier }) => identifier ?? '-').join('')}:${depth}`;
};

 

기존 함수 수정 ▼

const findBestMove = (
  board: TBoard,
  winCondition: number,
  player: BasePlayer,
) => {
  // ...생략
  const memo: Memo = new Map(); // 메모이제이션 객체 초기화 Map<string, number>

  for (let i = 0; i < board.length; i++) {
    if (board[i].identifier === null) {
      const score = evaluateMove(
        board,
        winCondition,
        depth,
        i,
        roles,
        cutBounds,
        memo,
      );
      // ... 생략
    }
  }

  return bestOutcome.move;
};

const evaluateMove = (
  board: TBoard,
  winCondition: number,
  depth: number,
  lastIndex: number,
  roles: Roles,
  cutBounds: CutBounds,
  memo: Memo, // 파라미터 추가
): number => {
  // ...생략
  const score = minimax(
    board,
    winCondition,
    depth + 1,
    lastIndex,
    roles,
    { ...cutBounds },
    memo,
  );
  // ...생략
};

const minimax = (
  board: TBoard,
  winCondition: number,
  depth: number,
  lastIndex: number,
  roles: Roles,
  cutBounds: CutBounds,
  memo: Memo, // 파라미터 추가
): number => {
  const key = generateBoardKey(board, depth); // 보드 상태와 depth를 기준으로 유니크 key 생성
  if (memo.has(key)) return memo.get(key)!; // 이미 평가한 보드 상태라면 해당 점수 반환
  // ... 생략

  for (let i = 0; i < board.length; i++) {
    if (board[i].identifier === null) {
      /* ...생략 */
    }
  }

  memo.set(key, bestScore); // 현재 보드 상태의 bestScore 저장
  return bestScore;
};

 

4x4 빈 보드에 Bot이 먼저 첫 번째 수를 둔다고 가정하고, 메모이제이션 적용 전/후 알고리즘 실행 시간은 아래와 같다. 메모이제이션을 적용하면 실행 시간을 약 72배가량 줄일 수 있다. 생각보다 엄청난 차이.

 

• 메모이제이션 전 : 159,853 milliseconds (약 159.8초)
• 메모이제이션 후 : 2,209 milliseconds (약 2.2초)

 

 

레퍼런스

---

• Tic Tac Toe: Understanding the Minimax Algorithm | Never Stop Building
• Tic-Tac-Toe with JavaScript: AI Player with Minimax Algorithm | Ali Alaa
• Artificial Intelligence | Alpha-Beta Pruning - Javatpoint
• Adversarial Search - Minimax Search와 Alpha-beta Pruning | 지그시

 

 

완성 레포지토리

---

GitHub - romantech/tic-tac-toe: Customizable Tic-Tac-Toe game with React

 

---

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요