어두운 방 안, 모니터 속 팩맨이 유령을 피해 미로를 누비는 화면이 빠르게 깜빡입니다. 수많은 갈림길 앞에서 팩맨이 어느 방향으로 움직여야 모든 점(dot)을 가장 빠르게 먹을 수 있을지, 그 찰나의 결정 뒤에는 정교한 수학적 설계가 숨어 있습니다. 단순한 게임처럼 보이지만 이는 인공지능이 복잡한 세상에서 정답을 찾아가는 ‘탐색 기반 문제해결’의 전형적인 모습입니다.
세상을 데이터로 정의하는 방법: 상태공간과 정식화
인공지능이 문제를 해결하려면 먼저 자신이 처한 상황을 수학적으로 정의해야 합니다. 이를 문제 정식화(Problem Formulation)라고 하며, 핵심은 상태공간(State Space)을 설정하는 것입니다. 상태공간이란 문제 해결을 위해 고려해야 할 모든 가능한 상태들의 집합을 의미합니다. 예를 들어 팩맨 게임에서 상태공간은 팩맨의 현재 좌표, 유령들의 위치, 그리고 각 점들이 먹혔는지 여부를 나타내는 불리언(Boolean) 값들의 조합으로 구성됩니다.
정식화 과정에서는 단순히 상태만 정의하는 것이 아니라, 상태를 변화시키는 행동(Actions)과 그 결과로 나타나는 다음 상태를 계산하는 전이 모델(Transition Model)이 필요합니다. 여기에 초기 상태(Initial State)에서 시작해 목표 상태(Goal Test)에 도달했는지 확인하는 조건과, 이동 시 발생하는 누적 비용을 계산하는 경로 비용(Path Cost) 함수가 더해지면 비로소 AI가 움직일 수 있는 지도가 완성됩니다. 이 지도가 얼마나 정교하게 설계되었느냐에 따라 탐색의 효율성과 최종 해답의 품질이 결정됩니다.
무작정 찾기 vs 똑똑하게 찾기: 탐색 전략의 차이
지도가 완성되었다면 이제 실제로 경로를 찾아야 합니다. 가장 단순한 방법은 무정보 탐색(Uninformed Search), 즉 블라인드 서치입니다. 이는 목표까지의 거리나 방향에 대한 사전 지식 없이 상태공간을 체계적으로 넓혀가는 방식입니다. 대표적으로 스택(Stack)을 이용해 한 우물만 깊게 파는 깊이 우선 탐색(DFS)과 큐(Queue)를 이용해 층별로 넓게 살피는 너비 우선 탐색(BFS)이 있습니다. 하지만 상태공간이 커질수록 분기 계수(Branching Factor)와 깊이(Depth)에 따라 연산량이 지수적으로 증가하는 ‘상태 폭발’ 문제에 직면하게 됩니다.
이 한계를 극복하기 위해 도입된 것이 휴리스틱 기반 탐색(Informed Search)입니다. 휴리스틱 함수 h(n)은 현재 상태에서 목표까지 남은 비용을 추정하는 ‘경험적인 지식’입니다. 예를 들어 미로 찾기에서 실제 경로가 아닌 직선거리(맨해튼 거리)를 계산해 목표에 더 가까워 보이는 노드를 먼저 확장하는 Greedy Best-First Search가 이에 해당합니다. 무작정 모든 경로를 뒤지는 대신, 가능성이 높은 곳을 우선적으로 탐색함으로써 시간과 메모리 비용을 획기적으로 줄일 수 있습니다.
실습: 파이썬으로 구현하는 간단한 상태공간 탐색
이론적인 개념을 넘어, 실제로 AI가 어떻게 상태를 확장하고 목표를 찾는지 간단한 파이썬 코드로 구현해 볼 수 있습니다. 아래는 우선순위 큐를 활용하여 누적 비용이 가장 낮은 경로를 먼저 찾는 비용 기반 탐색(Uniform Cost Search)의 기본 구조입니다.
import heapq
def uniform_cost_search(graph, start, goal):
# (누적비용, 현재노드, 경로)를 저장하는 우선순위 큐
queue = [(0, start, [start])]
visited = set()
while queue:
(cost, current, path) = heapq.heappop(queue)
if current not in visited:
visited.add(current)
if current == goal:
return path, cost
for neighbor, weight in graph.get(current, {}).items():
if neighbor not in visited:
# 누적 비용을 계산하여 큐에 삽입
heapq.heappush(queue, (cost + weight, neighbor, path + [neighbor]))
return None, float('inf')
# 상태공간 정의 (그래프 형태)
# A에서 D까지 가는 최적 경로 탐색
world_map = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
path, total_cost = uniform_cost_search(world_map, 'A', 'D')
print(f"Optimal Path: {path}, Total Cost: {total_cost}")
# 예상 출력: Optimal Path: ['A', 'B', 'C', 'D'], Total Cost: 4위 코드를 실행하여 최적 경로를 찾는 과정은 다음과 같습니다.
heapq라이브러리를 통해 우선순위 큐를 설정하여 항상 비용이 가장 낮은 노드를 먼저 꺼내도록 합니다.visited집합을 만들어 이미 방문한 상태를 기록함으로써 무한 루프에 빠지는 것을 방지합니다.- 현재 노드에서 갈 수 있는 모든 이웃 노드의 누적 비용을 계산해 큐에 넣고, 목표 노드
goal에 도달할 때까지 반복합니다.
만약 실행 중 KeyError가 발생한다면, graph.get(current, {}) 대신 graph[current]를 사용했기 때문일 가능성이 큽니다. 연결된 노드가 없는 상태(Dead-end)에 도달했을 때를 대비해 get 메서드를 사용하여 빈 딕셔너리를 반환하게 하는 것이 안전한 구현 팁입니다.
최적성과 완전성, 그리고 탐색의 미래
우리가 탐색 알고리즘을 평가할 때 가장 중요하게 보는 기준은 완전성(Completeness)과 최적성(Optimality)입니다. 완전성이란 해답이 존재한다면 반드시 찾아낼 수 있는지를 의미하며, 최적성은 찾아낸 해답이 최소 비용의 최단 경로인지를 의미합니다. BFS는 완전성과 최적성을 모두 보장하지만 메모리 소모가 극심하고, DFS는 메모리는 적게 쓰지만 최적의 해를 찾는다는 보장이 없습니다.
현대의 AI는 여기서 더 나아가 몬테카를로 트리 탐색(MCTS)과 같은 확률적 기법을 결합하여 알파고와 같은 복잡한 의사결정 시스템을 구축합니다. 단순히 모든 경우의 수를 계산하는 것이 아니라, 유망한 경로를 시뮬레이션하고 그 결과를 바탕으로 탐색 트리를 확장하는 방식입니다. 결국 AI의 발전은 ‘어떻게 하면 더 적은 자원으로 더 정확한 정답(Optimal Solution)에 빠르게 도달할 것인가’라는 탐색의 효율성 싸움이라고 할 수 있습니다.
이번 글을 통해 상태공간의 정의부터 휴리스틱을 이용한 효율적인 탐색까지 살펴보았습니다. 여러분의 일상 속에서도 복잡한 선택의 순간에 나름의 ‘휴리스틱 함수’를 적용해 최적의 경로를 찾고 있지는 않으신가요? 다음에는 정적인 환경을 넘어, 상대방의 수까지 계산해야 하는 적대적 탐색(Adversarial Search)과 게임 이론에 대해 다뤄보고자 합니다.