핵심 요약
게임은 상대방의 전략이 미지수인 환경에서의 의사결정 문제이며, Minimax 원칙을 통해 최악의 상황에서도 안정적인 결과를 보장하는 전략을 수립할 수 있다. Alpha-Beta Pruning과 평가 함수를 결합하면 거대한 탐색 공간에서도 효율적인 의사결정이 가능하다.
배경
스탠포드 대학교의 CS221 인공지능 강의 시리즈 중 열 번째 세션으로, 에이전트 단독의 의사결정(MDP)을 넘어 경쟁자가 존재하는 게임 환경을 다룬다.
대상 독자
인공지능 알고리즘과 게임 이론의 수학적 모델링에 관심 있는 학생 및 개발자
의미 / 영향
이 강의는 경쟁적 환경에서 작동하는 AI 에이전트의 핵심 설계 원리를 제공한다. Minimax와 Alpha-Beta Pruning은 체스나 바둑 같은 고전 게임뿐만 아니라 자원 경쟁이나 보안 전략 수립 등 다양한 실무 분야의 의사결정 최적화에 적용될 수 있다. 특히 계산 자원이 제한된 환경에서 대규모 탐색 공간을 효율적으로 다루는 방법론은 현대 AI 시스템의 성능 개선에 필수적인 통찰을 제공한다.
챕터별 상세
게임 모델링과 게임 트리의 기초
- •게임 트리의 각 노드는 특정 플레이어의 턴을 나타냄
- •루트에서 리프까지의 경로는 하나의 게임 시나리오(Outcome)임
- •상대방의 전략은 미지수이며 에이전트는 이에 대응해야 함
제로섬 게임과 효용의 정의
- •에이전트 효용 = -상대방 효용의 관계 성립
- •보상은 게임이 종료되는 시점에만 주어지는 Sparse Reward 구조임
- •플레이어들은 각자의 상태에서 자신의 효용을 최대화하려 함
게임 평가와 재귀적 가치 계산
- •고정된 정책 하에서 게임 가치는 기대 효용의 합임
- •재귀 함수를 통해 리프 노드부터 루트까지 가치를 전달함
- •MDP의 Policy Evaluation과 수학적으로 동일한 구조를 가짐
def V_eval(game, policies, state):
if game.is_end(state):
return game.utility(state)
player = game.player(state)
policy = policies[player]
value = 0
for action, prob in policy(state).items():
next_state = game.successors(state)[action]
value += prob * V_eval(game, policies, next_state)
return value고정된 정책을 가진 두 플레이어의 게임 가치를 재귀적으로 계산하는 함수 예시
Expectimax: 고정된 상대에 대한 최적 전략
- •에이전트는 Max 노드, 상대방은 Chance 노드로 모델링됨
- •상대방의 정책을 알고 있을 때 기대 효용을 최대화함
- •MDP의 Value Iteration과 유사한 방식으로 최적 정책을 도출함
Minimax: 최악의 상대를 가정한 의사결정
- •상대방이 에이전트의 효용을 최소화하려 한다고 가정함
- •Max 노드와 Min 노드가 번갈아 나타나는 재귀 구조임
- •상대방의 전략에 관계없이 보장되는 최악의 경우의 이득을 계산함
def V_minimax(game, state):
if game.is_end(state):
return game.utility(state), None
player = game.player(state)
successors = game.successors(state)
values = [(V_minimax(game, next_state)[0], action) for action, next_state in successors.items()]
if player == "agent":
return max(values)
else:
return min(values)상대방의 최적 대응을 가정하여 에이전트의 최적 행동과 가치를 계산하는 Minimax 재귀 함수
Alpha-Beta Pruning을 이용한 탐색 최적화
- •Alpha(하한)와 Beta(상한) 범위를 유지하며 불필요한 노드 제거
- •탐색 결과는 원래의 Minimax와 동일하지만 계산량은 대폭 감소함
- •노드 방문 순서가 가지치기 성능에 결정적인 영향을 미침
평가 함수와 깊이 제한 탐색
- •정해진 깊이까지만 탐색하고 리프 대신 평가 함수를 사용함
- •평가 함수는 상태의 가치를 추정하는 휴리스틱임
- •탐색 깊이와 평가 함수의 정확도 사이에는 트레이드오프가 존재함
실무 Takeaway
- 상대방의 전략을 모를 때는 Minimax 원칙을 적용하여 최악의 상황에서도 보장되는 최소 이득(Lower bound)을 확보하는 것이 안전하다.
- Alpha-Beta Pruning을 적용할 때 탐색 효율을 높이려면 가치가 높을 것으로 예상되는 행동을 먼저 탐색하도록 순서를 정하는 것이 중요하다.
- 실제 복잡한 게임 시스템에서는 전체 트리를 탐색하는 대신 깊이를 제한하고 도메인 지식이 반영된 평가 함수를 결합하여 실시간 의사결정을 수행한다.
- 상대방의 약점이나 특정 패턴을 알고 있다면 Minimax보다 Expectimax를 사용하여 더 높은 효용을 얻을 수 있다.
AI 요약 · 북마크 · 개인 피드 설정 — 무료
출처 · 인용 안내
인용 시 "요약 출처: AI Trends (aitrends.kr)"를 표기하고, 사실 확인은 원문 보기 기준으로 진행해 주세요. 자세한 기준은 운영 정책을 참고해 주세요.