4강
게임트리 탐색
1. 최대최소 탐색 (Minimax Search)
개념
- 두 명의 플레이어가 서로 번갈아가며 수를 두는 게임에서,
상대방이 항상 최선의 수를 둔다고 가정하고
자신에게 가장 유리한 수를 선택하는 탐색 방법
핵심 아이디어
- 내 차례(최대화): 가능한 수 중 가장 높은 가치를 선택
- 상대 차례(최소화): 가능한 수 중 가장 낮은 가치를 선택
동작 방식
- 트리를 최대화(MIN)와 최소화(MAX) 단계로 번갈아 내려가며,
리프 노드에서부터 위로 올라오며 최종적으로 루트에서 수를 결정
2. 최대최소 탐색의 실제 예 (삼목게임 Tic-Tac-Toe)
평가함수 F
- 승리한 상태: F = ∞
- 패배한 상태: F = -∞
- 그 외:
W: 이길 가능성이 있는 줄의 수L: 질 가능성이 있는 줄의 수F = W - L
3. α-β 가지치기 (Alpha-Beta Pruning)
목적
- 불필요한 노드 탐색을 줄여 탐색 효율을 높이는 방법
정의
- α (알파): 최대화 노드에서 찾은 현재까지의 최댓값
- β (베타): 최소화 노드에서 찾은 현재까지의 최솟값
가지치기 조건
- 최소화 노드에서 후계 노드의 값 ≤ α인 경우, 더 이상 탐색할 필요 없음
- 최대화 노드에서 후계 노드의 값 ≥ β인 경우, 더 이상 탐색할 필요 없음
4. 몬테카를로 트리 탐색 (MCTS: Monte Carlo Tree Search)
개념
- 무작위 시뮬레이션을 기반으로 한 게임트리 탐색 방법
- 체스, 바둑처럼 경우의 수가 많고 깊이가 깊은 게임에 적합
4단계 구성
- 선택 (Selection)
- 루트에서 시작하여 자식 노드를 선택하면서 내려감
- 확장 (Expansion)
- 아직 탐색되지 않은 노드를 확장하여 트리에 추가
- 시뮬레이션 (Simulation)
- 임의로 게임을 끝까지 진행 (롤아웃)
- 역전파 (Backpropagation)
- 결과(승/패/무)를 루트까지 전달하며 통계 갱신
5. 선택 전략: UCT 알고리즘
UCB1 수식
UCB1(ni) = v̄i + C × sqrt(ln(Np) / Ni)v̄i: 평균 가치Ni: 자식 노드의 방문 횟수Np: 부모 노드의 방문 횟수C: 탐사 강도를 조절하는 상수
6. 최종 수 선택 전략
- 최대 자식 (max child): 보상이 가장 높은 노드
- 강인한 자식 (robust child): 방문 횟수가 가장 많은 노드
- 최대-강인 자식: 위 둘의 균형
- 안전한 자식 (secure child): 신뢰 하한값이 최대인 노드
7. AlphaGo와 MCTS
-
AlphaGo는 MCTS를 바탕으로 게임 트리를 탐색하고,
정책망과 가치망을 통해 최적의 수를 선택함 -
주요 구성:
- 정책망: 다음 수를 어디에 둘지 확률적으로 예측
- 가치망: 해당 상태의 승리 확률을 평가
- 롤아웃 정책: 빠른 시뮬레이션 수행
요약
최대최소 탐색
- 상대방이 최선을 다한다고 가정하고, 나에게 유리한 수 선택
- 게임 트리에서 MAX / MIN 반복
- 효율 향상을 위해 α-β 가지치기 사용
몬테카를로 트리 탐색
- 무작위 시뮬레이션 기반 트리 탐색
- 선택, 확장, 시뮬레이션, 역전파 단계
- AlphaGo의 핵심 탐색 방법
코드
공통 목표 함수
# 최소값을 찾고 싶은 함수 (목표)
def objective_function(x):
return (x - 3)**2언덕오르기 탐색 (Hill Climbing)
import random
def hill_climbing(objective_function, start_x, step_size=0.1, max_iterations=100):
current_x = start_x
current_value = objective_function(current_x)
for i in range(max_iterations):
# 현재 위치 주변의 두 점을 확인
neighbors = [current_x + step_size, current_x - step_size]
# 이웃 중 더 나은(값이 더 작은) 점을 선택
next_x = min(neighbors, key=objective_function)
next_value = objective_function(next_x)
print(f"Iteration {i}: x = {current_x:.5f}, f(x) = {current_value:.5f}")
# 더 이상 개선이 없으면 멈춤
if next_value >= current_value:
break
current_x, current_value = next_x, next_value
print(f"최적해 추정: x = {current_x}, 최소값 = {current_value}")
return current_x
# 실행
hill_climbing(objective_function, start_x=random.uniform(-10, 10))설명
- 현재 위치에서 출발해서, 이웃 중 더 나은 방향으로만 이동
- f(x)가 작아지는 방향(오르막)을 선택하고, 나빠지면 중단
- 단점: 지역 최솟값에 빠질 수 있음
모의 담금질 (Simulated Annealing)
import math
def simulated_annealing(objective_function, start_x, initial_temp=100.0, cooling_rate=0.95, max_iterations=1000):
current_x = start_x
current_value = objective_function(current_x)
temperature = initial_temp
for i in range(max_iterations):
# 온도가 너무 낮아지면 중단
if temperature < 1e-6:
break
# 근처의 랜덤한 이웃 선택
new_x = current_x + random.uniform(-1, 1)
new_value = objective_function(new_x)
# 차이 계산
delta = new_value - current_value
# 개선되었거나, 확률적으로 허용하는 경우 이동
if delta < 0 or random.random() < math.exp(-delta / temperature):
current_x = new_x
current_value = new_value
print(f"Iteration {i}: x = {current_x:.5f}, f(x) = {current_value:.5f}, T = {temperature:.5f}")
# 온도 감소
temperature *= cooling_rate
print(f"최적해 추정: x = {current_x}, 최소값 = {current_value}")
return current_x
# 실행
simulated_annealing(objective_function, start_x=random.uniform(-10, 10))설명
- 언덕오르기와 달리, 나쁜 방향으로도 확률적으로 이동함
- 시간이 지나면서 확률이 줄어들어 전역 최솟값에 수렴하는 방식
- e^(-delta/T) 확률로 나쁜 해도 수용
A* 알고리즘 (A-Star Search)
import heapq
# A*에서 사용할 노드 정의 (단순화된 x값만 있음)
class Node:
def __init__(self, x, g):
self.x = x # 현재 상태 (x값)
self.g = g # 시작점에서 현재까지의 비용 (실제 비용)
self.h = (x - 3)**2 # 목표까지의 예측 비용
self.f = self.g + self.h # 평가함수 f(x) = g(x) + h(x)
def __lt__(self, other):
return self.f < other.f # 우선순위 비교
def astar_search(start_x, goal_range=0.01):
open_list = []
heapq.heappush(open_list, Node(start_x, g=0))
visited = set()
while open_list:
current = heapq.heappop(open_list)
print(f"x = {current.x:.5f}, f(x) = {current.f:.5f}, g = {current.g:.5f}, h = {current.h:.5f}")
# 목표에 도달했는지 검사
if abs(current.x - 3) <= goal_range:
print(f"최적해 도달: x = {current.x}, 최소값 = {objective_function(current.x)}")
return current.x
visited.add(round(current.x, 5))
# 이웃 생성 (양옆으로 조금씩 이동)
for dx in [-0.1, 0.1]:
neighbor_x = current.x + dx
if round(neighbor_x, 5) in visited:
continue
heapq.heappush(open_list, Node(neighbor_x, g=current.g + abs(dx)))
print("해를 찾지 못함")
return None
# 실행
astar_search(start_x=random.uniform(-10, 10))설명
- f(n) = g(n) + h(n) 으로 평가함수 구성
- g(n): 현재까지 이동한 거리
- h(n): 목표까지 얼마나 남았는지 예측 - f(n)이 가장 작은 노드를 먼저 선택해서 탐색
- h(n)이 정확할수록 탐색 성능이 좋아짐
Working Abroad ...