1 탐색 (Lecture Note #4) 인공지능 이복주 단국대학교 컴퓨터공학과 Modified from the slides by SciTech Media

2 Slide made by Bogju Lee Outline  탐색  문제 해결  상태 공간  탐색 기법  휴리스틱 기법 –Hill Climbing –Best-First Search –Beam Search –A* Search  게임 트리 기법  알파베타 탐색 문제  제약 조건 만족 문제

3 Slide made by Bogju Lee 게임 트리 탐색  컴퓨터 게임의 역사 –19 세기 : Charles Babbage, 해석 기계에서 서양장기 프로 그래밍 구상 –1950 년대 : Shannon, Turing, 서양장기의 컴퓨터적 알고 리즘 구체적으로 생각 –1960 년대 : Samuel, 프로그램 실제 작성  게임을 위한 탐색 – 지금까지의 탐색과 다른 점 : 다수 (2 인 ) 가 상호 배타적인 환 경에서 승리하기 위한 경로를 탐색 각자의 이익이 상대에게는 손해 – 같은 점 : 자신의 이익을 극대화 시키기 위한 결정 – 앞을 내다봄으로써 현재 상태의 선택을 결정한다 – 대부분의 게임에서 완벽한 평가함수의 정의가 불가능  휴 리스틱한 기준에 의한 추정치 만을 제공

4 Slide made by Bogju Lee 게임 트리 탐색  말패 (last-one-loses) 게임 – 임의의 수의 칩에서 시작, 1~3 개의 칩을 들어냄, 마지막 칩을 들 어낸 사람이 지는 게임 –4 개의 칩인 경우 탐색 트리 : 그림 2.13 –Note: state, operator 표현 – 실제 문제에서 전체 트리를 완성한 후 선택하는 것은 불가능

5 Slide made by Bogju Lee 게임 트리 탐색  예제 2.6: 말패 게임을 위한 평가함수 –4k+1 개의 칩이 남아 있게 하면 이김 –n=1,2,3 – 평가함수를 사용한 말패 게임 ( 그림 2.14)

6 Slide made by Bogju Lee 게임 트리 탐색  평가 함수 – 말패 게임은 특수한 경우 – 대부분의 다른 문제에서 완벽한 평가 함수 정의 힘듬  평가 함수 1 에서 –1 인 경우 –1: A 가 이기는 것 의미 –-1: B 가 이기는 것 의미 –0: 백중 (tie) –A 는 자녀 노드 중 평가 함수 큰 것 선택 ( 그림 2.15) –B 는 자녀 노드 중 평가 함수 작은 것 선택 A [c 1 ] f=0.8 [c 2 ] f=0.3 [c 3 ] f=-0.2

7 Slide made by Bogju Lee 게임 트리 탐색  두 단계 앞까지 고려한 경우 ( 그림 2.16) – 한 단계만 고려한다면 A 는 c1 (0.8) 선택 – 두 단계까지 고려한다면 A 가 c1 을 선택한 경우 B 는 c13 (-0.6) 선 택 –A 가 c3 를 선택한다면 B 는 c32 (-0.3) 선택 –A 는 c1, c3 중 어떤 노드를 선택해야 하나 ? A [c 1 ] f=0.8 [c 2 ] f=0.3 [c 3 ] f=-0.2 [c 11 ] f=0.9 [c 12 ] f=0.1 [c 13 ] f=-0.6 [c 21 ] f=0.1 [c 22 ] f=-0.7 [c 31 ] f=-0.1 [c 32 ] f=-0.3 최소화자 (B) 단계

8 Slide made by Bogju Lee 최소 최대 (minimax) 탐색법  최소최대 (minimax) 탐색법 – 최소화자 (minimizer) 와 최대화자 (maximizer) 로 구성되 어 있다고 가정하고 탐색해 나가는 전략 – 몇 수 앞을 내다보느냐가 탐색의 양에 영향 서양 장기 : 각 노드 당 평균 자녀 수 35 개, 한 게임 50 수  경 우의 수 – 최소최대법을 사용하면 탐색의 영역을 축소 가능 어떤 노드가 그 함수 값을 구하거나 확장하지 않아도 판단을 내리는데 지장이 없는 경우에 이 노드를 고려 대상에서 제외  - pruning ( 알파 - 베타 가지치기 )

9 Slide made by Bogju Lee 알파 베타 탐색 문제  알파베타 가지치기 ( 그림 2.17) – 최대화 노드에서 가능한 최소의 값 ( 알파 ) 과 최소화의 노드에서 가능한 최대의 값 ( 베타 ) 를 사용한 게임 탐색법 – 기본적으로 DFS 로 탐색 진행 – 어떤 최소화 노드의 베타값 (=-0.1) 이 자신보다 상위 ( 선조노드 ) 에 있는 어떤 최대화 노드의 알파값 (=0.2) 보다 작거나 같을 때, 이 최소화 노드는 가지치기 된다 ( 최소화 노드의 자식들이 cut 됨 ). [c 0 ]  =0.2 [c 2 ] f= -0.1 [c 1 ] f=0.2 [c 21 ] f= -0.1 [c 22 ][c 23 ] [c 11 ] f=0.2 [c 12 ] f=0.7 C 21 의 평가값 -0.1 이 C 2 에 올려지면 나머지 노드들 (C 22, C 23 ) 을 더 이상 탐색할 필요가 없음

10 Slide made by Bogju Lee 다음 법칙을 이용하여 아래의 알파 - 베타 탐색 트리를 완성하라 알파 베타 탐색 문제 가지치기가 일어나는 법칙 : 1. 어떤 최소화노드의 베타값 ( 예  =-3 ) 이 자신보다 상위 ( 선조노드 ) 에 있는 어떤 최대화 노드의 알파값 (  =0 ) 보다 작거 나 같을 때, 이 최소화 노드는 가지치기 된다. 2. 어떤 최대화노드의 알파값이 자신보다 상위 ( 선조노드 ) 에 있는 어떤 최소화 노드의 베타값보다 크거나 같을 때, 이 최 대화 노드는 가지치기 된다. 3. 최상위의 최대화노드의 알파값은 최종적으로 올려진 값 (backed-up value) 로 주어진다.

11 Slide made by Bogju Lee 제약 조건 만족 문제 (Constraint Satisfaction Problem)  n 개의 변수로 구성된 CSP 정의 – 유한하고 이산적인 영역들인 D 1, D 2, …,D n 으로부터 값을 취하 고 그 값들 간에는 제약조건 p k (x k1,x k2,…x kl ) 이 존재하는 문제 – 모든 제약 조건을 만족하도록 변수들에 적당한 값 지정 – 일종의 NP-complete 문제

12 Slide made by Bogju Lee  8-Queen 문제 ( 그림 2.18) – 여왕은 하나의 행이나 열에 놓이고 서로 대각선에 놓여도 안 됨 –x i : i 번째 행의 여왕이 놓일 수 있는 열 위치, x 1, x 2, …, x 8 – 여왕 x i, x j 의 위치사이의 제약조건 –i, j 의 열이 같으면 않 되고 행의 차이와 열의 차이가 같으면 않 됨 제약 조건 만족 문제 (Constraint Satisfaction Problem) x 2 = 7

13 Slide made by Bogju Lee 제약 조건 만족 문제 (Constraint Satisfaction Problem)  다른 CSP 문제 –Graph Coloring 문제 : 이웃 노드는 반드시 다른 색깔을 갖도록 색 칠  제약 조건 그래프 : 그림 2.19 –x 1 = {0, 1}, x 2 = {0, 1}, x 3 = {1} – 제약 조건 : x 1  x 2, x 1  x 3 –x 3 = 1, x 1 = 0, x 2 = 1

14 Slide made by Bogju Lee 제약 조건 만족 문제 (Constraint Satisfaction Problem)  탐색기법의 활용 – 공장자동화, 로보트의 경로계획 NASA 의 GPSS (ground processing scheduling system): 주어진 인원과 장비로 우주왕복선의 보수를 마치도록 적절한 일정을 탐색함 – 비행기 좌석예약 시스템 : 승객의 요구 최대 수용, 항공사의 이익 극대화 – 게임 chess - Deep Blue 바둑 - 아직 수준이 요원 – 경제학적 응용 : 다자가 공동의 공간에서 자신의 이익을 달성 하려는 경제적 문제 – 실제 게임의 경우 탐색의 양이 폭증  지식 활용에 대한 연 구가 많이 요구됨

15 Slide made by Bogju Lee Summary  게임 트리  최소 최대 탐색  알파 베타 탐색 문제  제약 조건 만족 문제