Minimax 게임 AI 시각화
Minimax 알고리즘과 알파-베타 가지치기를 틱택토 게임 트리로 학습합니다
게임 AI★★☆
속도
1 / 1💡 빈칸이 많아 트리가 매우 커집니다. 보드에 말을 3~4개 이상 놓은 후 실행하면 더 깔끔한 트리를 볼 수 있습니다.
클릭하여 말 놓기
다음:X
프리셋 보드
최대화 (MAX)최소화 (MIN)가지치기됨종단 노드최적 경로
👆
시작 전
보드에 말을 놓고 ▶ 재생 버튼을 누르세요
노드 확장: 깊이 {depth}
종단 평가: 점수 = {score}
점수 전파: {score} (α={alpha}, β={beta})
가지치기! β({beta}) ≤ α({alpha})
게임 트리가 어떻게 탐색되고 점수가 전파되는지 관찰하세요.
Minimax 알고리즘이란?
Minimax는 두 플레이어 제로섬 게임에서 최적의 전략을 찾는 알고리즘입니다. 한 플레이어(MAX)는 점수를 최대화하고, 상대(MIN)는 최소화하려 합니다. 알파-베타 가지치기를 추가하면 결과에 영향을 주지 않는 가지를 잘라내어 탐색 속도를 크게 높입니다.
사용 방법
- 1보드를 클릭하여 X와 O를 번갈아 놓으세요 (초기 상태 설정)
- 2또는 프리셋 버튼으로 빈/중반/종반 상태를 선택하세요
- 3알파-베타 가지치기를 켜고 끄며 차이를 비교하세요
- 4재생 버튼으로 게임 트리가 생성되는 과정을 관찰하세요
- 5주황색 노드는 MAX(최대화), 파란색은 MIN(최소화)입니다
동작 원리
- 1게임 상태를 트리로 표현: 각 노드는 보드 상태, 엣지는 가능한 수
- 2최대화 플레이어(MAX)는 점수를 최대화하는 수를 선택, 최소화 플레이어(MIN)는 점수를 최소화
- 3리프 노드(게임 종료 상태)에서 승/패/무 점수를 평가
- 4점수를 부모 노드로 역전파: MAX 노드는 자식 중 최댓값, MIN 노드는 최솟값 선택
- 5알파-베타 가지치기: α(MAX가 보장한 최소 점수) ≥ β(MIN이 보장한 최대 점수)이면 나머지 자식 탐색 생략
실무 활용
- •체스/바둑 AI — Deep Blue(IBM), AlphaGo의 탐색 기반. 실제로는 MCTS와 결합
- •보드게임 앱(오셀로, 체커, 커넥트4)의 AI 상대
- •카드 게임 AI(포커, 하츠) — 불완전 정보 게임에도 변형 적용
- •경제학의 게임 이론 — 전략적 의사결정 모델링(제로섬 게임)
- •자동 협상 시스템 — 최적 제안/수락 전략 결정
비슷한 알고리즘
- •MCTS(Monte Carlo Tree Search) — 랜덤 시뮬레이션으로 유망한 수를 통계적으로 평가. AlphaGo가 사용. Minimax보다 큰 게임(바둑)에 적합
- •Negamax — Minimax의 단순화 버전. MAX/MIN 구분 없이 점수를 부호 반전하여 항상 최대화. 구현이 간결
- •기대값 Minimax(Expectiminimax) — 확률 요소(주사위, 카드)가 있는 게임에 확장. 확률 노드 추가
학습 팁
- •빈 보드에서 알파-베타 ON/OFF 시 노드 수 차이를 비교해보세요
- •종반 상태에서는 트리가 작아 전체 과정을 쉽게 추적할 수 있습니다
- •가지치기된 노드(회색)는 탐색하지 않아도 결과가 바뀌지 않는 경우입니다
- •MAX 노드에서는 자식 중 가장 높은 점수를, MIN 노드에서는 가장 낮은 점수를 선택합니다
자주 묻는 질문
Q. Minimax는 어떤 게임에 사용되나요?
A. 체스, 바둑, 오목, 체커 등 모든 2인 완전정보 제로섬 게임에 사용됩니다. 이 사이트의 오목·오셀로·사목 AI도 Minimax 기반입니다.
Q. 알파-베타 가지치기는 결과에 영향을 주나요?
A. 아닙니다. 가지치기는 탐색 속도만 높이며, 최종 결과(최적 수)는 동일합니다. 불필요한 가지를 건너뛰는 것입니다.
Q. 틱택토에서 최적 전략은?
A. 양쪽 모두 최적으로 두면 항상 무승부입니다. Minimax는 이를 증명합니다 — 루트 점수가 0(무승부)이 됩니다.