탐색과최적화 -I 충북대학교소프트웨어학과이건명 충북대인공지능 1
1. 상태공간과탐색 탐색 ( 探索, search) 문제의해 (solution) 이될수있는것들의집합을공간 (space) 으로간주하고, 문제에대한최적의해를찾기위해공간을체계적으로찾아보는것 탐색문제의예 선교사 - 식인종강건너기문제 틱 - 택 - 토 (tic-tac-toe) 8- 퍼즐문제 순회판매자문제 (traveling salesperson problem, TSP) 8- 퀸 (queen) 문제 해 ( 解, solution) 일련의동작으로구성되거나하나의상태로구성 상태공간과탐색 상태 (state) 특정시점에문제의세계가처해있는모습 세계 (world) 문제에포함된대상들과이들의상황을포괄적으로지칭 상태공간 (state space) 문제해결과정에서초기상태로부터도달할수있는모든상태들의집합 문제의해가될가능성이있는모든상태들의집합 초기상태 (initial state) 문제가주어진시점의시작상태 목표상태 (goal state) 문제에서원하는최종상태 충북대인공지능 2
상태공간그래프 (state space graph) 상태공간에서각행동에따른상태의변화를나타낸그래프 노드 : 상태 링크 : 행동 선교사 - 식인종문제 상태공간과탐색 m: 선교사 c: 식인종 일반적인문제에서는상태공간이매우큼 미리상태공간그래프를만들기어려움 탐색과정에서그래프생성 해 (solution) 초기상태에서목표상태로의경로 (path) image : Gillian Mosley 2. 맹목적탐색 맹목적탐색 (blind search) 정해진순서에따라상태공간그래프를점차생성해가면서해를탐색하는방법 깊이우선탐색 (depth-first search, DFS) 초기노드에서시작하여깊이방향으로탐색 목표노드에도달하면종료 더이상진행할수없으면, 백트랙킹 (backtracking, 되짚어가기 ) 방문한노드는재방문하지않음 i i i i i i 1 1 1 1 4 1 4 제거 2 2 3 2 3 2 3 5 충북대인공지능 3
맹목적탐색 8- 퍼즐문제의깊이우선탐색트리 루트노드에서현재노드까지의경로하나만유지 1 6 4 7 5 1 2 3 8 4 목표상태 1 6 4 7 5 1 4 6 4 1 4 2 3 1 8 4 8 3 2 6 4 6 4 8 3 2 1 4 7 1 4 6 5 2 3 1 8 4 8 3 2 6 4 2 3 6 8 4 6 4 6 7 4 1 5 8 3 2 1 4 7 1 4 6 5 1 2 3 8 4 8 3 2 6 4 8 6 3 2 4 2 3 6 8 4 2 3 6 8 4 2 8 6 4 3 6 4 5 1 7 6 7 4 1 5 6 7 4 1 5 8 3 2 1 4 8 1 3 2 4 7 4 6 1 5 7 1 4 6 5 1 2 3 8 4 맹목적탐색 너비우선탐색 (breadth-first search, BFS) 초기노드에서시작하여모든자식노드를확장하여생성 목표노드가없으면단말노드에서다시자식노드확장 i i i 1 2 1 2 3 4 5 충북대인공지능 4
맹목적탐색 8- 퍼즐문제의너비우선탐색트리 전체트리를메모리에서관리 1 6 4 7 5 1 6 4 7 5 1 4 1 6 4 7 5 6 4 1 4 2 3 1 8 4 1 4 1 6 7 5 4 8 3 2 6 4 6 4 8 3 2 1 4 7 1 4 6 5 2 3 1 8 4 2 3 1 8 4 2 8 1 4 3 1 4 5 7 6 1 6 7 5 4 2 8 1 6 3 7 5 4 8 3 2 6 4 2 3 6 8 4 6 4 6 7 4 1 5 8 3 2 1 4 7 1 4 6 5 1 2 3 8 4 2 3 4 1 8 2 8 1 4 3 1 4 5 7 6 1 6 7 5 4 2 3 1 8 6 7 5 4 1 5 6 7 4 2 8 1 6 3 7 5 4 8 3 2 6 4 8 6 3 2 4 2 3 6 8 4 2 3 6 8 4 2 8 6 4 3 6 4 5 6 7 4 1 7 1 5 6 7 4 1 5 8 3 2 1 4 8 1 3 2 4 7 4 6 1 5 7 1 4 6 5 1 2 3 8 4 맹목적탐색 반복적깊이심화탐색 (iterative-deepening search) 깊이한계가있는깊이우선탐색을반복적으로적용 a 깊이 0: a 충북대인공지능 5
맹목적탐색 반복적깊이심화탐색 (iterative-deepening search) 깊이한계가있는깊이우선탐색을반복적으로적용 a b c 깊이 0: a 깊이 1: a,b,c 맹목적탐색 반복적깊이심화탐색 (iterative-deepening search) 깊이한계가있는깊이우선탐색을반복적으로적용 a b c d e f g 깊이 0: a 깊이 1: a,b,c 깊이 2: a,b,d,e,c,f,g 충북대인공지능 6
맹목적탐색 반복적깊이심화탐색 (iterative-deepening search) 깊이한계가있는깊이우선탐색을반복적으로적용 a b c d e f g h i j k l m n o 깊이 0: a 깊이 1: a,b,c 깊이 2: a,b,d,e,c,f,g 깊이 3: a,b,d,h,i,e,j,k,c,f,l,m,g,n,o 맹목적탐색 반복적깊이심화탐색 (iterative-deepening search) 깊이한계가있는깊이우선탐색을반복적으로적용 a b c d e f h i j k l p q 목표상태 깊이 0: a 깊이 1: a,b,c 깊이 2: a,b,d,e,c,f,g 깊이 3: a,b,d,h,i,e,j,k,c,f,l,m,g,n,o 깊이 4: a,b,d,h,i,p,e,j,k,c,f,l,q 충북대인공지능 7
맹목적탐색 맹목적탐색방법의비교 깊이우선탐색 메모리공간사용효율적 최단경로해탐색보장불가 너비우선탐색 최단경로해탐색보장 메모리공간사용비효율 반복적깊이심화탐색 최단경로해보장 메모리공간사용효율적 반복적인깊이우선탐색에따른비효율성 실제비용이크게늘지않음 각노드가 10 개의자식노드를가질때, 너비우선탐색대비약 11% 정도추가노드생성 맹목적탐색적용시우선고려대상 맹목적탐색 양방향탐색 (bidirectional search) 초기노드와목적노드에서동시에너비우선탐색을진행 중간에만나도록하여초기노드에서목표노드로의최단경로를찾는방법 초기노드 목표노드 충북대인공지능 8
맹목적탐색 3. 정보이용탐색 정보이용탐색 (informed search) 휴리스틱탐색 (heuristic search) 언덕오르기방법, 최상우선탐색, 빔탐색, A * 알고리즘등 휴리스틱 (heuristic) 그리스어 Εὑρίσκω (Eurisko, 찾다, 발견하다 ) 시간이나정보가불충분하여합리적인판단을할수없거나, 굳이체계적이고합리적인판단을할필요가없는상황에서신속하게어림짐작하는것 예. 최단경로문제에서목적지까지남은거리» 현재위치에서목적지 ( 목표상태 ) 까지지도상의직선거리 충북대인공지능 9
정보이용탐색 휴리스틱비용추정의예 최단경로문제 현재위치에서목적지까지직선거리 8-퍼즐문제 8-퀸문제 제자리에있지않는타일의개수충돌하는회수 현재상태 목표상태 추정비용 : 4 정보이용탐색 언덕오르기방법 (hill climbing method) 지역탐색 (local search), 휴리스틱탐색 (heuristic search) 현재노드에서휴리스틱에의한평가값이가장좋은이웃노드하나를확장해가는탐색방법 국소최적해 (local optimal solution) 에빠질가능성 충북대인공지능 10
정보이용탐색 최상우선탐색 (best-first search) 확장중인노드들중에서목표노드까지남은거리가가장짧은노드를확장하여탐색 남은거리를정확히알수없으므로휴리스틱사용 제자리가아닌타일의개수 a4 1 6 4 7 5 b5 1 6 4 c3 1 4 d5 1 6 4 7 5 7 5 e 3 1 4 f 3 2 3 1 8 4 g4 1 4 h 3 8 3 2 1 4 i4 7 1 4 6 5 j3 8 3 2 1 4 정보이용탐색 빔탐색 (beam search) 휴리스틱에의한평가값이우수한일정개수의확장가능한노드만을메모리에관리하면서최상우선탐색을적용 Image : america.pink 충북대인공지능 11
A * 알고리즘 정보이용탐색 추정한전체비용 을최소로하는노드를확장해가는방법 노드 n 을경유하는전체비용 현재노드 n 까지이미투입된비용 g(n) 과목표노드까지의남은비용 h(n) 의합 : 남은비용의정확한예측불가 : 에대응하는휴리스틱함수 (heuristic function) 노드 n 을경유하는추정전체비용 정보이용탐색 8- 퍼즐문제의 A * 알고리즘적용 0+4 1 6 4 7 5 1+5 1 6 4 1+3 1 4 1+5 7 5 1 6 4 7 5 2+3 1 4 2+3 2 3 1 8 4 2+4 1 4 8 3 3+3 2 1 4 3+4 7 1 4 6 5 2 3 3+2 1 8 4 3+4 2 3 1 8 4 4+1 1 2 3 8 4 1 2 3 5+0 8 4 5+2 목표상태 1 2 3 7 8 4 충북대인공지능 12
4. 게임에서의탐색 게임트리 (game tree) 상대가있는게임에서자신과상대방의가능한게임상태를나타낸트리 틱 - 택 - 톡 (tic-tac-toc), 바둑, 장기, 체스등 게임의결과는마지막에결정 많은수 (lookahead) 를볼수록유리 자신 상대방 O O O O O O O O 자신 O O... O 게임에서의탐색 mini-max 알고리즘 (mini-max algorithm) MA 노드 자신에해당하는노드로자기에게유리한최대값선택 MIN 노드 상대방에해당하는노드로최소값선택 단말노드부터위로올라가면서최소 (minimum)- 최대 (maximum) 연산을반복하여자신이선택할수있는방법중가장좋은것은값을결정 6 자신 MA 3 6 5 상대방 MIN 5 3 6 7 5 8 자신 MA 5 4 3 6 6 7 5 8 6 상대방 MIN 5 6 7 4 5 3 6 6 9 7 5 9 8 6 판세평가값 자신 MA 충북대인공지능 13
게임에서의탐색 - 가지치기 (prunning) 검토해볼필요가없는부분을탐색하지않도록하는기법 깊이우선탐색으로제한깊이까지탐색을하면서, MA 노드와 MIN 노드의값결정 - 자르기 (cut-off) : MIN 노드의현재값이부모노드의현재값보다같거나작으면, 나머지자식노드탐색중지 - 자르기 : MA 노드의현재값이부모노드의현재값보다같거나크면, 나머지자식노드탐색중지 36 자신 MA 53 6 5 상대방 MIN 5 3 6 7 5 자신 MA 5 74 3 6 6 7 5 상대방 MIN 5 6 7 4 5 3 6 6 9 7 5 9 8 6 자신 MA 간단한형태의 - 가지치기예 게임에서의탐색 몬테카를로시뮬레이션 (Monte Carlo Simulation) 특정확률분포로부터무작위표본 (random sample) 을생성하고, 이표본에따라행동을하는과정을반복하여결과를확인하고, 이러한결과확인과정을반복하여최종결정을하는것 원안의샘플개수전체샘플의개수 4 images: www.fansshare.com, www.casinonewsdaily.com 충북대인공지능 14
몬테카를로트리검색 몬테카를로트리탐색 (Monte Carlo Tree Search, MCTS) 현재상태 트리정책 기본정책 Coulom (06) Chaslot, Saito & Bouzy (06) Slide from Sylvain Gelly 몬테카를로트리검색 현재상태 트리정책 기본정책 Slide from Sylvain Gelly 충북대인공지능 15
몬테카를로트리검색 현재상태 트리정책 기본정책 Slide from Sylvain Gelly 몬테카를로트리검색 현재상태 트리정책 기본정책 Slide from Sylvain Gelly 충북대인공지능 16
몬테카를로트리검색 현재상태 트리정책 기본정책 Slide from Sylvain Gelly 몬테카를로트리검색 현재상태 Kocsis & Szepesvari (06) Slide from Sylvain Gelly 충북대인공지능 17
몬테카를로트리검색 현재상태 Slide from Sylvain Gelly 몬테카를로트리검색 현재상태 Slide from Sylvain Gelly 충북대인공지능 18
게임에서의탐색 몬테카를로트리탐색 (Monte Carlo Tree Search, MCTS) 탐색공간 (search space) 을무작위표본추출 (random sampling) 을하면서, 탐색트리를확장하여가장좋아보이는것을선택하는휴리스틱탐색방법 4 개단계를반복하여시간이허용하는동안트리확장및시뮬레이션선택 (selection) 확장 (expansion) 시뮬레이션 (simulation) : 몬테카를로시뮬레이션 역전파 (back propagation) 선택확장시뮬레이션역전파 이긴횟수게임수 ( 방문수 ) image : wikipedia 게임에서의탐색 몬테카를로트리탐색 cont. 선택 (selection) : 트리정책 (tree policy) 적용 루트노드에서시작 정책에따라자식노드를선택하여단말노드까지내려감 승률과노드방문횟수고려하여선택 UCB(Upper Confidence Bound) 정책 : UCB 가큰것선택 보모노드, : 자식노드 : 방문횟수 : 점수 ( 이긴횟수 ) 활용 (exploitation) 탐험 (exploration) 선택 확장 시뮬레이션 역전파 이긴횟수게임수 ( 방문수 ) 충북대인공지능 19
게임에서의탐색 몬테카를로트리탐색 cont. 확장 (expansion) 단말노드에서트리정책에따라노드추가 예. 일정횟수이상시도된수 (move) 가있으면해당수에대한노드추가 시뮬레이션 (simulation) 기본정책 (default policy) 에의한몬테카를로시뮬레이션적용 무작위선택 (random moves) 또는약간똑똑한방법으로게임끝날때까지진행 역전파 (backpropagation) 단말노드에서루트노드까지올라가면서승점반영선택확장시뮬레이션역전파 이긴횟수게임수 ( 방문수 ) 몬테카를로시뮬레이션 몬테카를로트리검색 몬테카를로트리탐색 cont. 동작선택방법 가장승률이높은루트의자식노드선택 가장빈번하게방문한루트의자식노드선택 승률과빈도가가장큰루트의자식노드선택없으면, 조건을만족하는것이나올때까지탐색반복 자식노드의 confidence bound 값의최소값이가장큰, 루트의자식노드선택 선택확장시뮬레이션역전파 이긴횟수게임수 ( 방문수 ) 충북대인공지능 20
몬테카를로트리검색 몬테카를로트리검색 cont. 판의형세판단을위해휴리스틱을사용하는대신, 가능한많은수의몬테카를로시뮬레이션수행 일정조건을만족하는부분은트리로구성하고, 나머지부분은몬테카를로시뮬레이션 가능성이높은수 (move) 들에대해서노드를생성하여트리의탐색폭을줄이고, 트리깊이를늘리지않기위해몬테카를로시뮬레이션을적용 탐색공간축소 선택확장시뮬레이션역전파 이긴횟수게임수 ( 방문수 ) 알파고의탐색 알파고의몬테카를로트리검색 바둑판형세판단을위한한가지방법으로몬테카를로트리검색사용 무작위로바둑을두는것이아니라, 프로바둑기사들을기보를학습한확장정책망 (rollout policy network) 이라는간단한계산모델을사용 0.6 정책망 : 가능한착수 ( 着手 ) 들에대한선호확률분포 가치망 : 바둑판의형세값을계산하는계산모델 확률에따라착수를하여몬테카를로시뮬레이션을반복하여해당바둑판에대한형세판단값계산 별도로학습된딥러닝신경망인가치망 (value network) 을사용하여형세판단값을계산하여함께사용 Image : Nature 충북대인공지능 21
알파고의탐색 알파고의몬테카를로트리검색 많은수의몬테카를로시뮬레이션과딥러닝모델의신속한계산을위해다수의 CPU 와 GPU 를이용한분산처리 Image : Nature 게임에서의탐색 충북대인공지능 22