■ 인공지능 탐색과 최적화 강의자료: 맹목적 탐색과 휴리스틱 탐색, A*, 미니맥스와 알파베타, 몬테카를로 트리 탐색 간략정리
인공지능의 탐색과 최적화를 다룬 47장 분량의 강의자료입니다. 선교사와 식인종 강 건너기 문제로 상태 공간의 개념을 소개하고 틱택토, 순회 판매자 문제, 루빅스큐브, 8퍼즐, 8퀸을 탐색 문제의 예로 제시합니다. 깊이 우선 탐색, 너비 우선 탐색, 반복적 깊이 심화 탐색, 양방향 탐색 등 맹목적 탐색의 원리와 장단점을 비교하고, 언덕 오르기와 최상 우선 탐색, 경로 비용을 함께 고려하는 A* 탐색 등 휴리스틱 탐색을 8퍼즐 예시로 설명합니다. 게임 트리에서의 미니맥스 알고리즘과 알파베타 가지치기, 몬테카를로 시뮬레이션과 다중 슬롯머신 문제, UCT 값을 이용한 선택, 확장, 평가, 역전파의 몬테카를로 트리 탐색과 알파고의 활용을 다룹니다. 백트래킹 기반의 제약조건 만족 문제, 조합 최적화와 함수 최적화, 회귀 문제의 최소 평균제곱법과 경사하강법으로 마무리합니다.
■ 인공지능 탐색과 최적화 강의자료: 맹목적 탐색과 휴리스틱 탐색, A*, 미니맥스와 알파베타, 몬테카를로 트리 탐색 필수만 빠르게 발췌.
0+4 1+5 1+3 1+5 2+4 2+3 2+3 3+3 3+4 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 7 6 5 2 3 1 8 4 7 6 5 3+2 3+4 4+1 5+0 5+2 목표 상태 8-퍼즐 문제의 A* 알고리즘 적용 만일 휴리스틱 함수 모 ≤ , A* 알고리즘은 항상 최적해를 갖게 됨 - 결 을 얼마나 잘 추정하는 지에 따라 A* 알고리즘의 성능 결정
Search in Game Game State Tree : 상대가 있는 게임에서 자신과 상대방의 가능한 게임 상태 - 자신의 순서에서는 최대한 유리한 상태 선택, 상대방 순서에서는 최대한 불리한 상태 선택 - 많은 수를 볼 수록 유리 자신 상대방 자신 O X O X O X X O X X O X O X O O X X X O X X O X X O . . .
1. Mini-Max 알고리즘 MAX 노드 : 자신에 해당하는 노드로 자기에게 유리한 최대값 선택 MIN 노드 : 상대방에 해당하는 노드로 최소값 선택 깊이 우선 탐색으로 단말 노드부터 위로 올라가면서 최소(minimum)-최대(maximum) 연산을 반복하여 자신이 선택할 수 있는 방법 중 가장 좋은 것은 값을 결정 자신 MAX 자신 MAX 자신 MAX 상대방 MIN 상대방 MIN 5 6 7 4 5 3 6 6 9 7 5 9 8 6 판세 평가값 6 3 6 5 5 4 3 6 6 7 5 8 6 5 3 6 7 5 8
2. α-β Pruning Mini-Max 알고리즘에서 모든 트리를 탐색할 필요가 있을까? 9 30 11 12 자신 MAX 상대방 MIN A B C D E F G 어떤 노드에 값이 있다면 Max node에서는 하한 값, Min node에서는 상한 값 역할 Alpha : Maximum value found so far Beta : Minimum value found so
검토할 필요가 없는 부분은 탐색 제외 - 깊이 우선 탐색으로 MAX 노드와 MIN 노드의 값을 결정하면서 cut-off : MIN 노드의 현재값이 부모노드의 현재 값( value)보다 작거나 같으면, 나머지 자식 노드 탐색 중지 cut-off : MAX 노드의 현재값이 부모노드의 현재 값( value)보다 같거나 크면, 나머지 자식 노드 탐색 중지 자신 MAX 자신 MAX 자신 MAX 상대방 MIN 상대방 MIN 5 6 7 4 5 3 6 6 9 7 5 9 8 6 5 7 5 4 5 3 3 6 6 3 3 6 6 7 7 6 5 5 5 α cut-off
Where alpha, beta cut-off? MAX MIN MAX MIN
Where alpha, beta cut-off? MAX MIN MAX MIN α Cut-off β Cut-off
3. Monte Carlo Tree Search Monte Carlo Simulation : 난수를 이용하여 함수의 값을 확률적으로 계산하는 알고리즘 예) 계산 - Uniform Distribution으로 정사각형내 점 선택 - 충분히 반복한 후 Mini-Max 알고리즘은 최적의 해를 찾을 수 있으나 모든 게임 트리를 탐색 Alpha-Beta Prunning은 효율적이지만 여전히 대부분의 게임 트리 탐색 필요
오늘의 추천자료! 빠르고 간편하게 해보세요! ⚡
인공지능 탐색과 최적화 강의자료: 맹목적 탐색과 휴리스틱 탐색, A*, 미니맥스와 알파베타, 몬테카를로 트리 탐색
■ 인공지능 탐색과 최적화 강의자료: 맹목적 탐색과 휴리스틱 탐색, A*, 미니맥스와 알파베타, 몬테카를로 트리 탐색 소소정보
문제 공간을 효율적으로 뒤지는 방법
인공지능의 많은 문제는 거대한 상태 공간에서 좋은 해를 찾는 탐색 문제로 바꿀 수 있습니다. 이 강의자료는 맹목적 탐색부터 몬테카를로 트리 탐색, 경사하강법까지를 정리했습니다.
자료 구성
- 상태 공간과 탐색 문제
- 맹목적 탐색
- 휴리스틱 탐색과 A*
- 미니맥스와 알파베타 가지치기
- 몬테카를로 트리 탐색
- 제약조건 만족과 최적화
탐색 방법 비교
| 방법 | 특징 |
|---|---|
| 너비 우선 탐색 | 최적해 보장, 메모리 사용이 급증 |
| A* 탐색 | 현재까지 비용과 남은 추정 비용의 합으로 선택 |
| 몬테카를로 트리 탐색 | 랜덤 플레이 결과로 UCT 값 갱신 |
인공지능 탐색 알고리즘과 게임 트리, 최적화 기법
- 알고리즘마다 단계별 예제 그림으로 동작을 보여 줍니다.
- 인공지능, 알고리즘, 기계학습 기초 수업의 학습에 참고하기 좋습니다.
- 알파고 사례로 이론과 실제 응용을 연결합니다.
■ 인공지능 탐색과 최적화 강의자료: 맹목적 탐색과 휴리스틱 탐색, A*, 미니맥스와 알파베타, 몬테카를로 트리 탐색 참고문헌
nan
