[AI 입문] 탐색(search)

트리, 그래프, 상태 공간 그래프(state space graph)

1. 탐색 방식의 종류

탐색 방식의 종류

A* 알고리즘은 게임 탐색이 아니다.

2. 맹목적 탐색 방법의 비교

• 깊이 우선 탐색
  • 장점: 메모리 공간 사용 효율적
  • 단점: 최단 경로 해 탐색 보장 불가
• 너비 우선 탐색
  • 장점: 최단 경로 해 탐색 보장
  • 단점: 메모리 공간 사용 비효율

3. 정보 기반 탐색(informed search)

• 휴리스틱 탐색(heuristic search)이라고도 부름
• 언덕 오르기 방법, 최상 우선 탐색, 빔 탐색, A*알고리즘 등

언덕 오르기 기법(hill climbing method)

• 현재 시점에서 휴리스틱 평가값이 가장 좋은 이웃 노드 하남나을 확장해 가는 탐색 방법
• 국소 최적점(local optima)에 빠질 위험 존재

언덕 오르기 기법

A* 알고리즘

• 추정한 전체 비용 f^(n)을 최소로 하는 노드를 확장해 가는 방법
• f(n): 노드 n을 경유하는 전체 비용
  • 이미 투입된 비용 g(n)과 목표 노드까지의 남은 비용 h(n)의 합

4. 게임 트리 탐색

• 상대가 있는 게임에서 자신과 상대방의 각각에 대해 가능한 게임 상태를 나타낸 트리
  • 틱-택-토(tic-tac-toe), 바둑, 장기, 체스 등
  • 게임 결과는 마지막에 결정
  • 많은 수(lookahead)를 볼 수록 유리

mini-max 알고리즘

• 현재 상태부터 지정된 깊이의 게임 트리를 제작 -> 현재 상태의 판세를 계산해서 가장 좋은 선택
• 단말 노드부터 위로 올라가면서 최소(minimum)와 최대(maximum) 연산을 반복하여 판세를 계산
• 끝까지 가야 할 수 있는 판세평가값으로서 아직 수가 많이 남았을 경우에는 사용하기 적절하지 않다.

 α-β 가지치기(pruning)

• 깊이 우선 탐색으로 제한 깊이까지 탐색하면서, MAX 노드와 MIN 노드의 값 결정