미니맥스 알고리즘, 알파-베타 가지치기

작고 귀여운 머리로 오목 규칙이랑 로직 생각하다가... 1차로 위와 같이 여러 조건을 생각해서 만들었다. 이것이 단일 단계 평가(1-Ply Evaluation)라고 한다.

이것도 재밌긴 했는데, 문제는 컴퓨터가 다채로운 방식으로 게임을 하진 못했다. 무슨 문제가 있었냐면..

1. 공격과 방어를 적절히 섞어서 수를 둬야 하는데 그렇지 못함(공격만, 방어만 주구장창 한다던가)
2. 상대의 대응(즉, 나의 대응)에 예측하지 못함
3. 대각선에 약함

이렇듯 단순하게 로직을 작성한다면 상대가 둘 미래의 수를 보지 못하고, 함정에 속수무책이라고 한다. 

그래서 이를 보완하기 위해 2-ply 이상 탐색, 즉 미니맥스 알고리즘으로 확장해서 작성했다.

로직을 작성하기 위해선 우선 미니맥스 알고리즘을 알아야 했다..

---

미니맥스 알고리즘(Minimax Algorithm)

나는 최선을 다하고, 상대도 최선을 다한다고 가정했을 때, 최종적으로 내가 가장 유리한 결과를 얻을 수 있는 수를 찾는 알고리즘

내가 가장 잘 이기게 두고, 상대는 나를 가장 못이기게 둔다는 가정으로 가능한 수를 시뮬레이션해서 최선을 수를 찾는다. 

저런식으로 컴퓨터 - 사람 플레이어 간 최선의 수를 찾기 위해 번갈아가면서 실행한다.

 

miniMax()함수로 구현

두명의 플레이어가 완벽히 플레이한다고 가정헀을 때, 지금 어떤 수를 두면 가장 유리할지 계산해주는 역할을 한다.

• Max(우리 차례) : 점수를 최대한 높이려는 플레이어
• Min(상대 차례) : 점수를 최대한 낮추려는 플레이어

그래서 miniMax()함수는 두가지의 일을 번갈아 가면서 하게 된다.

• 우리 차례라면 : 가장 높은 점수를 선택(이기기 위해)
• 상대 차례라면 : 가장 낮은 점수를 선택(우리를 불리하게 만들기 위해)

Ex : 틱택토 게임

다음과 같은 선택지가 다음과 같다고 하자.

A : 이기는 수 : 점수 +10

B : 비기는 수 : 점수 0

C : 지는 수 : 점수 - 10

 

이런 상황에서 miniMax()는 

내가 지금 둔 다음, 상대도 최선을 다할거야. 그럼 각 경우마다 결과가 어떻게 될까?

 

라고 생각하게 된다. 

 

구성

miniMax(board, depth, isMaximizing)

1. board : 현재 게임 상태
2. depth : 얼마나 깊이 계산할지(미래 수의 단계)
3. isMaximizing : 지금 "우리 턴"인지 "상대 턴"인지

순서 

1. 기저 조건(Base Case) : 게임이 끝났다면 그 점수를 반환한다. 승패가 정해지건, 더 둘 곳이 없을 때를 위한 종료 조건을 작성
2. 재귀 호출(Recursive Call) : 게임이 끝나지 않았다면 가능한 모든 수를 보고 그 결과를 miniMax()로 다시 호출하여 계산한다.
3. 최댓값/최솟값 선택 : 우리 턴이면 "가장 큰 값", 상대 턴이면 "가장 작은 값"을 선택한다.

function miniMax(board, depth, isMaximizing) {
  // 1단계: 종료 조건 (기저 조건)
  if (depth === 0 || 게임이끝났다면) {
    return 현재상태의점수  // 평가 함수 호출
  }

  // 2단계: Max 플레이어 턴
  if (isMaximizing) {
    let maxScore = -Infinity  // 가장 작은 값으로 시작
    
    for (가능한모든수) {
      // 가상으로 수를 둠
      수를둔다(board, 수)
      
      // 재귀: 상대방 턴으로 넘김
      let score = miniMax(board, depth - 1, false)
      
      // 수를 되돌림
      수를취소한다(board, 수)
      
      // 최댓값 갱신
      maxScore = Math.max(maxScore, score)
    }
    
    return maxScore
  }
  
  // 3단계: Min 플레이어 턴
  else {
    let minScore = Infinity  // 가장 큰 값으로 시작
    
    for (가능한모든수) {
      // 가상으로 수를 둠
      수를둔다(board, 수)
      
      // 재귀: 상대방 턴으로 넘김
      let score = miniMax(board, depth - 1, true)
      
      // 수를 되돌림
      수를취소한다(board, 수)
      
      // 최솟값 갱신
      minScore = Math.min(minScore, score)
    }
    
    return minScore
  }
}

 

 

최대한 이해하기 쉽게끔 작성은 했는데... 한계가 있어서 AI에게 보충 설명을 부탁했다. 

 

➡️ 수를 취소하는 이유?

미니맥스는 "만약 이렇게 두면 어떨까?"라고 미리 예측하는 것이기 때문에

가상으로 두고 →

점수를 계산하고 →

다시 돌을 없앤다.

 

올바른 진행 예시

현재 보드:
⚫ ⚪  _   _   _
 _     _   _   _   _
 _     _   _   _   _

라고 뒀다 쳤을 때

 

0. 현재 상태
board[0][2] = null  // 빈칸

// 1. 수를둔다(board, {x:0, y:2})
board[0][2] = '⚫'  // 가상으로 검은돌 두기
⚫ ⚪ ⚫ _ _  // 이렇게 됨
 _     _    _  _ _
 _     _    _  _ _

2. 이 상태로 재귀 호출
let score = miniMax(board, ...)  // 이 상태에서의 점수 계산 → 다시 호출해서 상대 턴으로 넘김

3. 수를취소한다(board, {x:0, y:2})
board[0][2] = null  // 다시 원래대로
⚫ ⚪ _ _ _  // 원상복구!
 _    _   _ _ _
 _    _   _ _ _

다음 칸 시뮬레이션 계속...

---

❌ 취소 안 하면 어떻게 될까?

1. 1번째 반복 - A칸 시뮬레이션

board[0][2] = '⚫'  // A칸에 둠

보드 상태:
⚫ ⚪ ⚫ _ _  <- A칸에 돌 생김

scoreA = miniMax(board, ...)  // 이 상태로 점수 계산

 

2. 2번째 반복 - B칸 시뮬레이션

board[0][3] = '⚫'  // B칸에 둠

 

예상했던 보드 상태 :

'⚫' ⚫ ⚪ _ ⚫ _ <- A칸은 없고 B칸만 있음! ✅

현실 보드 상태:
⚫ ⚪ ⚫ ⚫ _  <- A칸 돌이 아직 있음! + B칸 돌 추가됨!

scoreB = miniMax(board, ...)  // 잘못된 상태로 점수 계산!

 

3. 3번째 반복 - C칸 시뮬레이션

board[1][0] = '⚫'  // C칸에 둠

 

예상했던 보드 상태 :

'⚫' ⚫ ⚪ _ _ _ <- A칸, B칸은 없고

⚫ _ _ _ _ <- C칸만 있음! ✅

현실 보드 상태:
⚫ ⚪ ⚫ ⚫ _  <- A칸, B칸 돌이 모두 남아있음!
⚫ _ _ _ _  <- C칸 돌 추가됨!

scoreC = miniMax(board, ...)  // 완전히 잘못된 상태!

 

우리가 원하는 것은 

 

"A칸 하나만 뒀을 때" 점수는?
"B칸 하나만 뒀을 때" 점수는?
"C칸 하나만 뒀을 때" 점수는?

 

인데, 실제로는

"A칸 하나만 뒀을 때" 점수는? ✅ 정확
"A+B 칸 둘 다 뒀을 때" 점수는? ❌ 잘못됨!
"A+B+C 칸 셋 다 뒀을 때" 점수는? ❌ 잘못됨!

 

따라서 미니맥스 알고리즘은 각 반복(Iteration)마다 다음 2가지 중 하나를 수행해야 한다.

• 상태 복사 후 변경 (Deep Clone): 탐색을 위한 새로운 보드를 만들고(복사), 여기에 돌을 둡니다. 
• 상태 변경 후 복구 (Undo/Redo): 원본 보드에 돌을 두었다가, 재귀 호출이 끝난 후 반드시 돌을 다시 빼냅니다. (메모리 사용이 효율적인 방식)

➡️ 수를 취소하는 방법

핵심 개념 — 왜 반드시 원상복구해야 하나?

미니맥스는 “각 후보(칸) 별로 독립적인 결과”를 알기 위함
따라서 각 후보를 시뮬레이션할 때 보드 상태는 그 후보만 반영된 상태여야 한다.
돌을 두고 재귀 계산한 뒤 돌을 다시 제거하지 않으면 다음 후보를 시뮬레이션할 때 이전 후보의 변경이 남아 있어 결과가 뒤섞여 버린다.

예) A 칸 시뮬레이션 후 A를 제거하지 않으면 B 시뮬레이션은 A+B가 놓인 상태를 보고 계산한다 → 잘못된 결과.

---

구현 방법 — 두 가지 일반적 패턴

방법 A — 불변(immutable) 방식: 매 시뮬레이션마다 새 배열/보드를 만들어 재귀에 넘긴다

 

장점: 코드가 안전하고 버그가 덜 남. React 스타일과도 어울림.
단점: 복사 비용(메모리·속도)이 발생할 수 있음(특히 깊게/많이 복사하면).

// stones: {x,y,color}[] 형태일 때 

for (const {x,y} of possibleMoves) { 
  const newStones = [...currentStones, { x, y, color: 'black' as const }]
  const val = miniMax(newStones, depth - 1, alpha, beta, false) // 비교/갱신
}

// 이 방식은 board나 stone 원본을 절대 직접 변경하지 않으므로 undo가 필요 없음.

---

방법 B — 가변(mutable) 방식: 보드(2D 배열)를 직접 수정하고 재귀 끝난 뒤 되돌리기(undo)

 

장점: 메모리/속도 효율이 높음(복사 비용 없음).
단점: 반드시 “되돌리기”를 정확히 해야 하고, 실수하면 이전 상태가 오염됨.

 

// board: string | null[][] (2D 배열) 일 때 

function tryMoveAndEval(board, x, y, color, depth, alpha, beta, isMax) { 
  board[x][y] = color // 1) 가상으로 두기 
  const val = miniMax(board, depth - 1, alpha, beta, !isMax) // 2) 재귀 
  board[x][y] = null // 3) 반드시 되돌리기! 
  return val 
}

//이 패턴이 “두고 → 계산 → 취소”와 정확히 일치한다.

---

실전 팁 

1. 절대 setStone 같은 React 상태 업데이트를 미니맥스 내부에서 호출하지 말 것
   -> 재귀 안에서는 로컬(임시) 변수나 복사본/2D board를 써라. setState는 비동기이고 UI와 섞이면 엉킴
2. 키 포맷이나 Map/Set 사용 시 포맷 통일 ("${x},${y}" 처럼). 포맷 불일치는 치명적 버그를 낳음.
3. 성능: 많이 복사하면 느려지니 깊이와 후보 수(ex. 오목에서 수를 찾는 함수)를 적절히 제한하거나, mutable + undo 방식으로 최적화하자.
4. 디버깅:
   • 시뮬레이션 직후 console.log로 보드 상태 찍어보고, 재귀 반환 후 동일한 상태로 돌아왔는지 확인하라.
   • 예상과 다른 값(누적된 돌)이 나오면 “되돌리기 누락”부터 점검.

---

언제 mutable + undo가 더 좋은가?

• 후보가 많고 재귀 호출이 폭발할 때(성능 제한이 심한 상황), 보드 2D 배열 + 가변/undo 방식이 훨씬 빠름.
• 구현은 조금 더 까다롭지만, 대규모 탐색(깊이 3~4 이상)에서는 권장됨.

---

결론

• 해결 방법은 (A) 불변으로 새 보드/배열 만들어 넘기기 또는 (B) 가변 보드에 두고 재귀 끝나면 되돌리기.
• React 환경에서는 미니맥스 내부에선 setState 쓰지 말고 로컬 복사나 mutable-undo를 사용할 것.

그런데 미니맥스는 모든 경우의 수를 계산하기 때문에 필요하지 않은 경우의 수는 생략해야 성능이 향상된다.

그럴 때 사용하는 것이 알파-베타 가지치기이다!

알파 - 베타 가지치기(Alpha-beta pruning)

미니맥스에서 계산하는 과정 중 "이 경로로는 어차피 최선에 못미치니까 계산하지 말자"고 쓸데 없는 가지를 잘라내는 기술이다. 

컴퓨터(Max) 턴: "최소 10점은 보장받고 싶어!"
     |
     ├── 수A를 두면 → 사람이 뭘 해도 최소 10점
     |
     └── 수B를 살펴보는 중...
          └── 사람이 첫 번째 수를 두니 5점이 나옴
              → "아, 수B는 최대 5점이네?"
              → "이미 수A로 10점 보장받았으니 수B는 볼 필요 없어!"
              ✂️ 가지치기!

https://hello-kk.tistory.com/580

알파베타 가지치기 Alpha-beta pruning 설명

알고리즘 원리는 사실 내 설명보단 이 블로그 설명글 보는게 이해가 더 빠르다. 

그래서 내가 궁금했던 것 위주로 정리하였다.

 

1️⃣ 왜 max는 -∞에서, min은 ∞에서 시작할까?

Max(컴퓨터)는 "가능한 큰 점수"를 찾는 역할이기 때문에 시작값을 -∞로 둬야 한다 → 어떤 실제 숫자를 만나도 "그건 지금보다 크다"고 갱신할 수 있음

Min(상대, 사람)은 "가능한 작은 점수"를 찾는 역할이기 때문에 시작값을 +∞로 둬야 한다 → 어떤 실제 숫자를 만나도 "그건 지금보다 작다"고 갱신할 수 있음

 

➡️Max는 최솟값에서 출발해서 점점 더 좋은(큰)걸 찾고, Min은 최댓값에서 출발해서 점점 더 나쁜(작은)것을 찾는다.

➡️처음에는 아무 지식도 없기 때문에 무량대수값을 둔다.

 

알파 - 베타 가지치기 예시(코드로 보기)

1. Max 차례의 경우

let maxEval = -Infinity
for (let child of children) {
  const eval = miniMax(child, depth - 1, alpha, beta, false)
  maxEval = Math.max(maxEval, eval)
  if (beta <= alpha) break // 가지치기
}

첫번째 자식이 3이면 : maxEval = max(- ∞, 3) = 3

두번째 자식이 7이면 : maxEval = max(3, 7) = 7

세번째 자식이 2이면 : maxEval = max(7, 2) = 7

...

즉 계속 큰값으로 업데이트하면서 최댓값을 찾아간다.

 

2. Min 차례의 경우

let minEval = Infinity
for (let child of children) {
  const eval = miniMax(child, depth -1, alpha, beta, true)
  minEval = Math.min(minEval, eval)
  if (beta <= alpha) break // 가지치기
}

첫번째 자식이 5면 : minEval = min(∞, 5) = 5

두번째 자식이 2이면 : minEval = min(5, 2) = 2

세번째 자식이 8이면 : minEval = min(2, 8) = 2

...

즉 계속 작은 값으로 최솟값을 업데이트한다.

 

3. 의사 코드

function alphabeta(node, depth, α, β, maximizingPlayer)
     if depth = 0 or node is a terminal node
         return the heuristic value of node
     if maximizingPlayer
         v := -∞
         for each child of node
             v := max(v, alphabeta(child, depth - 1, α, β, FALSE))
             α := max(α, v)
             if β ≤ α
                 break (* β cut-off *)
         return v
     else
         v := ∞
         for each child of node
             v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
             β := min(β, v)
             if β ≤ α
                 break (* α cut-off *)
         return v

 

 

 

 

---

[참고 자료]

https://hello-kk.tistory.com/580

알파베타 가지치기 Alpha-beta pruning 설명

https://lordofkangs.tistory.com/205

[인공지능] 게임트리 ( 알파베타 가지치기 )

https://ssollacc.tistory.com/43

[인공지능] 게임 트리 - 미니맥스(minimax) 알고리즘, 알파베타 가지치기, 휴리스틱 평가 함수(evaluat

https://ko.wikipedia.org/wiki/%EC%95%8C%ED%8C%8C-%EB%B2%A0%ED%83%80_%EA%B0%80%EC%A7%80%EC%B9%98%EA%B8%B0

알파-베타 가지치기 - 위키백과, 우리 모두의 백과사전