준비 단계: 탐색이란 무엇일까?
여러분, 미로 찾기를 하거나 복잡한 퍼즐을 맞출 때 머릿속으로 어떤 생각을 하나요?
「이쪽으로 가면 막히려나? 저쪽으로 가면 정답이 나올까?」 하며 여러 가지 길을 미리 상상해 봅니다.
💡 컴퓨터 과학에서의 「탐색(Search)」
인공지능도 우리와 비슷합니다. 현재 상태에서 연산자를 적용해 다음 상태를 만들어 보며 목표 상태(정답)에 이르는 경로를 체계적으로 찾아 나가는 과정을 바로 「탐색」이라고 부릅니다. 경우의 수를 하나도 빠짐없이 전개해 보는 방법도 있고, 가망 있어 보이는 쪽부터 확인해서 전개할 양을 줄이는 방법도 있습니다.
상태 (State)
퍼즐의 현재 모습이나 미로에서의 현재 내 위치를 뜻합니다.
연산자 (Operator)
상태를 변화시키는 행동입니다. (예: 빈칸을 왼쪽으로 이동하기)
목표 (Goal)
우리가 최종적으로 도달하고자 하는 정답 상태를 말합니다.
1단계: 8-퍼즐 규칙 알아보기
본격적인 탐색 실습을 시작하기 전에, 우리가 풀게 될 8-퍼즐이 어떤 게임인지 3가지 핵심 규칙을 알아볼까요?
1. 기본 구성
가로 3칸, 세로 3칸의 게임판에 1부터 8까지의 숫자 타일과 1개의 빈칸이 있습니다.
2. 이동 방법
빈칸과 상하좌우로 맞닿아 있는 타일만 빈칸 쪽으로 밀어서 이동시킬 수 있습니다. 대각선으로는 옮길 수 없습니다.
3. 최종 목표
숫자를 1부터 8까지 순서대로 맞추고, 마지막 오른쪽 아래를 빈칸으로 만들면 퍼즐 완성입니다.
2단계: 8-퍼즐 직접 탐색해 보기
지금 이 배치의 어림값
어림값은 목표까지 얼마나 남았는지 짐작한 값입니다. 판을 한 번 움직일 때마다 어떻게 변하는지 보세요.
타일을 옮기면 어림값이 어떻게 변하는지 여기에 적습니다.
실습 방법
- 목표 상태: 숫자 1부터 8까지 순서대로 정렬하고, 마지막을 빈칸으로 만드는 것입니다.
- 직접 풀기: 빈칸 주변의 숫자를 클릭하여 상하좌우로 이동시켜 보세요. 인간의 탐색 과정을 경험할 수 있습니다.
- AI가 풀기: 버튼을 누르면 인공지능이 A* 알고리즘(휴리스틱 탐색)을 사용하여 브라우저 멈춤 없이 순식간에 최단 경로를 계산해 냅니다.
3단계: 핵심 원리 및 코드로 이해하기
인공지능은 퍼즐의 타일을 직접 만질 수 없습니다. 대신 숫자 데이터를 사용하여 현재 퍼즐의 「상태」를 기억하고 연산합니다. 가장 대표적인 방법은 2차원 리스트(배열)를 사용하는 것입니다.
# 8-퍼즐의 상태를 파이썬 2차원 리스트로 표현하기
# 0은 빈칸을 의미합니다!
initial_state = [
[1, 2, 3],
[4, 0, 5], # 정중앙에 빈칸(0)이 있는 상태
[7, 8, 6]
]
# 연산자: 빈칸(0)의 위치를 기준으로 상, 하, 좌, 우 위치값 변경
# 목표 상태인지 확인:
goal_state = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 0]
]
if initial_state == goal_state:
print("퍼즐을 완성했습니다!")
else:
print("계속 탐색하세요.")4단계: 오해와 진실
「인공지능은 퍼즐을 보면 직감적으로 한 번에 딱! 정답을 알아내는 거 아닌가요?」
아닙니다. 인공지능에게 사람과 같은 「직감」은 없습니다.
인공지능은 빈칸을 위로 움직였을 때의 상태, 아래로 움직였을 때의 상태를 마치 나뭇가지가 뻗어나가듯 「탐색 트리(Search Tree)」로 미리 그려 보고, 그중 정답으로 가는 길을 찾는 매우 체계적인 연산을 수행합니다.
확인 퀴즈
배운 내용을 확인해 봅시다.