미니맥스 알고리즘

개념

<aside> <img src="/icons/search_gray.svg" alt="/icons/search_gray.svg" width="40px" /> 제로섬 게임은 한 플레이어가 이득을 얻으면 다른 플레이어는 그만큼 손해를 보는 게임을 가리킨다

</aside>

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

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

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

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

구현

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

</aside>

🔍 evaluateWinning 함수 구현

미니맥스 알고리즘은 기본적으로 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;
};