챕터별 상세
00:00
게임 모델링과 게임 트리의 기초
게임은 에이전트가 효용을 최대화하려 하지만 환경에 상대방(Opponent)이 존재하여 그 전략을 알 수 없는 상태 공간 모델이다. 게임 트리는 각 노드를 플레이어의 결정 지점으로, 에지를 가능한 행동으로 정의하며 루트에서 리프까지의 경로는 게임의 가능한 결과를 나타낸다. MDP와 달리 환경의 전이가 랜덤이 아닌 상대방의 의도에 의해 결정된다는 점이 핵심 차이점이다.
04:18
제로섬 게임과 효용의 정의
두 플레이어 제로섬 게임(Two-player Zero-sum Games)은 에이전트의 효용과 상대방의 효용의 합이 항상 0이 되는 구조이다. 이는 에이전트가 얻는 이득이 곧 상대방의 손실임을 의미하며, 수학적으로는 상대방의 효용을 에이전트 효용의 음수 값으로 처리하여 모델을 단순화한다. 게임의 모든 보상은 리프 노드(End state)에만 존재하는 희소 보상(Sparse reward) 구조를 가진다.
11:05
게임 평가와 재귀적 가치 계산
두 플레이어의 정책이 고정되어 있을 때 게임의 가치를 계산하는 방법은 재귀적 관계식을 이용한다. 리프 노드에서는 정의된 효용을 반환하고, 중간 노드에서는 현재 턴인 플레이어의 정책에 따라 하위 노드 가치들의 가중 평균을 구한다. 이 과정은 MDP의 정책 평가와 유사하며, 시뮬레이션을 통한 몬테카를로 방식이나 정확한 재귀 계산을 통해 수행 가능하다.
python
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고정된 정책을 가진 두 플레이어의 게임 가치를 재귀적으로 계산하는 함수 예시
29:30
Expectimax: 고정된 상대에 대한 최적 전략
상대방이 특정한 확률 분포를 가진 고정된 정책을 사용한다고 가정할 때 에이전트의 최적 전략을 찾는 기법이다. 에이전트 노드에서는 하위 노드 중 최대 가치를 선택(Max)하고, 상대방 노드에서는 확률에 따른 기대값(Expectation)을 계산한다. 이는 상대방을 지능적인 경쟁자가 아닌 랜덤한 환경의 일부로 취급하는 방식이며, 상대의 전략을 정확히 알 때 유효하다.
34:45
Minimax: 최악의 상대를 가정한 의사결정
상대방의 전략을 모를 때, 상대가 항상 나에게 가장 불리한 선택을 할 것이라고 가정하는 보수적인 전략이다. 에이전트 노드에서는 가치를 최대화(Max)하고, 상대방 노드에서는 에이전트의 가치를 최소화(Min)하는 행동을 선택한다. 이 알고리즘을 통해 얻은 가치는 상대방이 어떤 전략을 쓰더라도 보장받을 수 있는 최소한의 이득인 '하한선'을 제공한다.
python
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 재귀 함수
48:50
Alpha-Beta Pruning을 이용한 탐색 최적화
Minimax 탐색의 지수적 복잡도를 줄이기 위해 결과에 영향을 주지 않는 가지를 제거하는 기법이다. 탐색 중 현재 경로에서 얻을 수 있는 가치의 범위가 이미 발견된 다른 경로의 결과보다 나쁘다는 것이 확인되면 해당 하위 트리의 탐색을 즉시 중단한다. 탐색 순서(Ordering)를 최적화하여 좋은 노드를 먼저 방문할수록 가지치기 효율이 극대화되어 탐색 속도가 획기적으로 빨라진다.
66:48
평가 함수와 깊이 제한 탐색
체스와 같이 탐색 공간이 너무 큰 게임에서는 트리의 끝까지 갈 수 없으므로 깊이 제한 탐색(Depth-limited Search)을 수행한다. 특정 깊이에 도달하면 탐색을 멈추고 평가 함수(Evaluation Function)를 호출하여 해당 상태의 승률이나 유리함을 수치로 추정한다. 평가 함수는 기물의 수, 위치적 이점 등 도메인 지식을 반영하며, 탐색 깊이가 깊어질수록 평가 함수의 오류에 덜 민감해진다.
용어 해설
- 제로섬 게임(Zero-sum Game)
- — 한 플레이어의 이득이 다른 플레이어의 손실과 정확히 일치하여 전체 효용의 합이 0이 되는 게임 모델이다. 상대방의 효용을 나의 효용의 음수 값으로 정의함으로써 경쟁적인 상호작용을 수학적으로 단순화한다. 체스나 바둑과 같은 전형적인 대결 게임이 이에 해당한다.
- 익스펙티맥스(Expectimax)
- — 상대방이 고정된 확률적 전략을 사용한다고 가정할 때, 에이전트가 얻을 수 있는 기대 효용을 최대화하는 알고리즘이다. MDP의 가치 반복과 유사하게 작동하며, 상대방의 행동 노드에서 가중 평균(기대값)을 계산한다. 상대의 전략을 알고 있을 때 최적의 대응을 가능하게 한다.
- 미니맥스 알고리즘(Minimax Algorithm)
- — 상대방이 항상 자신의 효용을 최소화하려 한다는 최악의 시나리오를 가정하여 에이전트의 최소 이득을 최대화하는 결정 방식이다. 게임 트리에서 에이전트 노드는 최대값을, 상대방 노드는 최소값을 선택하며 재귀적으로 가치를 전달한다. 불확실한 상대에 대해 안전한 하한선을 보장하는 전략이다.
- 알파-베타 가지치기(Alpha-Beta Pruning)
- — Minimax 탐색 과정에서 최종 결정에 영향을 주지 않을 것이 확실한 하위 트리의 탐색을 중단하는 최적화 기법이다. 현재까지 발견된 최선의 값(Alpha, Beta) 범위를 유지하며, 이 범위를 벗어나는 노드는 더 이상 조사하지 않는다. 탐색 효율을 높여 더 깊은 수준까지 게임 트리를 분석할 수 있게 한다.
- 평가 함수(Evaluation Function)
- — 게임 트리의 끝까지 탐색하지 않고 중간 상태에서 해당 국면이 얼마나 유리한지를 수치로 추정하는 휴리스틱 함수이다. 체스의 기물 점수나 위치적 이점 같은 도메인 지식을 활용하여 상태의 가치를 계산한다. 탐색 깊이를 제한하면서도 합리적인 결정을 내리게 돕는 핵심 도구이다.
AI 분석 전체 내용 보기
AI 요약 · 북마크 · 개인 피드 설정 — 무료
출처 · 인용 안내
원문 발행 2026. 03. 10.수집 2026. 03. 10.출처 타입 YOUTUBE
인용 시 "요약 출처: AI Trends (aitrends.kr)"를 표기하고, 사실 확인은 원문 보기 기준으로 진행해 주세요. 자세한 기준은 운영 정책을 참고해 주세요.
