[인공지능 4주차] Heuristics’ Consistency, Adversarial Search with Minimax

다음주 화요일은 임시공휴일이 되어버린 국군의 날(10/1)이기 때문에 수업이 없는 줄 알았는데, 수업을 진행하신단다. 대신 줌으로도 열어주시고, 녹강도 해주신다고. 목요일은 개천절(10/3)인데 이때는 없으려나..?

Sep 24(Tue)

지난 주에 우리는 optimal한 A* search를 위해서 admissibility가 보장되는 heuristic을 선택해야한다는 것을 배웠다. 그런데 해당 그래프는 사이클(cycle)이 없는 그래프였다. 과연 Cyclic한 그래프에서도 admissible한 휴리스틱은 여전히 optimal할까? (그러지 않으니 물어봤겠지?)

Consistency of Heuristics

상태 공간 그래프(state space graph)를 탐색하는 데 사이클이 존재한다면, 자칫하다간 그 사이클을 벗어나지 못하고 뺑뺑 제자리를 돌 수 있다. 탐색 트리(search tree)에서도 여러 노드의 자식 노드에서 같은 subtrees가 발생하면서 무한히 갇히거나 비효율적 탐색을 하는 일이 발생할 수도 있다.

그래서 방문한 노드는 다시 탐색하지 않는다는 원칙 하에, closed set으로 방문 노드를 관리해보자. closed set에 등록이 된 노드라면 건너뛰고, 신규 노드라면 closed set에 추가 후 방문한다는 약속을 세워보자. 과연 완전탐색, 그리고 최적의 탐색이 가능할까?

최초 S노드에서 G노드로 가는 최적 경로를 A* search를 통해 찾아보자. 이때 휴리스틱은 admissible하도록 goal까지의 최적 비용보다 작거나 같게 설정한다.

먼저 탐색을 하기 전에 시작 노드인 S를 closed set에 넣는다. 이후 S의 f값을 계산해보면 g+h=0+2=2이다. 이제 탐색을 A와 B로 할 수 있는데 B에서의 f가 더 작으므로 경로 SB를 탐색하자. 노드 B를 closed set에 넣고 탐색을 해보니 경로 SBC와 SBS가 4로 같다. (경로 SA는 f가 5로 이미 후순위로 밀린 상태이다.)

그런데 closed set에 S가 방문한 노드라고 기록돼있으니 SBS를 우선순위 큐에서 삭제하고(정확힌 애초에 집어넣지 않고) SBC를 탐색해보자. 노드 C를 closed set에 넣고 탐색해보니 경로 SBCG와 SBCB가 보인다. 둘 다 f가 6이므로, 기존에 뒷 순위로 밀렸던 f값 5의 경로 SA를 탐색하는 걸로 돌아가자.

노드 A를 closed set에 집어넣고 SA를 탐색해보니, SAS와 SAC가 가능한데 S와 C 모두 closed set에 방문했다고 기록되어있다. 따라서 이 두 노드는 모두 탐색할 가치가 없으므로 우선순위 큐에 집어넣지 않는다. 그렇담 우선순위 큐의 맨 앞에 있는 경로는 이제 누굴까.

경로 SBCG이다. 노드 G를 closed set에 집어 넣고 G를 확인해보니 goal node다. 도착했다! 우리는 경로 SBCG를 cost=6으로 찾아냈다. 그런데 최적 경로는 cost=5의 SACG이다. 어라 실패다? 왜 optimal한 값을 못 찾았을까?

순회가 가능한 상태 공간 그래프에서는 admissibility 말고도 Consistency를 고려해야한다. 어느 휴리스틱이 Consistent하다는 것은 모든 화살표(arc)에서 두 노드 간 휴리스틱의 차이가 실제 비용보다 작은지, 즉 각각의 화살표에서 admissible함을 의미한다. 수식으로 표현한다면

\[\text{Admissibility: }h(A)\le \text{cost(A to G)}\] \[\text{Consistency: }h(i)-h(j)\le \text{cost(i to j)}=g(j)-g(i), i\lt j\]

그리고 부등식을 살짝 옮겨서

\[\begin{align} \text{Consequences of consistency: }h(i)&\le h(j)+\text{cost(i to j)} \\&= h(j)+g(j)-g(i),\forall (i\lt j) \end{align}\]

모든 구간에서 consistency가 보장되는, 즉 f값이 단조증가(monotonic)할 경우 Consequences of consistency라 한다. 따라서 일반적으로 consistency가 연속적으로 보장되면, 모든 구간에서 admissibility가 보장된다고 볼 수 있다. 역명제는 성립하지 않는다.

cyclic한 state graph에서 consistency가 연속적으로 보장되면, A* search는 optimal하다! 앞선 예에서 노드 A의 h를 2로 조정하면 모든 구간에서 consistency가 보장된다. optimal한 경로 SACG도 잘 찾는다.

이를 그래프로 표현하자면 노드 N1과 N2에서의 h값과 g값을 각각 h(N1), h(N2), c(N1), c(N2)라 할 때,

\[c(N_2)-c(N_1)\ge h(N_1)-h(N_2), \forall (N_1\lt N_2)\]

하다는 것이다. 여기서 h는 admissibility와, c는 consistency와 관련이 있다. 또한 c는 누적 비용이므로 N2에서 더 크지만, h는 heuristic이므로 N1에서 더 크기에 부등식의 순서에 유의하자.

물론 일반적으로 relaxed problem에서 admissible한 휴리스틱은 consistent한 경향이 있다. 그러나 항상 그렇지 않으므로 ‘역명제는 성립하지 않는다’고 상술하였다.

Sep 26(Thu)

그런데 과연 똑똑한 agent가 우리만 있을까? 다른 agent(상대방)가 있다면? 그 상대방이 매우 똑똑해서 우리처럼 optimal한 경로를 찾는다면? 그 상대방과 서로 게임을 통해 겨뤄야한다면? 우리는 어떤 전략을 취할 수 있을까

Adversarial Search(적대적 탐색)

일단 게임에 대해 생각해보자. AI에서 말하는 Game이란 두 명 이상의 agent끼리 수행하는 과업이다. 시작지점 S에서 각각의 플레이어들 P가 행동 A를 통하여 다음 지점으로 이동한다고 formalization을 하면, S와 A에 의해 다음 S가 정해진다. 즉 현대 상태를 토대로 player는 다음 행동을 취한다.

게임은 여러 측면으로 분류되는데, 결과가 정해져있는지 혹은 확률적인지(deterministic or stochastic?), 각 agent가 관련한 정보를 완전히 소유하고 있는지(fully observable?), 몇 명의 플레이어가 참여하는지? 등이 있다.

특히 제로섬 게임인지(Zero sum?)가 상당히 중요한 기준이 되는데, 상대방의 이득이 내게는 불이익이 되기 때문이다. 이렇듯 둘 이상의 agent가 서로 적대적 관계로서 서로를 이기기 위한 탐색을 진행하는 것을 Adversarial Search(적대적 탐색)이라고 부른다.

제로섬 게임에서는 플레이어 A가 자신의 value를 maximize할 경우, 이는 상대방 B의 value를 minimize하는 것과 같다. 이와 대조되는 것이 General-Sum Games인데 이때 각 agent는 독립적인 효용(independent utilities)을 가지기에 서로 협력함으로써 팀 게임을 이끈다.

제로섬 게임(Zero-Sum Games)에서 승리하려면?

자주 연구되는 제로섬 게임으로는 체커, 체스, 바둑 등이 있다. 이 중 체커의 경우는 양측이 완벽한 전략으로 둔다는 가정 하에, 각 위치에서의 최종 결과가 100% 알려져 있다. 이를 solved라고 표현한다. 나머지는 아직 연구 중인듯. 아무튼 앞으로 생각하는 적대적 탐색, 그리고 제로섬 게임에서는 나와 상대방이 모두 optimal한 전략을 지녔다고 생각하자.

먼저 나 혼자 게임을 하는 종전의 상황을 생각하자. 무엇이 최선이었는가. 내 포인트(value)를 최대로 만드는 게 중요했다. 만약 우리가 모든 케이스를 계산할 수 있다면, 각 탐색에서의 마지막 상태(Terminal States)가 최대가 되는 경로를 택하면 됐었다. 즉 Single Agent에서 Non-Terminal States의 value는

\[V(s)=\max_{s'\in \text{children(s)}}V(s')\]

내 자식 케이스들이 취할 수 있는 value 중 최댓값을 내 value로 갖게 된다. 이 경로를 root node까지 올려보내면 최적의 경로가 나올 것이다!

그런데 Two Agents끼리 번갈아가며 움직인다면 어떨까? 나는 당연히 내 자식 케이스들 중 최선의 선택지로 이동할 것이고, 상대방은 자신의 자식 케이스들 중 최악의 선택지로 이동할 것이다. Opponent에겐 내 value를 minimize하는 것이 이득이기 때문이다. 수식으로 만들면

\[\text{Agent: }V(s)=\max_{s'\in \text{children(s)}}V(s')\] \[\text{Opponent: }V(s')=\min_{s\in \text{children}(s')}V(s)\]

여기서 이떄 V(s)와 V(s’)는 모두 내게 해당하는 value다. 전략이 나왔다!(어디?)

Minimax(미니맥스)

우리는 DFS를 통해 모든 terminal states의 values들을 알고 있다. 상대방도 optimal한 heuristic으로 모든 미래의 경우의 수를 다 내다보고 있을 것이다. 따라서 전략은 상대방은 항상 최솟값을 고를테니까, 우리는 그 최솟값이 다른 최솟값들보다 최대가 되도록 경로를 설정하는 것이다. 이처럼 추정되는 최대의 손실을 최소화하는 역설적인 기법을 Minimax라 한다!

다음과 같이 각 Max노드에서는 max-value()함수를, Min노드에서는 min-value()함수를 쓴다고 하자. 두 함수는 조건문으로 연결되어 value()라는 하나의 함수로 합쳐져있다.

만약 내 현재 위치가 max노드라면, max노드에서 max(v, value(successor))를 통해 자신의 자식 노드인 min노드들을 함수의 인자로 반환한다. value()에 적힌 ‘next agent’라 이 successor를 뜻한다.

이러면 3개의 조건문 중 마지막 MIN 노드에 해당하는 경우로 들어가는데, 다시 여기서는 자식인 MIN노드의 자식인, 즉 손주 MAX노드로 재귀를 넘기게 된다. 이렇게 해서 재귀가 마무리되면 최종 전략이 나오는 것이다!

물론 미니맥스는 상대가 완벽한 플레이어(perfect; without uncertainty)인 경우에 해당하고, 상대가 완벽하지 않다면 더 나은 경로를 찾을 희망도 존재하긴 한다.

Minimax는 exhaustive한 DFS를 사용하므로, 복잡도는 DFS와 같이 시간 O(b^m)과 공간 O(bm)이다. 알다시피 지수형의 시간 복잡도는 좋은 선택은 아니다. 그렇다면 어떻게 Minimax를 개선할 수 있을까? 우리가 방문하지 않아도 되는 노드는 없을까?

\(\alpha-\beta\) Pruning

MAX노드가 가지고 있는 현재 최적의 값(가장 큰 값)을 알파, MIN노드가 가지고 있는 현재 최적의 값(가장 작은 값)을 베타라 하자. MAX노드의 입장에서, 손주 노드의 값 v가 자신의 값 알파보다 작다면 자식인 MIN노드는 v보다 작거나 같은 값을 올려보낼 것이고, 따라서 자신은 해당 값으로 현재값 알파를 교체할 수 없게 된다. (뭔말알?)

반대로 MIN노드의 입장에서, 손주 노드의 값 v가 자신의 값 베타보다 크다면 자식인 MAX노드는 v보다 크거나 같은 값을 올려보낼 것이고, 따라서 자신은 해당 값으로 현재값 베타를 교체할 수 없게 된다. 이를 \(\alpha-\beta\) Pruning이라 하는데, 예를 살펴보자.

다음 Minimax 문제에서 우리가 살피지 않아도 되는 arc를 쳐내보자(prune). 방식은 Minimax의 DFS 방식을 따라간다.

먼저 a, b, c순서대로 쭉 들어갈 것이고, d를 탐색할 때 10보다 작은 6이므로, c와 d의 MAX노드에는 10이 기록된다. DFS이므로 다시 b를 타고 올라가 MIN에 10을 기록하고 e를 탐색해보자.

f를 탐색할 때 100이 나오므로 MAX노드에는 100이 기록된다. 여기서 주목! g에서 무슨 값이 나오든 해당 MAX노드에는 100 혹은 그 이상의 값이 기록될 것이다. 그런데 그 위 MIN노드에는 10이 기록되어 있으므로, e를 통해 무슨 값이 올라오든 받아들여지지 않는다. 따라서 우리는 엣지 g를 탐색할 필요가 없으므로 쳐내도 된다!(g would be pruned!)

다시 a를 타고 올라가서 직전 MIN노드의 최종 값인 10을 저장하고, h로 모험을 계속하자. i와 j를 타고 들어가니 3층의 MIN노드엔 1이 저장될 것이고, 곧이어 k를 탐색한 후 값이 2로 변경될 것이다. 이제 i를 타고 가서 2층의 MIN노드에는 2가 기록된다. 다시 여기서 주목!

l에서 무슨 값이 나오든 해당 MIN노드에는 2 혹은 그 이하의 값이 기록될 것이다. 그런데 그 위 MAX노드에는 10이 기록되어 있으므로, l을 통해 무슨 값이 올라오든 받아들여지지 않는다. 따라서 우리는 엣지 l을 탐색할 필요가 없으므로 쳐내도 된다!(l would be pruned!)

이해가 되는가? 해당 edge의 부모 노드와 조부모 노드의 관계를 비교하여 가지를 칠 수 있다는 결론에 이르게 된다. 이것이 알파-베타 푸르닝이다. 따라서 최적의 경로는 a-b-c이고, g와 l은 쳐내진다.

자 이게 알고리즘인데, 사실 정확히는 이해가 되지 않는다. 이해가 되는 부분까지만 작성하면

각 노드에서는 종전의 MINIMAX와 같이, successor를 인자로 넘겨서 value를 판단하게 한다. 이때 원래의 MAX노드가 지니던 beta값보다 v값이 크면, 어차피 기각될 것이므로 빠르게 값을 넘겨 나머지 edge에서의 판단을 건너뛴다.

마찬가지로 원래의 MIN노드가 지니던 alpha값보다 v값이 작으면, 어차피 기각될 것이므로 빠르게 값을 return해 나머지 edge에서의 판단을 건너뛴다. 근데 여기서 알파와 베타가 어떻게 올라오는지에 대한 관계식이 없어서, 조금 더 설명이 필요해보인다. 관련해서는 교수님께 여쭤보자.

알파-베타 가지치기는 탐색 순서에 영향을 받는다.(뭐 그래 보인다) 알파-베타 방식을 해도 MINIMAX 전략에는 영향이 없으며, 오히려 더 빠른 탐색이 가능하다(시간복잡도가 진짜 좋으면 O(b^(m/2))로 줄어듦). 또한 이것은 ‘계산할 것에 대해 계산하는’ meta-reasoning 방식이라고.

출처: 인공지능(COSE361) ㅇㅅㅅ 교수님