인공지능 탐색과 최적화 강의자료: 맹목적 탐색과 휴리스틱 탐색, A*, 미니맥스와 알파베타, 몬테카를로 트리 탐색 글자 크게 보기

※ 1페이지는 원본 그대로 미리 볼 수 있어요. 구매하면 원본 파일 전체를 바로 다운로드할 수 있어요.

■ 인공지능 탐색과 최적화 강의자료: 맹목적 탐색과 휴리스틱 탐색, 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*, 미니맥스와 알파베타, 몬테카를로 트리 탐색 참고문헌

nan