[인공지능] 5. Adversarial Search(적대적 탐색)

이 단원에서는 competitive multiagent environment, 즉 서로 경쟁적인 두 agent가 있는 상황을 다룬다. 이는 game으로 잘 알려져 있는 adversarial search problem을 말한다.

 

 

1. Game 

 1) game은 다음과 같은 요소들로 이루어져 있다. 

 

 - S0 : The initial state. 게임이 어떤 상황에서 시작되는지

 - Player(s) : 각 state에서 어느 player가 움직일 차례인지 알려줌

 - Actions(s) : 각 state에서 취할 수 있는 move들의 집합을 return

 - Result(s, a) : 어떤 state s에서 action a를 했을 때 result. transition model.

 - TerminalTest(s) : 게임이 끝났거나 한명이 졌을 때 true를 반환. 게임이 끝났는지 안 끝났는지를 판별. (게임이 종료된 그 state를 terminal state라고 부름)

 - Utility(s, p) : state s에서 player p에게 얼마나 유리한지를 정의하는 utility function( = objective function or payoff function)

 

 2) Game Tree

  : initial state, actions function, result function으로 트리를 만들어 search space를 표혐함. 

    정점은 게임의 state, 간선은 move를 의미한다. 이 tree는 각각 절반의 move가 합쳐져 있다. 즉 나 한번 상대방 한 번 번갈아가면서 move를 한다. 이런 move를 게임 용어로 ply라고 말한다. 

 

2. Optimal Decision in Games (Minimax Algorithm)

 

  * Minimax Value : game tree에서 optimal stategy는 minimax value를 통해 결정된다. 각 node의 minimax value는 각 player가 처음부터 끝까지 optimal하게 게임을 play했다고 가정했을 때의 utility이다. 선택권이 주어졌을 때, 나는 나에게 value가 maximum이 되는 state를 선호할 것이고, 상대방은 나의 value가 minmum되는 state를 선호할 것이다. 

 

MiniMax(s) = Utility(s)  if TerminalTest(s)

                  max MiniMax(Result(s,a))  if Player(s) = MAX( 이건 내 차례일 때 )

                  min MiniMax(Result(s,a))   if Player(s) = MIN( 상대 차례일 때 )

즉 내 차례일 때는 action을 취했을 때의 utility 값이 maximum하게 선택할 것이고

상대 차례일 때는 action을 위했을 때의 utility 값이 minimum하게 선택할 것이다. 

 

첫 번째, 나는 utility 값이 가장 큰 것을 선택할거다. 그래서 어떤 값이 가장 클까 하고 봤더니 아래에선 이미 상대가 내 utility가 가장 작아지는 state를 선택했을 것이다. 그래서 결국 내가 선택하게 되는 state는 상대가 각각의 action을 취했을 때 나올 수 있는 utility의 최솟값 중 가장 큰 값을 가진 state가 되는 것이다. 이러한 계산이 되면 A는 최소한 3의 이득을 볼 수 있는 a1의 action을 취할 것이다. B는 당연히 이 중에서 가장 작은 b1 action을 취할 것이고. 

 

다음은 minimax algorithm이다. Max-Value는 MinValue중에 최댓값, Min-Value는 MaxValue중에 최솟값이라고 생각하면 된다. 제일 먼저는 MAX turn이니까 Min-value 중 max 값을 return한다. 아래서 부터는 계속 반복이다. 

만약 terminal node, 즉 게임이 끝나는 node면 그 노드의 utility 값을 반환한다. 

 

이렇게 생긴게 마치 dfs같다. 

 

 

- Min이 optimal하게 게임을 play하지 않을 경우, optimal 할 경우보다 나에게는 더 이득이 된다.

- minimax algorithm은 현재 state에서 모든 minimax decision을 탐색하므로 complete dfs와 같다.

- 그래서 minimax search는 tree의 깊이에 따라 탐색해야 할 game의 states가 exponential 하다.

 

 

 * Multiplayer Games

 : 만약 둘이서 게임을 하는 것이 아니라 여러명이서 게임을 한다면, node에는 utility 값 하나 대신에 vector of value가 배정될 것이다. 이 vector는 각 player의 관점에서 이 state의 utility를 알려준다. 각 player의 차례에서 player들은 자신의 관점에서 가장 이득이 높은 state를 고르게 될 것이다. 

 

 

 

3. Alpha-Beta Pruning ( Alpha - Beta Search Algorithm )

: minimax 와 똑같이 작동하지만, final decision에 어차피 속하지 못할 branch들은 처음부터 가지치기를 해준다. 

만약 tree에 node n이 있다고 하자. 만약 player가 n보다 윗 쪽에서 더 좋은 선택지 m을 가지고 있었다면, n은 실제 play에서 선택될 일이 없을 것이다. 이럴 경우 우리는 n이 속한 노드들을 더이상 조사해보지 않고 prune할 수 있다. 어차피 저기서 제일 best한 경우를 선택해봤자 n이기 때문에! 

 

그래서 Alpha-beta pruning은 두개의 파라미터를 사용한다. 

  a(alpha) : 지금까지 쭉 탐색했던 것 중에서 max에게 가장 best한 값(highest-value) max는 이 값보다 작은 node는 아예 안본다.

  B(beta) : 지금까지 쭉 탐색했던 것 중에서 min에게 가장 best한 값(lowest-value) min은 이 값보다 큰 node는 아예 안본다.

Alpha-beta search는 남은 가지들을 가지치기 해나가며 계속해서 a와 B 값을 Update 해나간다.

 minimax와 달리 처음 시작할 때 직접 max_value를 호출한다. 이 때 최댓값은 -INT, 최솟값은 INF이다.

 

max_value에 들어오면 다른 것은 기존의 것과 같은데, 알파와 베타 값이 추가가 되었다.

v 값은 (이 Max노드에서 받은 min value중에 가장 높았던 minimax 값)과 (새로 찾은 min_value)중에 더 큰 것이 된다. 즉 v는 항상 min value 중 최댓값이다.

만약 이 v의 값이 기존 최솟값 B(위쪽 Min node에서 받아온, 이전까지의 min 노드에서 찾았던 가장 낮은 minimax 값) 보다 크면 어차피 min 단계에서 선택될 리가 없으므로 바로 가지치기, return해준다.

그리고 v가 B보다 작으면 최댓값인 a 값을 기존 a값과 새로운 값 v와 비교해서 더 이득이 큰 값으로 바꾸고 return 해준다. 

 

min_value를 보자. 

일단 v는 지금까지 받았던 max value의 최솟값과 새로 받을 max_value중에 더 작은 것을 선택한다. 즉 v는 max value 중 최솟값을 말한다. 이 v의 값이 , 앞서 찾았던 max의 최대 이득 a 보다 작으면 어차피 MAX가 선택을 하지 않을 것 이므로 return시켜 버린다. 그리고 만약 v가 a보다 크면 B에 MAX가 얻을 수 있는 가장 작은 이득을 update해주고 return 해준다. 

 

정리하자면 a값은 Max가 최소한으로 받고 싶어하는 이득이다. 이미 앞에서 a라는 이득을 볼 수 있음이 보장되는데, Min_Value를 통해 Max가 그 노드에서 받을 수 있는 최대 이득을 봤더니 a 보다 작다? 더이상 탐색을 할 필요가 없는 것이다. 즉 Min_Value에서 현재 탐색의 하한선을 지정해준 것이다. 

 

B는 Min이 허용할 수 있는 MAX의 이득의 최대값이다. 이미 앞에서 MAX가 B라는 더 작은 이득을 볼 수 있는 노드가 있는데, 굳이 Max_Value를 한 값이 B보다 큰 경우를 더 볼 필요는 없다. 즉 Min이 자신의 action을 정하기 위해 호출한 Max_Value에서 이득을 탐색할 때, 이 값을 넘으면 더 볼 필요가 없다고 상한선을 지정해 준 것 이다. 

 

(a) 우선 a=-INF, B=INF로 초기화하고 A에서 Max_value를 호출한다. 

    그러면 B에서 Min_Value를 호출하겠지? 이 때 B에서 첫 번째 노드를 탐색했더니 v=3이 되었고, 이 v의 값은 a보다 크므로 넘어간다. 그리고 B를 3으로 업데이트 해준다. 

(b) 다음으로 12인 노드를 탐색한다. v는 3과 12중 작은 값이므로 여전히 v = 3이 된다. 

(c) 다음으로 8인 노드를 본다. 마찬가지로 v=3이 그대로 유지되고 loop문을 다 돌았으므로 return v = 3 을 해준다. 

    이렇게 되면 B노드에서 바라본 가장 작은 값은 3이 된다. 

    A의 관점에서 본 B 노드의 이득은 3이다. 3이 -INF보다 크기 때문에 v=3이 되고, 이 때 v는 B의 값인 INF보다 작기 때문에 무사히 넘어온다. 그리고 a 값도 3으로 업데이트 된다. 

(d) 자 그럼 다음 노드 C를 살펴보자. A에서는 Min_value(C, 3, INF)를 호출했다. 그래서 C의 첫번째 노드를 가봤더니 return 2를 하여 C에게 돌아온다. 이렇게 되면 v=2로 업데이트가 되는데, 이 v의 값이 기존 a값인 3보다 작기 때문에, 이 node가 포함된 C노드는 더이상 볼 필요가 없어서 return 2를 하게 된다. (적어도 저기서 나오는 minimum value는 2보다 같거나 작을거기 때문에 어차피 선택 안될거라 2 return 해줘도 됨) 

(e) 이제 D 노드를 탐색해보자. Min_value(C, 3, INF)를 호출했다. D의 첫번째 노드에서 return 14가 되므로 v= 14이다. 이 값은 a보다 크므로 ok하고, 기존 B값인 INF보다 14가 더 작으므로 B를 14로 업데이트 해준다.

(f) 나머지 두 노드를 검사해보면 5일 때는 v = 5 가 되고, 이 값이 a보다 크므로 ok, 그리고 B도 14보다 5가 작으므로 5로 업데이트 해준다. 그런데 2일 때 v = 2가 되면 , 이 값이 a보다 작아져서 더이상 볼 필요가 없어진다. 그래서 그냥 그 상태에서 return 2를 해줘버린다. 

 

그럼 이제 A, B, C중 가장 큰 값인 3을 얻을 수 있는 B로 이동을 한다. 이 때 value는 v=3가 된다. 

 

 

- 이 alpha-beta pruning은 state들을 조사하는 순서에 영향을 많이 받는다. best한 경우 시간 복잡도는 O(b^(m/2))로 줄어든다. (원래는 O(b^m) ) Max level에서는 Minimax value가 큰 노드부터 , Min level 에서는 Minimax value가 작은 것부터 조사하면 제일 굿! 

 

- 과거 search에서 가장 best했던 move를 먼저 시도하는 것과 같은 dynamic move-ordering schemes을 추가하게 되면, 이론적으로 가장 효율적인 case에 근접할 수 있다. current move에서 어떤 path가 가장 best했는지에 대한 정보를 얻어내는 방법에는 iterative deepening search가 있다. 먼저 1 ply deep을 search하고 가장 best path를 기록한다. 그리고 한 칸 더 search할 때는 이전에 기록해둔 path를 이용해서 어떤 순서로 움직여야 하는지를 알려준다. 

 

 

 

 

 

 

4. Real-Time Decision

 

 - Minimax algorithm은 전체의 game search space를 생성해내고, alpha-beta algorithm은 그 중 많은 부분을 가지치기 할 수 있게 해준다. 하지만 alpha-beta 역시 여전히 search space의 일부분은 terminal states까지 탐색을 해봐야 한다. Terminal node가 나올 때까지의 깊이가 보통은 매우 깊기 때문에, 이 알고리즘은 그리 실용적이지는 않다. 

 

그래서 alpha-beta 를 두가지 방법으로 변형할 수 있다.

 

  ① utility function을 heuristic evaluation function으로 대체해서 사용할 수 있다. 

  ② 또는 terminal test 대신 Evaluation function을 이용한 cutoff test를 사용할 수 있다. 

 

 

 1) Evaluation functions

 

 game-playing program의 수행 능력은 evaluation function의 퀄리티에 영향을 받는다.

   ① evaluation function을 사용할 때, 실제 utility function에서의 terminal states의 순서와 달라지면 안된다.

   ② nonterminal state에서, evaluation function은 실제로 이길 확률과 강하게 연관되어 있어야 한다.

   ③ 계산이 지나치게 오래 걸리면 안된다.

 

* Features

  : 대부분의 evaluation function은 각 state의 features를 통해 state가 얼마나 좋은지를 계산한다. 이 때 feature는 state의 '상태'라고 보면 된다.  Feature를 사용하여 states의 카테고리를 분류하거나 같은 class들을 정의할 수 있다. 같은 feature를 갖는 states끼리 묶은 것이 카테고리이다. 

 

-> state가 어떤 상태(=feature)에 있고 이때 이 상태가 어떤 상태인지 분석해서 얼마나 유리한지 값 반환하는게 evaluation function

 

 

 * Weighted Linear Functions 

 : 대부분의 evaluation funtion은 각 feature에서의 기여도를 계산한 다음에 이들을 합쳐서 최종적인 value값을 찾는다.

 Feature와 weights는 game의 rule의 일부는 아니다. 그것들은 수세기 동안의 사람들의 경험에서 나온것이다. 사람과 달리 이러한 경험이 없는 게임에서는 machine learning을 이용해 evaluation function의 weight를 추정할 수 있다.

 

 

  2) Cutoff Strategies 

  : 대부분의 straightforward apporach는 depth limit을 설정하여 search의 양을 조절한다. 이도 마찬가지로 depth limit 까지만 search 해보고 cutoff한다.

  Cutoff Test는 어떠한 정해진 depth limit을 넘어가면 true를 return한다. depth limit는 할당된 시간 안에 답을 도출할 수 있도록 정한다. 

 

  더 강력한 접근 방식은 iterative deepening을 사용하면 된다. 시간이 다 되면, 프로그램은 그 때까지 탐색한 것 중 가장 깊은 곳에서 완료된 search에서 답(move)를 선택해 반환한다. 이러한 iterative deepening은 move ordering에도 도움을 준다. 

 

  이런 간단한 approach는 evaluation function의 대략적인 성질 때문에 error을 일으킬 수도 있다. (터미널 노드까지 가는 것이 아니니까 당연히 error가 날 수 밖에 ...)  

 

 

  *Quiescence Search (정적 탐색)

: evaluation function은 각 position들이 quiescent(정적)일 때, 즉 가까운 미래에서 evaluation 값이 큰 변동을 보일 가능성이 없을 때에만 적용 가능하다. 진행할 때마다 evaluation이 요동칠 경우, 해당 move가 정말 좋은 move인지 판단하기 어렵기 때문에 더 탐색할 필요가 있다.

 

이렇듯 Nonquiescent position이라면, quiescent position에 도달할 때까지, 즉 evaluation 값이 안정될 때 까지 탐색을 하면 된다. 이 때의 search를 quiescence search라고 부른다. 어떤 특정 유형의 이동만 고려함을 통해(chess라면 어떤 말을 잡는 경우의 move를 위주로), 해당 노드의 불확실성을 해결할 수 있다. 

 

 

  *Horizon Effect (지평선 효과)

 : 몇 수 더 가보면 이 state가 나에게 치명적으로 좋지 않다는 것을 알 수 있는데, 그것을 못 보는 상태를 말한다. 좋은지 나쁜지 체크하기 어렵거나, 좋다고 생각해서 선택했는데 알고보니까 안 좋은 경우들이 그러하다. 'delaying tactics'으로 일시적으로 피할 수 있다. 가장 제거하기 어려운 effect이다. 

보면 검정색 비숍은 결국 죽게 되어있다. 하지만 검은 pawn으로 이 죽음을 뒤로 미룰 수는 있다. 하지만 결국 죽게 되기 때문에 의미가 없다. 만약 그냥 알고리즘으로 돌린다면 분명 이 의미없는 희생을 하게 될 것이다. 

 

  *Singular Extension 

  : horizon effect를 방지하는 하나의 방법으로, 어떤 move가 다른 move보다 확연하게 좋아보인다면, depth limit에 따라 cut-off 하지 말고 끝까지 탐색해보는 것을 말한다. 어차피 singular extension이 일어나는 노드는 몇개 없을 것이기 때문에 tree를 deeper하게 만든다고 해서 시간 복잡도를 많이 늘리지도 않을 것이다.

 

  *Forward Pruning 

  : 주어진 node에서 몇개의 moves는 기준 없이 가지치기 해나간다. 그래서 모든 가능한 subtree를 탐색하는 것이 아니라 몇몇개만 search한다. 

 

   - Beam search : forward pruning의 응용버전으로, 각 ply 때마다 모든 possible moves를 고려하는 것이 아니라 n개의 best moves만 고려하여 그들만 탐색해나가는 것을 말한다.

 

 --> 하지만 이 approach는 가장 best한 move가 가지치기 당할 수도 있기 때문에 위험하기도 하다.

 

 

  * Table Lookup 

  : 대부분의 게임 playing program은 이 'table lookup'을 활용한다. 이게 뭐냐하면 처음 몇 수와 마지막 몇 수는 사전에 미리 searching 해서 좋은 수들을 저장해두고 사용하는 것을 말한다. 

 

  또한 컴퓨터는 policy를 만들어내서 endgame을 풀어나갈 수 있다. policy란 각각 가능한 모든 state에서 가능한 best move를 미리 계산해 놓는 것이다. 그러면 다시 다 계산할 필요 없이 그 때 그 때 best move를 찾기만 하면 된다.