복잡한 미로 앞에 선 팩맨이 유령을 피해 모든 점을 먹기 위해 어떤 생각을 할까. 단순히 무작위로 움직이는 것이 아니라, 현재 위치에서 가능한 모든 선택지를 계산하고 가장 효율적인 경로를 찾아내는 과정이 과연 단순한 ‘운’에 불과할까. 우리가 직관적으로 수행하는 문제 해결 과정을 수학적 구조로 옮겨놓은 것이 바로 인공지능의 상태 공간 탐색이다.
세상을 상태와 행동으로 정의하는 문제 정식화
인공지능이 문제를 해결하려면 먼저 세상을 컴퓨터가 이해할 수 있는 형태로 정의해야 한다. 이를 문제 정식화(Problem Formulation)라고 부르는데, 핵심은 현재의 상황을 상태(State)로 정의하고, 그 상태를 변화시키는 규칙을 행동(Action)으로 설정하는 것이다. 예를 들어 팩맨 게임에서 상태는 팩맨의 좌표, 유령의 위치, 그리고 각 점(dot)들이 먹혔는지 여부를 나타내는 불리언 값들의 집합이 된다.
단순히 상태를 정의하는 것만으로는 부족하다. 초기 상태(Initial State)에서 시작해 어떤 행동을 했을 때 다음 상태로 넘어가는지 정의하는 전이 모델(Transition Model)이 필요하며, 현재 상태가 우리가 원하는 정답인지 확인하는 목표 테스트(Goal Test)가 있어야 한다. 여기에 각 이동마다 발생하는 비용을 계산하는 경로 비용(Path Cost) 함수까지 더해지면, AI는 비로소 ‘어디로 가야 가장 저렴하고 빠르게 목표에 도달할지’를 계산할 수 있는 수학적 토대를 갖추게 된다.
탐색 트리와 무정보 탐색의 한계
정식화된 문제는 보통 탐색 트리(Search Tree) 형태로 확장된다. 루트 노드인 초기 상태에서 시작해 가능한 모든 행동을 뻗어 나가며 자식 노드들을 생성하는 방식이다. 하지만 여기서 치명적인 문제가 발생한다. 평균적으로 한 상태에서 생성되는 자식의 수인 분기 계수(Branching Factor, b)와 목표까지의 최소 깊이인 깊이(d)가 커질수록, 탐색해야 할 노드의 수는 지수적으로 증가하여 메모리와 시간이 폭발하는 ‘상태 공간 폭발’ 현상이 일어난다.
사전 지식이 전혀 없는 무정보 탐색(Uninformed Search), 즉 블라인드 서치는 이 폭발적인 공간을 무식하게 훑는다. 스택을 이용해 한 우물만 깊게 파는 깊이 우선 탐색(DFS)이나, 큐를 이용해 층별로 넓게 살피는 너비 우선 탐색(BFS)이 대표적이다. BFS는 최단 경로를 보장하는 완전성을 갖지만 메모리 소모가 극심하고, DFS는 메모리는 적게 쓰지만 무한 루프에 빠질 위험이 크다. 이를 해결하기 위해 방문한 상태를 기록하는 그래프 탐색(Graph Search) 구조를 도입해 중복 방문을 막는 것이 필수적이다.
휴리스틱과 A* 알고리즘으로 찾는 최적 경로
무작위 탐색의 비효율을 극복하기 위해 도입된 것이 바로 휴리스틱(Heuristic)이다. 휴리스틱 함수 $h(n)$은 현재 상태 $n$에서 목표까지 남은 예상 비용을 추정하는 ‘똑똑한 짐작’이다. 예를 들어 지도상에서 목적지를 찾을 때, 실제 도로망을 무시하고 직선거리를 계산하는 ‘맨해튼 거리’나 ‘유클리드 거리’가 대표적인 휴리스틱이다.
가장 효율적인 탐색 알고리즘으로 꼽히는 A* 알고리즘은 지금까지 온 비용 $g(n)$과 앞으로 갈 예상 비용 $h(n)$의 합인 평가 함수 $f(n) = g(n) + h(n)$을 사용한다. 이를 통해 AI는 목표 방향으로 가장 유망한 노드를 우선적으로 확장하며, 불필요한 경로 탐색을 획기적으로 줄인다. 좋은 휴리스틱은 실제 비용보다 절대 크게 추정하지 않는 ‘허용성(Admissibility)’을 가져야 하며, 그래야만 최적의 해(Optimal Solution)를 보장할 수 있다.
실습: 파이썬으로 구현하는 기본 탐색 구조
이론적인 상태 공간 탐색을 실제로 구현해보기 위해, 파이썬의 heapq 라이브러리를 활용한 우선순위 큐 기반의 탐색 구조를 만들어 볼 수 있다. 아래 코드는 상태와 비용을 관리하며 최적 경로를 찾는 기본적인 프레임워크를 보여준다.
import heapq
def a_star_search(problem):
# (우선순위, 현재상태, 경로, 누적비용)
frontier = []
heapq.heappush(frontier, (0, problem.initial_state, [], 0))
visited = set()
while frontier:
f, current_state, path, g = heapq.heappop(frontier)
if current_state in visited:
continue
path = path + [current_state]
if problem.goal_test(current_state):
return path, g
visited.add(current_state)
for action, next_state, cost in problem.get_successors(current_state):
if next_state not in visited:
# f(n) = g(n) + h(n)
new_g = g + cost
new_f = new_g + problem.heuristic(next_state)
heapq.heappush(frontier, (new_f, next_state, path, new_g))
return None, float('inf')
# 실행 예시를 위한 간단한 문제 정의 클래스
class MazeProblem:
def __init__(self):
self.initial_state = (0, 0)
self.goal_state = (2, 2)
def goal_test(self, state):
return state == self.goal_state
def heuristic(self, state):
# 맨해튼 거리 계산
return abs(state[0] - self.goal_state[0]) + abs(state[1] - self.goal_state[1])
def get_successors(self, state):
# 상하좌우 이동 가능한 상태 반환
successors = []
for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
nx, ny = state[0]+dx, state[1]+dy
if 0 <= nx < 3 and 0 <= ny < 3:
successors.append(('move', (nx, ny), 1))
return successors
problem = MazeProblem()
path, cost = a_star_search(problem)
print(f"최적 경로: {path}, 총 비용: {cost}")위 코드를 실행하기 위해서는 파이썬 3.x 환경이 필요하며, 별도의 외부 라이브러리 설치 없이 기본 라이브러리만으로 작동한다. 만약 IndexError가 발생한다면 get_successors 함수 내의 경계 값 체크(0 <= nx < 3) 부분이 맵의 크기와 일치하는지 확인해야 한다. 맵 크기를 늘릴수록 visited 집합의 크기가 커지며 메모리 사용량이 증가하는 것을 관찰할 수 있을 것이다.
탐색의 확장과 다음 단계
상태 공간 탐색은 단순한 경로 찾기를 넘어 체스나 바둑 같은 게임 AI의 적대적 탐색(Adversarial Search)으로 확장된다. 상대방의 최선의 수를 고려하는 미니맥스(Minimax) 알고리즘이나, 탐색 트리를 효율적으로 가지치기하는 알파-베타 가지치기(Alpha-Beta Pruning) 등이 그 예다. 또한, 상태 공간이 너무 거대해 완전한 탐색이 불가능할 때는 유전 알고리즘이나 시뮬레이티드 어닐링 같은 메타 휴리스틱(Meta-heuristic) 기법을 통해 ‘충분히 좋은’ 근사해를 찾는 방향으로 나아간다.
이번 과정을 통해 문제를 상태와 행동으로 쪼개어 바라보는 정식화의 힘을 배웠다. 결국 AI의 성능은 얼마나 정교한 휴리스틱을 설계하느냐, 그리고 얼마나 효율적으로 상태 공간을 관리하느냐에 달려 있다. 그렇다면 우리가 일상에서 내리는 수많은 결정 중, 무의식적으로 사용하고 있는 나만의 ‘휴리스틱 함수’는 무엇일까? 혹은 더 효율적인 경로를 찾기 위해 내가 포기하고 있는 ‘가지치기’는 없는지 생각해보게 된다.