블라인드 탐색은 어떠한 정보 없이 차례대로 탐색하는 것입니다. 내가 미로 안에 들어가서 푸는 것처럼 , 우선 모든 길을 둘러보면서 목적지를 찾는 것이지요. 복잡한 미로일수록 이를 푸는 시간은 기하급수적으로 늘어날 것입니다.
좀 더 효율적인 방법은 없을까요? 만약 컴퓨터가 아니라 사람이라면 문제를 어떻게 해결할까요?
1. 사람은 어떻게 문제를 해결할까요?
바둑이나 체스를 둘 때를 생각해 봅시다. 우리는 상대의 수를 보고 내가 낼 수 있는 모든 수를 살펴본 후, 가장 유리한 수를 하나 고르는 방법으로 게임을 하지는 않습니다. 모든 경우의 수를 생각하는 것은 매우 어려울뿐더러 시간과 정보가 부족하기 때문이지요. 그래서 사람들은 그동안 게임을 한 경험을 바탕으로 그냥 적당히, 어림짐작으로 유리할 것 같은 수를 둡니다. 최고라고 할 수 는 없지만 효율적인 해라고 말할 수 있습니다.
이처럼 탐색 과정에서 자신의 경험이나 사전 정보를 활용하는 방법을 ‘정보이용 탐색(Informed search)’이라고 합니다. 사용하는 정보 중 휴리스틱(Heuristic)이 많기 때문에 ‘휴리스틱 탐색’이라고도 합니다.
2. 휴리스틱은 무엇인가요?
휴리스틱이란 경험을 통해 얻은 지식이나 직감, 어림짐작을 의미합니다.
휴리스틱은 ‘찾다, 발견하다’를 뜻하는 그리스어 ‘Eurisko’에서 유래하였습니다. 휴리스틱이란 경험을 통해 얻은 지식이나 직감, 어림짐작을 의미합니다. 계속해서 시도하고 실패를 반복하는 것을 시행 착오라고 하지요? 시행 착오를 거쳐 점점 나아가는 것도 휴리스틱이라 할 수 있습니다. 즉 여러번 시도해보고 얻은 교훈을 통해 문제를 해결하는 것, 전에 와본 기억을 더듬어 길을 찾는 것 등이 휴리스틱을 이용한 문제 해결이라고 할 수 있습니다.
휴리스틱 탐색을 통해 얻은 답은 완벽한 답은 아니지만 그에 가까운 꽤 좋은 답입니다. 또 굳이 체계적인 판단을 할 필요가 없을 때 적당한 휴리스틱을 찾아 이용합니다.
예를 들어보겠습니다. 여러 분은 학교에 지각할 위기에 놓여있습니다. 여러분이 알고 있는 집에서 학교까지 가는 길은 위의 그림과 같이 하늘색, 보라색, 분홍색 길 세 가지입니다. 세 길 모두 오르막이나 내리막 길은 없으며 다른 조건은 비슷하다고 할 때 여러분이라면 어떤 길을 선택할 것인가요? 또 선택한 이유가 무엇인가요?
여러분은 모두 가운데 보라색 길을 골랐을 것입니다. 한 눈에 보기에도 짧은 길이기 때문입니다. 혹시 줄자나 도구를 이용해서 각 길의 거리를 측정한 친구가 있나요? 아마도 없을 것입니다. 길을 고른 이유를 묻는 질문에 대부분 ‘그냥!’, ‘딱 봐도 가까워 보여서요.’라고 대답할 거예요. 이처럼 깊은 생각을 하지 않고 순간의 감으로 판단하는 것을 ‘직관적’이라고 합니다. 이렇게 직관적으로 판단하는 것도 사람이 사용하는 휴리스틱입니다.
3. 휴리스틱 탐색을 체험하여 봅시다.
아까의 미로를 다시 한 번 통과하여 봅시다. 이번에는 아래의 스크래치 프로그램을 통해 ‘휴리스틱을 이용하여 길 찾기’를 해보겠습니다. 마찬가지로 여러분이 로봇이 되었다고 상상하여 봅시다. 가운데의 파란 점이 로봇인 여러분이고, 문제는 ‘미로에서 목적지●를 찾는 것’입니다. ‘Chapter 2 로봇의 길 찾기’와 달리 이번 길 찾기 문제에서는 목적지●를 숨기지 않고 보여줍니다. 아래의 스크래치 프로그램으로 ‘휴리스틱을 이용하여 길 찾기’를 해보세요. ‘시작하기’ 버튼으로 시작할 수 있고 방향키로 움직일 수 있습니다.
‘로봇의 눈으로 길 찾기’ 미로와 비교하였을 때, 어떤 것이 탈출하기 쉬웠나요? 목적지를 몰랐던 아까와는 달리 지금 여러분은 목적지의 방향을 알 수 있었습니다.
왼쪽의 그림처럼 목적지가 왼쪽에 있다면, 자연스레 왼쪽 방향의 길을 먼저 탐색하였을 것입니다. 만약 목적지가 오른쪽에 있다면, 오른쪽 방향의 길을 먼저 탐색했을 것입니다. 또한 여러분은 이 미로를 아까 한 번 풀어보았기 때문에 미로의 길이 익숙할 것입니다. 이 문제에서는 ‘나의 위치와 목적지까지의 거리’, ‘목적지에 가까이 가는 방향이 최적의 경로일 것이라는 직감’과 ‘미로를 이미 풀어본 경험’이 휴리스틱이 될 수 있습니다.
컴퓨터는 휴리스틱을 어떻게 정하고 사용할까요? 컴퓨터도 마법처럼 한 번에 문제를 해결할까요? 그렇지 않습니다. 컴퓨터는 정보를 숫자로 이해합니다. 그래서 인간의 경험이나 짐작을 컴퓨터가 이해할 수 있도록 만든 것 중 하나가 ‘평가 함수’입니다. 함수라는 말이 조금 어렵지요? 여기에서 함수는 어떤 식이라고 이해하고, 평가 함수를 ‘평가 점수’ 혹은 ‘평가값’라고 생각해도 괜찮습니다. 컴퓨터는 휴리스틱을 숫자로 바꾸어 점수를 매깁니다. 위의 길 찾기 문제에서 컴퓨터는 ‘목적지까지의 거리’를 측정하여 평가값으로 사용할 수 있습니다. 예를 들어 목적지까지의 거리를 줄이는 방향으로 나아가면 미로를 더 빨리 풀 수 있을 것이라고 기대할 수 있습니다.
4. 휴리스틱 탐색으로 문제를 해결하여 봅시다. - 언덕 오르기 알고리즘
휴리스틱 탐색에서는 문제에 따라 휴리스틱이 달라지기도 하고 휴리스틱을 활용하는 방법도 다양합니다. 그 중에서도 여기서는 가장 좋아 보이는 것을 탐색하는 ‘언덕 오르기 방법(언덕 오르기 알고리즘)’을 소개하고자 합니다. 언덕 오르기 알고리즘은 언덕 정상에 가고자 할 때 자연스럽게 올라가는 길로 향하는 것처럼 휴리스틱 평가값이 좋은 것 하나만을 선택해서 탐색하는 방법입니다.
※ 알고리즘은 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합을 뜻합니다. [천재학습백과 초등 소프트웨어 용어사전]
8퍼즐 문제를 컴퓨터의 휴리스틱 탐색-언덕 오르기 방법으로 해결하여 봅시다.
8퍼즐은 퍼즐을 위, 아래, 옆 방향으로 밀어서 맞추는 슬라이딩 퍼즐입니다. 초기 상태를 오른쪽의 목표 상태로 만드는 것이 문제라고 할 때, 목표 위치에 있는 퍼즐의 개수를 평가함수(점수)로 생각할 수 있습니다. 이번에는 목표 위치에 있는(제자리인) 퍼즐의 개수를 점수로 하여 풀어보겠습니다.
처음의 상태와 목표 상태를 비교한다면, 8개의 조각 중 [1, 2, 3, 8]이 목표 상태와 같습니다. 그러면 초기 상태의 평가값(점수)은 ❹입니다. 여기서 움직일 수 있는 블록은 (7, 8)입니다. (7)블록을 아래로 내리거나 (8)블록을 왼쪽으로 밀어낼 수 있습니다. 만약 왼쪽처럼 (7)블록을 움직인다면 평가값은 ❺가 되고, 오른쪽 처럼 (8) 블록을 움직인다면 평가값은 ❸이 됩니다. 언덕 오르기 알고리즘은 가장 좋아 보이는 것을 선택하는 것입니다. 그러므로 컴퓨터는 평가 값이 작은 것은 더 이상 탐색하지 않고, 평가 값이 큰 것만 더 탐색합니다. 그러므로 우리는 평가값이 5로 더 큰 첫번째 그림만 탐색하겠습니다.
마찬가지로 두 번째 확장에서 움직일 수 있는 블록은 (1, 4, 7)입니다. 그런데 (1)을 움직인 퍼즐은 이전에 이미 만들어 본 것이므로 더 탐색하지 않고 (4, 7)을 움직여 만든 블록만 탐색합니다. 두 개의 퍼즐 중 (4)를 움직인 것의 평가 값이 ❻이므로 이 블록을 더 확장하여 탐색합니다. 이러한 방법으로 계속 확장하면 결국 목표 상태에 도달하게 됩니다.
5. 휴리스틱 탐색은 언제나 좋을까요?
같은 문제라도 어떤 휴리스틱을 사용하느냐에 따라 결과가 달라질 수도 있습니다. 대표적인 예가 바로 ‘내비게이션’입니다. 어떤 내비게이션은 거리가 가장 짧은 것을 중요하게 생각하고, 어떤 것은 시간이 적게 걸리는 것을 더 중요하게 생각합니다. 또 교통상황을 고려할 수 도 있습니다. 어떤 휴리스틱을 얼만큼 더 중요하게 생각하느냐에 따라 경로와 도착 시간에 차이가 생기게 됩니다.
블라인드 탐색처럼 모든 경로를 순차적으로 찾아본다면 그 중 최고의 해를 찾을 수 있겠습니다. 하지만 복잡한 문제에서 모든 것을 살펴보는 것은 어마어마한 시간과 노력이 듭니다. 따라서 경험과 짐작으로 문제를 해결하는 휴리스틱 탐색은 효율적이라고 할 수 있습니다.
하지만 휴리스틱 탐색으로 얻은 답이 최고의 해는 아닐 수도 있습니다. 어림짐작하여 발견한 좋은 해이지만 아직 발견하지 못한 더 좋은 답이 있을 수 있는 것입니다. 예를 들어 언덕 오를 때를 생각하여 봅시다. 계속 높은 곳을 향해 나아가다가 주변에 더 이상 높은 곳이 없다면 그 곳이 정상이겠지요? 하지만 그림에서처럼 조금만 돌아가면 더 높은 언덕이 있을 수도 있습니다. 사실 이 남자는 오르막길1보다 내리막길2을 선택했어야 했습니다. 조금 돌아가더라도 정상에 오를 수 있는 길이니까요!
Think Good AI
휴리스틱 탐색으로 얻은 답은 최고의 해답이라고 확신할 수 없다. 그렇다면 실생활에서 휴리스틱 탐색만으로 결정을 내려서 안되는 상황에는 어떤 예들이 있을까?
퀴즈
휴리스틱 탐색으로 찾은 해는 언제나 최고의 해이다.
좋은 해는 맞지만, 최적의 해는 아닐 수도 있다.
휴리스틱은 탐색 공간이 큰 현실 세계의 문제를 해결할 때 적합하다.
문제에 따라 휴리스틱은 바뀔 수 있다.
휴리스틱이 바뀌면 탐색 성능도 차이가 난다.
참고문헌
1. 이건명, 「인공지능 튜링테스트에서 딥러닝까지」, 생능출판(2018)
2. 미래인재연구소, 초등학교 STEAM 교사용 교재 ‘로봇의 눈으로 길찾기’, 한국과학창의재단(2019)