요즘 AI 담론의 중심은 거대 언어 모델(LLM)과 생성형 AI가 차지하고 있다. 하지만 화려한 챗봇의 이면을 들여다보면, 결국 ‘현재 상태에서 목표 상태로 어떻게 효율적으로 이동할 것인가’라는 고전적인 탐색(Search)의 문제가 여전히 핵심 엔진으로 작동하고 있다. 경로 최적화부터 복잡한 퍼즐 해결, 로보틱스의 움직임 제어에 이르기까지 AI가 정답을 찾아가는 과정은 정교하게 설계된 상태 공간의 탐색 과정과 맞닿아 있다.
세상을 모델링하는 방법: 상태 공간과 탐색 트리
AI가 문제를 풀기 위해서는 먼저 세상을 컴퓨터가 이해할 수 있는 형태로 정의해야 한다. 이를 상태 공간(State Space) 모델링이라고 한다. 상태 공간은 문제에서 발생할 수 있는 모든 가능한 설정의 집합이다. 예를 들어 체스라면 바둑판 위의 모든 말의 배치 상태가 하나의 ‘상태’가 되고, 미로 찾기라면 현재 캐릭터의 좌표 (x, y)가 상태가 된다.
여기서 중요한 것은 추상화(Abstraction)의 수준이다. 모델을 너무 세밀하게 잡으면 계산량이 폭발하여 시스템이 멈추고, 너무 단순하게 잡으면 현실의 제약 조건을 반영하지 못해 엉뚱한 답을 내놓는다. 적절한 추상화를 거친 후, 우리는 초기 상태(Initial State)에서 시작해 가능한 행동(Actions)을 취하며 다음 상태로 넘어가는 후계 함수(Successor Function)를 정의한다. 이 과정이 반복되면서 가지를 뻗어 나가는 구조가 바로 탐색 트리(Search Tree)가 된다.
많은 입문자가 상태 공간 그래프와 탐색 트리를 혼동하곤 한다. 상태 공간 그래프는 세상에 존재하는 모든 상태와 그 연결 관계를 나타내는 지도라면, 탐색 트리는 특정 시작점에서 출발해 실제로 어떤 경로를 밟아 내려갔는지를 기록한 ‘탐색의 기록’이다. 동일한 상태라도 도달 경로가 다르면 트리에서는 서로 다른 노드로 취급된다는 점이 핵심이다.
맹목적 탐색을 넘어 효율로: 휴리스틱의 마법
너비 우선 탐색(BFS)이나 균일 비용 탐색(UCS) 같은 알고리즘은 반드시 최적의 해를 찾아준다는 보장(Optimal)이 있지만, 모든 방향을 다 훑어야 하므로 속도가 매우 느리다. 마치 안개 속에서 사방으로 손을 뻗어 출구를 찾는 것과 같다. 이때 필요한 것이 바로 휴리스틱(Heuristic), 즉 ‘경험적인 추측’이다.
휴리스틱 함수 $h(n)$은 현재 상태에서 목표 상태까지 남은 거리를 추정하는 함수다. 가장 대표적인 예가 맨해튼 거리(Manhattan Distance)다. 격자 모양의 맵에서 장애물이 없다고 가정하고 가로 거리와 세로 거리의 합을 구하는 방식이다. $\text{Manhattan}(x_1, y_1, x_2, y_2) = |x_1 – x_2| + |y_1 – y_2|$ 라는 간단한 식 하나만으로 AI는 어느 방향이 목표에 더 가까운지 ‘짐작’할 수 있게 된다.
이 휴리스틱을 활용한 A* 알고리즘은 ‘지금까지 온 거리($g(n)$)’와 ‘앞으로 갈 예상 거리($h(n)$)’를 더한 값 $f(n) = g(n) + h(n)$이 가장 작은 노드부터 탐색한다. 덕분에 불필요한 경로를 획기적으로 줄이면서도, 휴리스틱 함수가 실제 거리보다 작거나 같게 추정(Admissible)한다면 여전히 최적의 해를 보장받을 수 있다.
실습: Python으로 구현하는 간단한 상태 공간 탐색
이론만으로는 감이 오지 않는다. 간단한 2차원 그리드 맵에서 시작점에서 목표점까지 최단 경로를 찾는 A* 알고리즘의 구조를 살펴보자. 아래 코드는 휴리스틱으로 맨해튼 거리를 사용하며, 우선순위 큐를 통해 가장 유망한 상태를 먼저 확장한다.
import heapq
def manhattan_distance(p1, p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
def a_star_search(grid, start, goal):
# grid: 0은 통로, 1은 벽
close_set = set()
came_from = {}
g_score = {start: 0}
f_score = {start: manhattan_distance(start, goal)}
oheap = []
heapq.heappush(oheap, (f_score[start], start))
while oheap:
current = heapq.heappop(oheap)[1]
if current == goal:
data = []
while current in came_from:
data.append(current)
current = came_from[current]
return data[::-1] # 경로 반환
close_set.add(current)
for i, j in [(0,1), (0,-1), (1,0), (-1,0)]:
neighbor = current[0] + i, current[1] + j
if 0 <= neighbor[0] < len(grid) and 0 <= neighbor[1] < len(grid[0]):
if grid[neighbor[0]][neighbor[1]] == 1 or neighbor in close_set:
continue
tentative_g_score = g_score[current] + 1
if tentative_g_score < g_score.get(neighbor, float('inf')):
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score[neighbor] = tentative_g_score + manhattan_distance(neighbor, goal)
heapq.heappush(oheap, (f_score[neighbor], neighbor))
return False
# 실행 예시
grid = [[0, 0, 0, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 1, 1, 0]]
start = (0, 0)
goal = (3, 3)
print(f"Path found: {a_star_search(grid, start, goal)}")위 코드를 실행하기 위해서는 Python 환경이 필요하며, 별도의 외부 라이브러리 설치 없이 표준 라이브러리인 heapq만으로 동작한다. 실행 순서는 다음과 같다.
- Python 3.x 버전이 설치된 환경을 준비한다.
- 위 코드를
search_ai.py파일로 저장한다. - 터미널에서
python search_ai.py명령어를 입력해 실행한다.
만약 맵의 크기를 100×100 이상으로 키우고 벽(1)을 촘촘하게 배치했는데 프로그램이 너무 느려진다면, 그것은 휴리스틱 함수가 적절하지 않거나 탐색해야 할 상태 공간이 기하급수적으로 늘어났기 때문이다. 이럴 때는 Weighted A* 처럼 휴리스틱 값에 가중치를 곱해 최적성은 조금 포기하더라도 탐색 속도를 높이는 전략을 고려해 볼 수 있다.
다음에 해볼 것: 정적 탐색에서 동적 게임 이론으로
지금까지 살펴본 탐색은 환경이 변하지 않는 ‘정적’인 상황이었다. 하지만 실제 세상, 특히 게임이나 자율주행 환경은 내가 움직일 때 상대방이나 주변 환경도 함께 변한다. 이제는 단순히 경로를 찾는 것을 넘어, 상대의 최선의 수를 예측하고 나의 이득을 최대화하는 Minimax 알고리즘이나 Alpha-Beta Pruning 같은 게임 탐색 영역으로 확장해 볼 차례다.
우리는 과연 복잡한 현실 세계를 얼마나 단순하게 모델링해야 효율적인 정답을 얻을 수 있을까? 너무 많은 정보를 넣어서 느려진 AI와 너무 적은 정보 때문에 멍청해진 AI 사이의 그 절묘한 균형점은 어디에 있을까? 다음 글에서는 이 균형을 잡는 ‘상태 정의의 기술’에 대해 더 깊이 다뤄보고자 한다.