AI의 탐색 방법론

상태 공간과 맹목적 탐색

상태공간과 탐색

어떤 문제를 알고리즘적으로 해결하기 위해서는 문제의 정보를 정형화된 형식으로 표현해야 한다. 여기서 문제와 해를 상태의 개념으로 표현하고 이를 이용하는 탐색을 통해 해를 찾을 수 있다.

다양한 문제들이 이러한 탐색 방법으로 해결될 수 있는데, 대표적인 예로 식인종 문제나 8-퍼즐 문제가 있다. 이들 문제들의 해는 일련의 동작으로 구성되거나 상태로 표현된다. 일련의 동작이 해인 경우에는 각 동작이 세계의 상태를 순차적으로 변화시켜 목표하는 상태에 도달하게 된다. 여기서 세계란 문제에 포함된 대상들과 이들이 처해있는 전체 상황을 포괄적으로 지칭하는 말이고, 상태는 특정 시점에 세계가 처해 있는 모습을 의미한다.

탐색문제는 상태 공간의 개념을 사용하여 설명할 수 있다. 상태 공간은 문제의 초기 상태로부터 도달할 수 있는 모든 상태의 집합 또는 문제의 해가 될 가능성이 있는 상태들의 집합이다. 초기 상태는 문제가 주어진 시점의 시작 상태이고 목표 상태는 문제에서 원하는 최종 상태를 말한다.

상태 공간에서 각 상태를 노드로 나타내고 어떤 상태에서 다른 상태로 변화시키는 행동이 방법이 있다면 해당 노드들 사이에 간선을 추가하여 표현한 그래프를 상태 공간 그래프라고 한다. 그래프가 사전에 주어져 있거나 탐색하는 과정 중에 그래프를 만들어야 한다.

맹목적 탐색

맹목적 탐색 방법들은 상태 공간 정보를 이용하지 않고 정해진 순서에 따라 상태 공간 그래프를 점차 생성해 가면서 해를 찾는다.

1. 깊이 우선 탐색

깊이 우선 탐색은 초기 상태의 노드에서 깊이 방향으로 점차 목표 상태의 노드를 찾아 들어가다가 더 이상 들어갈 수 없으면 되돌아 나와 아직 찾아보지 않은 다음 상태를 갖는 노드로 다시 깊이 방향으로 탐색을 하는 과정을 반복하는 탐색 방법이다. 이 방법을 흔히 DFS라고 말한다. 메모리 공간 활용이 효율적이지만 최단 경로 해를 보장하지 못한다는 특징이 있다.

2. 너비 우선 탐색

너비 우선 탐색은 초기 상태인 루트 노드에서 시작하여 모든 자식 노드를 확장하여 생성한 후, 목표 노드가 없으면 다시 이들 자식 노드를 확장하는 과정을 반복한다. 이 방법을 흔히 BFS라고 말한다. 메모리 공간 활용이 비효율적이지만 최단 경로 해를 보장한다는 특징이 있다.

3. 반복적 깊이 심화 탐색

반복적 깊이 심화 탐색은 깊이 우선 탐색과 너비 우선 탐색의 장점 모두를 취하고 있다. 이 탐색 방법은 깊이 한계가 있는 깊이 우선 탐색을 반복적으로 적용하는 방법이다. 탐색 깊이 한계를 0에서 시작하여 점차 1씩 증가시켜 가면서 깊이 우선으로 탐색하여 최단 경로를 찾는 것을 보장한다. 그리고 기본적으로 깊이 우선 탐색이기 때문에 메모리 부담이 적다. 실제로 너비 우선 탐색에 비해 약 11% 정도의 노드를 더 많이 생성하는 정도에 불과하다.

4. 양방향 탐색

양방향 탐색은 초기 상태와 목표 상태에서 동시에 너비 우선 탐색을 진행하여 중간에 만나도록 하여 최단 경로를 찾는 방법이다. 양방향에서 동시에 내부에 있는 목표지점을 찾기 때문에 너비 우선 탐색과 같은 효과를 가지면서도 훨씬 적은 수의 노드를 생성하기 때문에 메모리 공간과 시간 측면에서 너비 우선 탐색보다 유리하다고 볼 수 있다. 추가적으로 탐색 시, 추론 방법을 소개하자면, 전향추론이란 초기지점에서 목표지점으로 찾는 것을 의미하고 후향추론이란 목표지점에서 초기지점으로 찾는 것을 의미한다.

정보이용 탐색과 게임탐색

정보이용 탐색

정보이용 탐색은 상태 공간에 있는 정보를 이용하여 탐색 효율을 높이는 탐색 방법이다. 이는 대부분 휴리스틱을 이용하기 때문에 휴리스틱 탐색이라고도 한다.

1. 휴리스틱

휴리스틱은 굳이 체계적이고 합리적인 판단을 할 필요가 없는 상황에서 신속하게 어림잡는 것을 말한다. 따라서 탐색에서 휴리스틱은 일반적으로 특정 상태에서 목표 상태까지의 거리에 대한 정보를 제공하는 것을 의미한다.

이러한 휴리스틱을 사용하는 탐색 방법으로는 대표적으로 언덕 오르기 방법, 최상 우선 탐색, 빔 탐색, A* 알고리즘 등이 있다.

2. 언덕 오르기 방법

언덕 오르기 방법은 현재 노드에서 확장 가능한 이웃 노드들 중에서 휴리스틱에 의한 평가 값이 가장 좋은 것 하나만을 선택해서 확장해 가는 탐색 방법이다. 현재 상태의 이웃 상태들만 고려하기 때문에 지역 탐색이라고도 하고 휴리스틱 탐색, 그리디 알고리즘이라고도 한다.

3. 최상 우선 탐색

최상 우선 탐색은 확장 중인 노드들 중에서 목표 노드까지 남은 거리가 가장 짧은 노드를 확장하여 탐색하려는 것으로 남은 거리를 휴리스틱을 사용하여 추정한다.

4. 빔 탐색

빔 탐색은 휴리스틱에 의한 평가 값이 우수한 일정 개수의 확장 가능한 노드 만을 메모리에 관리하면서 최상 우선 탐색을 적용하는 방법이다.

5. A* 알고리즘

A* 알고리즘은 전체 비용이 최소인 노드를 확장해 가면서 해를 찾는 방법이다. 노드 n에서 목표 노드까지 남은 비용 h(n)을 정확히 계산할 수 없기 때문에 휴리스틱 함수를 h^(n)을 사용하여 전체 비용 추정함수를 추정한다.

f(n) = g(n) + h(n) -> f^(n) = g(n) + h^(n)

게임 탐색

게임에서 게임 참여자들은 이기기 위해 매 순간 최선의 방법을 찾는다. 이러한 게임 문제도 탐색 문제로 간주될 수 있으며, 이를 해결하기위해 탐색방법을 사용한다.

1. Mini-max 게임 트리

게임에서 미리 수를 보는 것을 트리로 표현할 수 있는데 이 때, 루트 노트는 자신의 상태, 자식 노드들은 상대방의 게임 상태에 해당한다. 자신과 상대방의 게임 상태가 반복되면서 트리가 만들어지는데 이를 게임 트리라고 한다. 자신에 해당하는 최대값의 Max노드, 상대방에 해당하는 최소값의 Min노드가 있다.

2. 알파-베타 가지치기

이는 게임 트리에서 더 이상 자식 노드를 탐색해 볼 필요가 없을 때, 탐색을 그만두는 것을 의미한다. Min 노드의 현재 값이 부모 노드 값보다 작거나 같으면 알파-자르기, Max 노드의 현재 값이 부모 노드 값보다 크거나 같으면 베타-자르기를 할 수 있다.

3. 몬테카를로 트리 탐색

실제로 단말 노드의 형세를 판단하여 제대로 수치화 하는 것은 쉽지 않다. 따라서 무작위 적인 시뮬레이션에 의해 형세의 유리한 정도를 결정하여 게임 트리를 구성하는 알고리즘이 몬테카를로 트리 탐색이다. 이 알고리즘은 휴리스틱이 필요 없을 뿐만 아니라 성능이 뛰어나다는 것이 확인되었다. 실제로 수 많은 이슈화가 되었던 알파고도 이러한 몬테카를로 트리 탐색 방법을 사용한다.

Writer: Jae-Hwan Lee