미니맥스(Minimax) 알고리즘은 두 플레이어 게임에서 자신의 이득을 극대화하고 상대방의 이득을 최소화하는 최적 전략을 찾는 알고리즘이다. 체스, 바둑, 틱택토 등 게임 AI의 기반이다.
동작 원리
MAX 플레이어: 자신에게 유리한 최대값 선택
MIN 플레이어: 상대에게 불리한 최소값 선택
MAX
/ \
MIN MIN
/ \ / \
3 5 2 9
MAX에서 보면:
MIN 왼쪽: min(3,5) = 3
MIN 오른쪽: min(2,9) = 2
MAX: max(3,2) = 3 → 왼쪽 선택
구현 (틱택토)
python
def minimax(board, depth, is_maximizing):
score = evaluate(board)
if score != 0 or is_full(board):
return score
if is_maximizing:
best = -float('inf')
for move in get_moves(board):
make_move(board, move, 'X')
best = max(best, minimax(board, depth+1, False))
undo_move(board, move)
return best
else:
best = float('inf')
for move in get_moves(board):
make_move(board, move, 'O')
best = min(best, minimax(board, depth+1, True))
undo_move(board, move)
return best
알파-베타 가지치기
미니맥스의 최적화: 최적해에 영향을 줄 수 없는 브랜치 조기 종료.
탐색 노드 수: O(b^d) → O(b^(d/2)) (약 제곱근 감소)
관련 개념
참고문헌
- •Russell & Norvig. Artificial Intelligence: A Modern Approach — Chapter 5
