Tic Tac Toe 게임- 미니맥스(Minimax) 알고리즘

 

⬇️게임 실행하기⬇️

https://game-steel-beta.vercel.app/

Tic Tac Toe

 

 

https://github.com/veryyounng/game/tree/08c0447c213be78d0a3d4ffe838b16104c517cdb

GitHub - veryyounng/game

 

📌 개요

"인공지능은 어떻게 틱택토에서 최선의 수를 두는 걸까?"

이 글에서는 게임 이론에 기반한 Minimax 알고리즘의 원리와,
틱택토에 적용된 수학적 사고방식을 분석하였다.

 

🎯 1. 미니맥스란 무엇인가?

🔹 정의

Minimax는 두 명의 플레이어가 번갈아가며 승패를 겨루는 게임에서,
상대가 항상 최선의 수를 둔다고 가정하고
→ 자신에게 최선의 수를 고르는 결정 알고리즘이다.

🔹 게임 이론 배경

• 게임 이론(Game Theory)은 수학적으로 전략을 분석하는 학문
• Minimax는 Zero-Sum Game (제로섬 게임)을 전제로 함:
  한 쪽이 이득을 보면, 다른 쪽은 반드시 손해를 본다
• 목적: 자신의 최악의 경우에도 가장 덜 손해보는 선택

🧮 2. 수학적 원리: 트리 탐색과 백트래킹

틱택토 게임은 모든 수의 조합을 트리(Tree) 구조로 표현가능

        [현재 상태]
        /     |     \
  [상대 수1] [상대 수2] ...
    /       |        \
[내 다음 수1] ...

• Leaf Node (말을 다 둔 상태)에서는 승/패/무 결과가 정해진다.
• Minimax는 이 모든 경우를 재귀적으로 탐색해서,
  각 노드에서의 최선의 선택값을 위로 전달(backtrack) 한다.

✨ 핵심:
MAX: 내가 둘 차례 → 최대의 값을 선택
MIN: 상대 차례 → 내 점수를 최소화시키는 수를 선택
그래서 Minimax!

 

🔍 3. 수식으로 표현

각 상태 sss에서의 점수 V(s)V(s)V(s)는 다음과 같이 정의:

• 내 차례일 때 (MAX player):

V(s) = \max_{a \in A(s)} V(\text{Result}(s, a))

• 상대 차례일 때 (MIN player):

V(s) = \min_{a \in A(s)} V(\text{Result}(s, a))

 

여기서,

• A(s)A(s)A(s): 상태 sss에서 가능한 모든 액션 집합
• Result(s,a)Result(s, a)Result(s,a): 액션 aaa를 취한 뒤의 상태
• Leaf 노드일 경우 V(s)=승패 점수V(s) = \text{승패 점수}V(s)=승패 점수로 직접 반환 (예: 승: 1, 무: 0, 패: -1)

 

🧠 4. 틱택토에 적용할 때 고려사항

• 게임 상태 수가 많지 않기 때문에, 완전탐색(Brute-force)이 가능
• 무승부가 최선일 수 있음 (이기는 수가 없을 경우)
• 가지치기(Pruning) 없이도 실시간에 충분한 성능
  (→ 향후 알파-베타 가지치기(Alpha-Beta Pruning)로 최적화 가능)

 

🧑‍💻 6. 실제 코드에서의 적용 (핵심 요약)

function minimax(board, isMaximizing) {
  if (isGameOver(board)) return score(board)

  const scores = []
  for (let move of getAvailableMoves(board)) {
    const newBoard = makeMove(board, move, isMaximizing ? 'X' : 'O')
    const result = minimax(newBoard, !isMaximizing)
    scores.push(result)
  }

  return isMaximizing ? Math.max(...scores) : Math.min(...scores)
}