미래에 발생할 수 있는 여러 상황이나 결정의 결과를 미리 예측하고 평가하여, 현재의 최적의 행동을 결정하는 탐색 전략
당장의 이득만을 쫓는 탐욕적인 결정이 아닌, 장기적인 관점에서 더 나은 결과를 가져올 수 있는 결정을 내리기 위함
⭐ Lookahead의 특징
✅ 1. 지역 최적점 탈출:
당장 가장 좋은 선택이 장기적으로는 최악의 결과를 초래할 수 있다. Lookahead는 이런 '지역 최적점'에 갇히는 것을 방지하고 더 나은 전역 최적해를 찾을 기회를 제공한다.
✅ 2. 복잡한 의사결정:
여러 가지 선택지가 있고 각 선택이 미래에 다양한 결과를 낳을 때, Lookahead는 복잡한 상황에서 합리적인 판단을 내리는 데 도움을 준다.
✅ 3. 위험 관리:
특정 결정이 가져올 수 있는 잠재적 위험을 미리 파악하고 회피할 수 있게 한다.
📌 Lookahead의 단계
✅ 1. 탐색 트리 구축
현재 상태를 트리의 뿌리로 설정하고, 취할 수 있는 모든 가능한 행동을 탐색하며 트리를 만들어 나간다. 이 과정은 정해진 깊이(Lookahead Depth)까지만 진행된다.
ex) 깊이가 3이라면 현재 상태에서 3단계 앞까지의 모든 가능성들을 가지와 노드로 표현
✅ 2. '말단 노드' 평가
트리의 가장 끝단에 있는 노드들(Lookahead 깊이에 도달한 노드들)에 평가 함수를 적용하여 점수를 매긴다. (이 점수는 해당 노드가 얼마나 유망한 상태인지를 나타내는 추정치)
ex) 체스 AI라면 '상대방의 말이 몇 개 남았고, king이 얼마나 안전한지'와 같은 요소들을 평가하여 점수를 부여
✅ 3. 점수 역전파 (Backpropagation of Scores)
말단 노드에서 얻은 점수를 거꾸로 거슬러 올라가(역전파) 트리의 뿌리까지 전달한다. 이 과정에서 각 층위의 노드들은 자신에게 유리한 선택을 한다.
ex)
'나'의 턴(Max player): 내 차례인 노드는 아래 노드들 중 가장 높은 점수를 자신에게 가져온다.
'상대'의 턴(Min player): 상대방의 차례인 노드는 아래 노드들 중 가장 낮은 점수를 자신에게 가져온다 (상대방이 나에게 가장 불리한 선택을 할 것이라고 가정하기 때문).
✅ 4. 최적의 행동 선택
뿌리 노드에 도달한 최종 점수들을 비교하여 가장 높은 점수를 가져온 행동을 현재의 최적의 행동으로 선택한다. 이는 단순히 한 단계 앞의 이득이 아니라, Lookahead 깊이 내에서 상대방의 반격까지 고려한 가장 현명한 선택이 된다.
❗ Lookahead의 구현
✅ 1. 탐색 깊이 (Search Depth)
탐색의 깊이는 몇 수 앞까지 예측할 것인지를 의미
- 깊이가 깊을수록 더 정확한 예측이 가능하지만, 계산량이 기하급수적으로 늘어나기 때문에 시간이 오래 걸림
- 깊이가 얕으면 계산은 빠르지만, 단기적인 최적해에 머물러 장기적인 최적해를 놓칠 수 있음. 따라서 탐색 깊이는 문제의 복잡성과 허용 가능한 시간 사이의 균형을 고려하여 설정해야 함.
✅ 2. 상태 평가 함수 (Evaluation Function)
각 단계에서 탐색한 상태가 얼마나 좋은지 평가하는 함수
- 단순히 현재 상태뿐만 아니라 미래 예측의 결과를 종합적으로 평가하여 최적의 경로를 선택하는 데 결정적인 역할을 함
- 예를 들어, 체스 게임에서 상대방의 왕을 위협하는 상태, 유리한 위치에 있는 말의 수 등을 점수로 환산하여 평가할 수 있음
✅ 3. 탐색 알고리즘
Lookahead는 단독으로 사용되기보다, 미니맥스(Minimax) 알고리즘이나 알파-베타 가지치기(Alpha-Beta Pruning)와 같은 탐색 알고리즘과 결합하여 구현됨
-
미니맥스 (Minimax) 알고리즘
- '나'의 차례에서는 점수를 최대화(Maximize)하는 수를, '상대방'의 차례에서는 점수를 최소화(Minimize)하는 수를 선택하는 방식으로 탐색
- 이를 통해 상대방의 최적의 대응을 가정한 상태에서 나의 최적의 수를 찾음
-
알파-베타 가지치기 (Alpha-Beta Pruning)
- 미니맥스 알고리즘의 비효율성을 개선한 방법
- 탐색 과정에서 더 이상 최적해가 나올 가능성이 없는 가지(branch)를 미리 잘라내어 탐색 범위를 줄이는 방식
- 이를 통해 탐색 속도를 비약적으로 향상시킬 수 있음
⚠️ Lookahead의 장단점
✅ 장점
- 전략적 판단: 현재의 이득뿐만 아니라 미래에 발생할 수 있는 여러 상황을 예측하여 더 나은 장기적인 결정을 내릴 수 있음
- 지역 최적해 방지: 단기적으로는 최선이 아닐 수 있지만, 장기적으로 유리한 수를 찾아 지역 최적해(Local Optimum)에 갇히는 것을 방지함
- 상대방의 대응 고려: 미니맥스(Minimax)와 같은 알고리즘과 결합하여 상대방의 최적 대응을 가정한 상태에서 나의 수를 결정하므로, 더 정교하고 방어적인 전략을 세울 수 있음
❌ 단점
- 높은 연산 복잡도: 탐색 깊이가 깊어질수록 고려해야 할 경우의 수가 기하급수적으로 증가합니다. 이로 인해 연산량이 매우 많아져 실행 시간이 길어짐
- 비현실성: 복잡한 문제에서는 모든 경우의 수를 탐색하는 것이 사실상 불가능함
- 평가 함수의 의존성: Lookahead의 성능은 상태 평가 함수가 얼마나 정확하게 미래를 예측하는지에 크게 의존함. 평가 함수가 부실하면 잘못된 결정을 내릴 수 있음.
📝 예제
0부터 시작해서 10에 가장 빨리 도달하는 것. 각 위치에서 +1, +2, +3 이동이 가능하며, 각 이동에는 비용이 든다
# 비용 예시: 이동 거리가 길수록 비용이 높거나, 특정 지점은 비용이 높을 수 있음. 여기서는 간단히 이동 거리를 비용으로 간주
move_costs = {1: 1, 2: 2, 3: 3}
# 목표 지점
TARGET = 10
def evaluate_position(position):
"""
현재 위치를 평가하는 함수 (목표에 가까울수록 좋음)
여기서는 목표까지 남은 거리가 짧을수록 좋다고 가정
"""
return TARGET - position # 남은 거리가 짧을수록 높은 점수 (역으로 해석)
def find_best_move_greedy(current_pos):
"""
탐욕적인 방식: 한 칸만 보고 가장 좋은 이동 선택
(여기서는 비용이 가장 적게 드는 이동 = 짧은 이동)
"""
best_move = -1
min_cost = float('inf')
print(f"현재 위치: {current_pos} (탐욕적)")
for move_distance in [1, 2, 3]:
cost = move_costs[move_distance]
if cost < min_cost and current_pos + move_distance <= TARGET:
min_cost = cost
best_move = move_distance
if best_move != -1:
print(f" 탐욕적 선택: +{best_move} (비용: {min_cost}) -> 다음 위치: {current_pos + best_move}")
return best_move
def find_best_move_with_lookahead(current_pos, lookahead_depth):
"""
Lookahead 방식: 주어진 깊이만큼 미래를 예측하여 가장 좋은 이동 선택
"""
if current_pos == TARGET:
return 0 # 목표 도달
best_overall_score = -float('inf') # 더 높은 점수가 좋은 선택 (평가 함수 기준)
best_initial_move = -1
print(f"현재 위치: {current_pos} (Lookahead 깊이: {lookahead_depth})")
for initial_move in [1, 2, 3]:
next_pos = current_pos + initial_move
if next_pos > TARGET:
continue # 목표를 넘어가는 이동은 무시
current_path_cost = move_costs[initial_move]
# Lookahead 시뮬레이션
if lookahead_depth > 0:
# 재귀적으로 다음 단계 Lookahead 호출 (가장 좋은 다음 이동을 찾음)
# 여기서는 다음 이동으로 인해 얻을 '미래 가치'를 고려하는 간단한 로직
# 실제로는 Minimax나 Alpha-Beta Pruning 같은 알고리즘이 사용될 수 있음
future_value_score = evaluate_position(next_pos) # 다음 위치의 예상 가치
# 미래 경로를 더 깊이 탐색하는 로직 (간단화)
# 예를 들어, 다음 스텝에서 또 다시 Lookahead를 수행하여 미래 점수 합산
if next_pos < TARGET:
# 다음 스텝에서 얻을 수 있는 최대 점수를 대략적으로 예측
# (실제로는 복잡한 탐색 트리를 구성하고 모든 경로를 평가)
# 여기서는 단순히 다음 스텝의 평가 점수를 추가
future_value_score += evaluate_position(next_pos + 1) # 예시로 한 스텝 더 예측
if lookahead_depth > 1:
future_value_score += evaluate_position(next_pos + 2) # 더 깊이 예측하는 흉내
# 현재 이동 비용과 미래 가치를 결합하여 이 행동의 최종 점수 계산
# (점수는 높을수록 좋고, 비용은 낮을수록 좋으므로, 비용을 점수에서 뺌)
overall_score_for_this_move = future_value_score - current_path_cost
else: # Lookahead 깊이가 0이면 현재 위치만 평가 (탐욕적과 유사)
overall_score_for_this_move = evaluate_position(next_pos) - current_path_cost
print(f" +{initial_move} 선택 시 예상 점수 (비용 포함): {overall_score_for_this_move:.2f}")
if overall_score_for_this_move > best_overall_score:
best_overall_score = overall_score_for_this_move
best_initial_move = initial_move
if best_initial_move != -1:
print(f" Lookahead 선택: +{best_initial_move} (예상 점수: {best_overall_score:.2f}) -> 다음 위치: {current_pos + best_initial_move}")
return best_initial_move
print("--- 탐욕적 방식 ---")
current_position = 0
while current_position < TARGET:
move = find_best_move_greedy(current_position)
if move == -1: # 더 이상 움직일 수 없을 때
print("더 이상 움직일 수 없습니다.")
break
current_position += move
print(f"최종 위치: {current_position}\n")
print("--- Lookahead 방식 (깊이 1) ---")
current_position = 0
while current_position < TARGET:
move = find_best_move_with_lookahead(current_position, lookahead_depth=1)
if move == -1:
print("더 이상 움직일 수 없습니다.")
break
current_position += move
print(f"최종 위치: {current_position}\n")
print("--- Lookahead 방식 (깊이 2) ---")
current_position = 0
while current_position < TARGET:
move = find_best_move_with_lookahead(current_position, lookahead_depth=2)
if move == -1:
print("더 이상 움직일 수 없습니다.")
break
current_position += move
print(f"최종 위치: {current_position}\n")🔎 Lookahead의 주요 활용 예시
✅ 1. 게임 인공지능 (Game AI)
체스, 바둑, 틱택토와 같은 보드 게임에서 컴퓨터가 다음 수를 결정할 때 사용. Lookahead를 통해 몇 수 앞의 상황을 미리 예측하여 상대방의 대응까지 고려한 최적의 수를 찾음.
- 동작 방식
- 미니맥스(Minimax)나 알파-베타 가지치기(Alpha-Beta Pruning)와 같은 알고리즘을 사용
- 내가 최적의 수를 두었을 때 상대방도 최적의 대응을 할 것을 가정하여 탐색
- ex) 체스 게임에서 룩어헤드를 사용하면, 단순히 현재 폰을 잡는 수가 아니라, 몇 수 뒤에 상대방의 퀸을 잡을 수 있는 더 유리한 경로를 찾아낼 수 있음
✅ 2. 경로 계획 및 탐색
로봇 공학이나 자율 주행 차량에서 최적의 경로를 찾거나 장애물을 피할 때 사용되는 전략
- 동작 방식
- 현재 위치에서 몇 초 후의 로봇 위치나 주변 환경의 변화를 미리 예측하고, 그 예측을 바탕으로 충돌 위험이 가장 적고 목표에 빠르게 도달할 수 있는 경로를 선택
- ex) 자율 주행 차량이 교차로에서 좌회전할 때, 반대편에서 오는 차량의 속도를 예측하여 충돌이 발생하지 않는 최적의 진입 시점을 결정
✅ 3. 스케줄링 및 자원 할당
복잡한 작업 스케줄링이나 자원 할당 문제에서 발생할 수 있는 병목 현상이나 비효율성을 미리 예측하여 최적의 계획을 세움
- 동작방식
- 각 작업의 우선순위와 소요 시간을 기반으로 다양한 스케줄 시나리오를 미리 탐색하고, 가장 효율적인 스케줄을 찾아냄
- ex) 공장의 생산 라인에서 작업을 배정할 때, 특정 기계에 부하가 집중될 경우를 미리 예측하여 이를 방지하고 전체 생산 효율을 높이는 스케줄을 만듦
