[AI] Adversarial Search (1)

이 글은 포스텍 이근배 교수님의 CSED442 인공지능 수업의 강의 내용과 자료를 기반으로 하고 있습니다.

인공지능 4주차 강의 요약이다.

인공지능 과목이 재밌긴 한데, 내용이 많아서 글 적기가 참 힘들다.

1. Adversarial Search

Adversarial, 즉 적대적 탐색은 두 개 이상의 agent가 서로 적대적인 관계를 가진다라고 가정했을 때의 탐색 방법을 말한다.

이때 이렇게 여러 agent가 서로의 이득을 취하기 위해 움직이는 상황을 ‘게임’이라고 하며, 이런 관점에서 adversarial search를 game search라 부르기도 한다.

우리가 이제껏 배웠던 탐색들은 모두 ‘나’의 행동만을 고려했다. 그러나 ‘게임’의 기본은 상대방의 행동을 고려하는 것이다.

따라서 이번 챕터에서는 상대방의 행동을 예측하고 그 결과를 활용하여 내 이익을 극대화 시키는 탐색 방법에 대해서 배운다.

Types of Games

우선 게임의 종류를 구분짓는 요소들을 몇 가지 정리해보자면 다음과 같다.

• Deterministic or stochastic (확률적)?
• One, two, or more player?
• Zero sum?
• Perfect information?

우선 Deterministic, two player, zero sum game에 대해서 배울 것이다.

Deterministic Game

우선 Deterministic game이란 무엇일까?

간단히 말해서, player의 action이 예측 가능한 결과를 낳는 게임을 말한다.

예를 들어 팩맨은 우리가 입력한 방향키대로만 움직인다.

반대로 stochastic game은 action이 예측 불가능한 결과를 낳는 게임을 말한다.

이에 대해서는 다음 챕터에서 배울 것이다.

Deterministic game을 formalize 하는 방법은 다양하나, PPT에서 제공하는 방법은 아래와 같다.

• States: $S$ (start at $s_0$)
• Players: P={1…N}
• Actions: A
• Transition Function: $S \times A \rightarrow S$
• Terminal Test: $S\rightarrow \lbrace t,f \rbrace$
• Terminal Utilities: $S \times P \rightarrow R$

여기서 Terminal Utilities란 state를 player가 선호하는 정도를 숫자로 표현한 값이다.

예를 들어 체스에서 승리는 1, 패배는 0, 비기는 것은 1/2 로 표현할 수 있다.

이 utility 값을 정하는 방법은 6번에서 배운다.

지금은 간단히 값이 클수록 좋은 state, 작을수록 나쁜 state라 생각하면 된다.

Zero-Sum Game

그 다음으로 Zero-Sum Game이란 무엇일까?

익히 들어본 표현이겠지만, 간단히 말해 내가 얻으면 상대가 잃고, 내가 잃으면 상대가 얻는 게임을 말한다.

다른 말로, agent들이 서로 반대되는 utility를 가지고 있다는 말이다.

이와 반대되는 개념으로 General Game이 있으나, 이번 챕터에서 다루진 않는다.

2. Minimax Search

팩맨 게임은 대표적인 Deterministic, two player, zero sum game 이다.

팩맨이 다음 행동을 결정하기 위해 탐색을 한다고 해보자.

그러면 위와 같이 두 가지 state를 탐색해낼 것이다.

이때, 계속 내 행동만 생각해서 탐색을 이어가면 될까?

아니다. 게임은 상대와 내가 번갈아서 행동을 하기 때문에 이제 상대편-유령-이 움직일 것을 생각해야 한다.

그래서 팩맨은 위 그림처럼 유령의 행동의 경우의 수를 생각해서 탐색을 했고, utility도 매겼다.

이때 utility를 어떻게 매긴 것인지는 중요하지 않다. 그냥 상대적인 크기 차이만 신경쓰면 된다.

여하튼 그럼 팩맨은 +8이 있는 우측으로 움직일까?

이는 섣부른 생각이다.

왜냐면 우측으로 움직이면 유령이 -10 state를 선택할 수도 있기 때문이다.

따라서 팩맨은 어떻게 유령이 행동할지 추측해서, 신중히 행동을 정해야 한다.

이때 상대가 무조건 합리적이게 나의 이득을 최소화시키는 방향으로 간다고 생각하는 것이 minimax search이고,

반대로 조금 비합리적이고 확률적인 방향으로 움직인다고 생각하는 것이 expectimax search이다.

우리가 우선 배울 것은 minimax search이다.

Minimax search란 항상 utility를 최대화 하는 방향으로 선택하는 MAX와, 항상 utility를 최소화 하는 방향으로 선택하는 MIN이 있다고 생각하는 탐색방법이다.

예를 들어 팩맨 게임에서 MAX는 팩맨이고, MIN은 유령이라고 보면 된다.

위 그림에서 팩맨이 minimax search를 한다면, 최종적으로 팩맨은 좌측으로 움직이는 것을 택할 것이다.

왜냐하면 좌측으로 움직이면 유령은 -8 state로 갈 것이고, 우측으로 움직이면 유령은 -10 state로 갈 것이기 때문에 좌측으로 움직이는 것이 그나마 낫기 때문이다.

구현법은 상당히 간단하다.

흐름만 알면 된다.

MAX는 MIN에게 턴을 넘기고, MIN이 반환하는 값 중 가장 큰 것을 택한다.

반대로 MIN은 MAX에게 턴을 넘기고, MAX가 반환하는 값 중 가장 작은 것을 택한다.

예제를 한번 풀어보자.

보다시피 MIN(역삼각형)은 탐색한 값들 중 가장 작은 것을 골랐다.

MAX는 그 MIN들이 반환한 값 (3,2,2) 중 가장 큰 값을 선택했다.

그런데 이걸 유심히 보다보면 의문이 들 수 있다.

두 번째 MIN은 어차피 탐색을 할 필요가 없지 않나? 어차피 2보다는 작은 걸 반환할텐데 라고.

만약 이런 생각이 들었으면, 오.. 상당히 감각이 뛰어난 사람이다.

실제로 두 번째 MIN은 이렇게 중간에 탐색을 중단해도 문제가 없다.

MIN은 3 이상을 선택할 것이고, 두 번째 MIN은 2가 나온 이상 2보다는 작거나 같은 걸 선택할 것이 자명하기 때문이다.

3. Alpha-Beta Pruning

위와 같은 기법을 alpha-beta pruning이라고 부른다.

갑자기 알파, 베타 라는 이름이 붙어서 뭔가 어려워보이는데, 알고보면 하나도 어렵지 않다.

알파는 MAX가 가지는 최소 값을 말하고,

베타는 MIN이 가지는 최대 값을 말한다.

이를 이용해 pruning 기법을 설명하자면 다음과 같다.

1. MAX 입장에서 알파보다 작은 값을 내놓는 MIN은 탐색할 가치가 없다. (Alpha Cut off)

2. MIN 입장에서 베타보다 큰 값을 내놓은 MAX는 탐색할 가치가 없다. (Beta Cut off)

약간 아리송 할 수 있는데, 구현을 보면 명확해진다.

• max-value

MAX의 조상은 MIN이고, MIN은 베타보다 크거나 같은 값은 수용하지 않을 것이 자명하다.

그래서 만약 탐색을 하다가 베타보다 크거나 같은 값이 나왔다면, 죽음을 택한다.

MAX는 해당 값보다는 크거나 같은 값을 선택할 것이기 때문이다.

• min-value

MIN의 조상은 MAX이고, MAX는 알파보다 작거나 같은 값은 수용하지 않을 것이 자명하다.

그래서 만약 탐색을 하다가 알파보다 작거나 같은 값이 나왔다면, 죽음을 택한다.

MIN은 해당 값보다는 작거나 같은 값을 선택할 것이기 때문이다.

이제 예제까지 풀어보면 완벽히 이해할 수 있을 것이다.

여기서 어떤 부분을 pruning 할 수 있을까?

한 번 풀어보자.

왼쪽 MIN은 b 경로 탐색을 통해 베타를 10으로 정했다.

그런데 e 경로 탐색을 했더니, MAX가 최소 100을 반환할 것으로 보였다.

따라서 g 경로는 볼 필요도 없이 버리면 된다.

a 경로 탐색이 끝났으므로 MAX는 알파를 10으로 정했다.

이제 h 경로 탐색을 떠나보자.

오른쪽 MIN은 i 경로 탐사를 떠나 베타를 2로 정했다.

이 말은 h 경로는 최대 2를 반환한다는 말이므로, MAX 입장에선 더 이상 탐색할 필요가 없다.

따라서 l 경로는 갖다 버리면 된다.

Properties

정말 효율적이어 보이는 알고리즘이지만, 어떤 값을 먼저 발견하느냐에 따라 pruning이 될지 안될지가 달라진다.

예를 들어 이렇게 순서가 바뀌게 된다면 pruning을 할 수가 없어진다.

정말 완벽한 순서로 탐색을 한다 가정하면, 시간 복잡도가 $O(b^{m/2})$로 떨어진다고 한다.

탐색해야 할 깊이가 절반 정도로 줄어드니, 정말 잘만 탐색하면 매우매우 효율적일 것이다.

Evaluation Function

그런데 그 깊이를 어디까지로 해야할까?

무작정 terminal state가 나올 때까지 하긴 어렵다.

체스같은 걸 생각해보면 terminal state까지 도달하려면 정말 수천, 수만번 파고들어야 할 거고, 시간 초과가 뜰지도 모른다.

그래서 나온 것이 depth-limited search이다.

말 그대로 깊이를 적당히 정해서 탐색을 하는 것이다.

그러면 Non terminal state가 얼마나 terminal state와 가까운지를 정해야 하는데, 이것이 evaluation function이 하는 일이다.

Evaluation function은 경험적인 근거를 토대로 현재 state에 대한 평가를 내린다.

이 경험적인 근거라는 것은 룩의 개수, 퀸의 위치 등등 게임의 승패에 영향을 미치는 요소들을 의미한다.

4. Expectimax Search

우리는 이제까지 상대방이 항상 합리적으로 utility를 최소화 시키는 방향을 선택한다고 생각했다.

그런데 꼭 상대방이 그럴 것이라는 보장은 없다.

빅픽쳐를 그릴 수도 있고, 아님 그냥 미친놈이어서 맘대로 고를 수도 있다.

곧, 우리는 확률적으로 접근해야 한다.

저 놈이 저 행동을 할 확률이 몇 퍼센트고.. 저걸 할 확률은 몇 퍼센트고.. 이런 식으로 말이다.

따라서 우리는 상대가 선택할 값을 min 값이 아니라 기댓값으로 생각해야 한다.

그래서 이름도 MIN이 아니라 chance라고 부른다.

위와 같은 방식의 search를 expectimax search라고 한다.

구현은 단순하기 그지없다.

바뀐 것은 기댓값을 반환한다는 것 뿐이다.

기댓값을 반환한다는 게 무슨 말인지 와닿지 않을 수도 있다. 아래 예시를 보자.

이렇게 chance node가 8, 24, 12를 확률적으로 선택할 때, 기댓값은 10이 된다.

따라서 MAX는 저 chance node가 10을 선택할 것으로 생각하고 탐색을 한다.

전체적인 그림은 아래와 같다.

그런데 여기서도 pruning을 할 수 있을까?

당연히 불가능하다. Chance가 최종적으로 뭔 값을 토해낼지 모르기 때문이다.

What probabiliies to use?

그런데 보다보면 한 가지 의문점이 들 수 있다.

저 확률은 어떻게 구해지는거지? 라고.

사실 확률을 구하는 과정은 매우 복잡하다.

상대를 분석하고, 모델을 세우고, RL을 돌리고.. 너무 귀찮다.

그래서 그냥 PPT는 심플하게 요정이 만들어줬다고 간주하라고 말하고 있다.

그런데 가끔 상대가 어떻게 행동하는지 주어지는 경우가 있다.

예를 들어 상대가 80%는 depth 2 minimax를 돌려서 선택하고, 20%는 랜덤으로 선택한다고 하자.

그럼 MAX는 상대방의 행동을 결정하기 위해 depth 2 minimax를 돌려야 한다.

이를 통해 구한 방향에 0.8을 주고, 20%는 랜덤으로 선택한다고 했으므로 공평하게 나눠서 각 방향에 0.1씩 주면 될 것이다.

이런 식의 탐색 안의 탐색은 optimal하긴 하나, 정말 느리다.

Depth 2라서 다행이지, 깊이 제한 없이 탐색한다고 가정하면 그냥 탐색이 끝나지 않을 수도 있다.

Optimism and Perssimism

만약 expectimax search를 하지만 실제로 상대방은 MIN 만을 고른다고 가정하면 어떻게 될까?

이러면 상대방한테 처참하게 깨질 확률이 높아질 것이다.

이 상황을 optimism이라고 한다.

반대로 minimax seach를 하지만 실제로 상대방은 랜덤하게 움직인다고 가정하면 어떻게 될까?

너무 쓸데없이 빙빙 돌아서 답에 도달할 확률이 높아진다.

그림처럼 토끼보고 “이거 뱀파이어 토끼아냐..?!” 하고 무서워서 다른 길로 가버리는 것이다.

이 상황을 perssimism이라고 한다.

실제로 팩맨을 optimism / perssimism 하게 돌려보면 극단적인 결과가 나온다.

5. Other Game Types

이제까지 Deterministic, two player, zero sum game에 대해서 알아봤다.

아래는 추가적으로 알아두면 좋을 법한 게임들이다.

1. Mixed Layer Types

Mixed layer type이란 말 그대로 복잡한 형태의 게임을 말한다.

가장 대표적인 예시가 backgammon인데.. 그냥 모두의 마블 생각하면 된다.

주사위를 굴리고, 뭐가 나오냐에 따라서 가능한 행동들이 달라지기 때문에, 이를 표현하기 위해 MIN, MAX의 전후로 random agent를 넣어서 탐색하는 것이다.

2. Multi-Agent Utilities

Multi-Agent Utilites란 말 그대로 agent가 여러 명 있을 때의 상황이다.

별 거 없다. 그냥 utility가 여러 개인 것이다.

6. Utility

우리는 utility라는 말을 그냥 써왔는데, 이게 정확하게 뭘까?

Utility란 agent의 선호도를 수치화한 값이다.

예를 들어 agent가 아이스크림이 많은 걸 더 선호한다면, utility를 좌측부터 -1, 0, 1 이렇게 설정할 수 있을 것이다.

혹은 두 개 짜리를 너무 좋아해서 -1, 0, 10 이렇게 설정할 수도 있을 것이다.

1. Maximum Expected Utility

Agent가 아이스크림 탐색을 한다면 어떻게 될까?

만약 -1, 0, 1 이라면 실패하는 것이 무서워서 한 개만 담는 방향을 선택할 것이고

만약 -1, 0, 10 이라면 실패할 가능성이 있더라도 두 개를 담는 방향을 선택할 것이다.

이처럼 agent는 utility가 극대화 되는 방향으로 움직이려고 하고, 이것이 바로 Principle of maximum expected utility이다.

2. Preferences

그러면 어떻게 선호도(preference)를 수치화할까?

그 전에, preference라는게 대체 뭘까?

Preference란 말 그대로 어떤 걸 좋아하는 정도를 의미한다.

이때 그 선호의 대상은 prize와 lottery가 될 수 있다.

여기서 prize와 lottery란 agent가 얻을 수 있는 어떤 결과물이라고 생각하면 된다.

예를 들어 10만원 교환권, 20만원 교환권이 prize라고 할 수 있고,

10% 확률로 100만원, 90% 확률로 만원을 주는 랜덤 골드 박스가 lottery라 할 수 있겠다.

이때 $A \succ B$는 A를 B보다 선호함을 의미하고,

$A \sim B$는 indifference, 즉 선호도에 차이가 없음을 의미한다.

1. Rational Preferences

사실 마냥 모든 preference를 utility로 바꿀 수 있는 건 아니다.

오로지 Rational preference만 utility로 바꿀 수 있다.

왜냐면 rational preference를 가지는 agent의 행동만이 maximization of expected utility principle을 따르기 때문이다.

그럼 Rational preference란 뭘까?

위의 조건들을 만족시키는 preference를 rational preference라고 한다.

뭔가 어려워보이지만 알고보면 굉장히 당연한 것들이다.

Orderability는 한 쪽을 선호하거나 혹은 선호도에 차이가 없어야 한다는 말이다.

Transitivity는 A를 B보다 선호하고 B를 C보다 선호하면 A를 C보다 선호해야 한다는 지극히 당연한 말이다.

Continuity는 $A \succ B \succ C$ 일 때, A와 C의 확률을 적절히 조절해서 B를 만들어낼 수 있다는 것이다. 이것도 당연하다.

Substitutability는 A와 B의 선호도 차이가 없을 때, 그 lottery 또한 선호도 차이가 없다는 말이다.

Monotonicity는 A보다 B를 선호할 때, 그 lottery 또한 그 관계를 따라간다는 말이다.

이 조건들을 만족시키지 않으면 논리적으로 말이 안되는 상황이 벌어진다.

예를 들어 preference가 $A \succ B, B \succ C, C \succ A$의 순환적 구조를 띈다면, agent는 A-B-C 사이에서 무한정 반복해서 돌게 된다.

여하튼 이 rational preference에 대해서는 위의 수식을 만족시키는 어떤 real-valued function $U$가 존재함이 증명되어있다.

이때 $U$가 만들어내는 real-value가 바로 utility이다.

그럼 이 real-valued function을 어떻게 찾아내느냐?

이건 매우매우 어렵다.

다만 PPT에서 특수한 경우에 가능한 방법을 하나 제시해주고는 있다.

3. Human Utility

이는 rational preference의 continuity를 이용하는 방법이다.

예를 들어 prize A의 utility를 구한다고 해보자.

$best\;case \succ A \succ worst\;case$ 니까, continuity에 의해 A와 [p,base case, 1-p, worst case]의 선호도가 동등해지는 지점이 있을 것이다.

이 지점을 찾아서, 이때의 $p$를 utility로 정하는 것이다.