탐색 문제란?
인공지능에서 많은 문제는 상태공간 탐색으로 표현할 수 있어요. 가능한 상황을 '상태', 한 상태에서 다른 상태로 옮기는 동작을 '연산자'로 두고, 시작 상태에서 목표 상태로 가는 연산자의 순서를 찾는 거예요. 길 찾기, 퍼즐 풀기, 로봇 경로 계획, 체스 같은 게임이 모두 여기에 해당해요. 기계가 '지능적으로' 문제를 푼다는 생각의 출발점은 인공지능의 정의와 튜링 테스트에서도 볼 수 있어요.
정보 없는 탐색
- 너비 우선 탐색(BFS): 시작점에서 가까운 상태부터 한 단계씩 넓혀 가요. 모든 이동 비용이 같으면 최단 경로를 보장하지만 메모리를 많이 써요.
- 깊이 우선 탐색(DFS): 한 갈래를 끝까지 따라간 뒤 되돌아와요. 메모리는 적게 쓰지만 최단 경로를 보장하지 않고 무한한 공간에서는 빠져나오지 못할 수 있어요.
- 균일 비용 탐색·다익스트라 알고리즘: 지금까지 온 비용 g(n)이 가장 작은 상태부터 확장해요. 다익스트라(1959)가 제시한 방법으로, 비용이 음수가 아니면 최단 경로를 찾아요.
A* 알고리즘
A*는 1968년 스탠퍼드 연구소의 피터 하트, 닐스 닐슨, 버트램 라파엘이 로봇 셰이키의 경로 계획 연구 과정에서 발표했어요. 각 상태 n을 다음 평가함수로 정렬해 가장 작은 것부터 확장해요.
f(n) = g(n) + h(n)
- g(n): 시작점에서 n까지 실제로 든 비용이에요.
- h(n): n에서 목표까지 남은 비용의 추정치(휴리스틱)예요. 지도에서는 직선거리, 격자에서는 맨해튼 거리를 흔히 써요.
- 허용성: h(n)이 실제 남은 비용을 절대 넘지 않으면(과대평가하지 않으면) A*는 최적 경로를 보장해요.
- 일관성: 인접한 두 상태 사이에서 h가 이동 비용보다 크게 줄지 않으면, 같은 상태를 다시 확장할 필요가 없어 효율이 좋아져요.
- h(n)=0이면 A*는 다익스트라 알고리즘과 같아지고, 휴리스틱이 정확할수록 확장하는 상태 수가 줄어요.
게임 탐색: 미니맥스
두 사람이 번갈아 두는 게임에서는 상대도 이기려고 한다는 점을 고려해야 해요. 미니맥스는 게임 트리의 각 끝(또는 일정 깊이)에서 평가값을 매긴 뒤, 내 차례(MAX)에는 가장 큰 값을, 상대 차례(MIN)에는 가장 작은 값을 위로 올려 보내 최선의 수를 골라요. 이론적 바탕은 폰 노이만의 1928년 미니맥스 정리이고, 클로드 섀넌은 1950년 논문에서 이 방법과 평가함수를 이용해 컴퓨터가 체스를 두는 방법을 제안했어요.
알파베타 가지치기
미니맥스는 트리 전체를 봐야 해서 깊이가 깊어지면 계산량이 폭발해요. 알파베타 가지치기는 이미 찾은 최선값(α: MAX가 보장받는 최소값, β: MIN이 보장받는 최대값)과 비교해 결과에 영향을 줄 수 없는 가지를 잘라내요. 결과는 미니맥스와 같으면서 계산량은 크게 줄어요. 커누스와 무어(1975)는 수의 순서가 이상적일 때 탐색해야 하는 노드 수가 대략 제곱근 수준으로 줄어든다는 것을 분석했어요.
한계와 이후 발전
- 상태 수가 지수적으로 늘어나는 '조합 폭발' 때문에 바둑처럼 큰 게임에서는 미니맥스만으로 한계가 있어요. 그래서 몬테카를로 트리 탐색과 신경망 평가를 결합한 방법이 나왔어요.
- A*는 열린 목록을 모두 메모리에 저장해야 해서 큰 문제에서는 IDA* 같은 메모리 절약형 변형을 써요.
- 좋은 휴리스틱과 평가함수를 설계하는 일 자체가 어렵고, 문제마다 전문 지식이 필요해요.
이 이론을 다룬 레포트·발표 자료는 캠퍼스다운 자료실의 '인공지능 탐색 알고리즘' 레포트 검색에서 찾아볼 수 있어요.
참고문헌
- von Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100, 295–320.
- Shannon, C. E. (1950). Programming a computer for playing chess. Philosophical Magazine, 41(314), 256–275.
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271.
- Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
- Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6(4), 293–326.