[AI] 5. Adversarial Search (Minimax, α-β pruning, Expectimax)

 

Adversarial Search

지금까지는 주어진 State space에서 보다 효과적으로 Goal을 달성하기 위한 알고리즘이었다면, 이번에는 적(Opponent agent 혹은 Adversary)가 있을 때 승리하기 위한 알고리즘인 Adversarial Search에 대해 알아보자.

적대적인 관계에 있는 agent가 서로의 이익을 최대화 하기 위해 움직이는 상황을 '게임'과 같다고 하여 Game Search라 불리는데, 즉, 지금부터는 상대방(Opponent)의 행동을 예측하고 그 결과를 바탕으로 나의 이익(Reward)를 최대화 하는 결정을 찾아야 한다.

Deterministic Games

Game은 State space의 상태에 따라 Deterministic과 non-Deterministic(혹은 Stochastic) 한 상황으로 나눌 수 있다. Deterministic(결정론적인)은 말 그대로 action을 취했을 때 next state가 딱! 결정될 수 있는 문제이다. 예를 들어 로봇이나 Packman에게 북쪽으로 1칸 가라고 하면 정확히 1.0만큼 이동 할 수 있는 경우이다. 반면 non-Deterministic(혹은 Stochastic : 확률론적인) 한 게임은 때로는 예상치 못한 방향으로 agent가 행동하는 경우다. Non-deterministic한 경우는 추후에 Markov Decision Process를 학습하는 단원에서 더욱 다루기로하고, 지금은 Deterministic Game Search에 대해 알아보자. 본격적 학습에 있어 Deterministic game을 Formalize하기 위한 정의에 대해서 알아보자.

• State : S = {State space, Player} (start at s0)

• Players : P = {1 ... N}

• Actions : A

• Transition Function : S X A → S    (Action을 통한 State의 변화)

• Terminal Test : S → {t, f}              (Goal state에 도착하였는가?)

• Terminal Utilities : S X P → R        (Player의 점수)

 

※ 위 분류 외에도 Player의 수, Utility 등에 따라 다양하게 Game을 아래와 같이 분류하니 기억해 두자. 

 1) Zero-Sum Game : 두 agent가 서로 반대의 utility를 가지며, 서로 뺏기위해 싸운다.

 2) General Game : 각자의 utility를 maximize 하기 위해 독립적으로 진행한다. 

 3) Single agent game : 혼자 잘하면 되는 게임 (ex. feed를 많이 먹는 packman)

 4) Multiple agent game : 상대방이 있는 게임 (ex. 유령으로부터 살아남아야 하는 packman)  

Minimax vs. Expectimax 

Opposite agent가 있는 게임을 한다고 가정하자. 예를 들면 유령을 피해 feed를 많이 먹어야 하는 Packman game이 있다. 이 경우, 가장 합리적인 Packman의 이동방향을 결정하기 위해서는 유령(Opposite agent)가 어떤 판단을 기준으로 움직일 것인지를 예상해야한다. 이때 상대가 나의 이득을 최소화 시키는 방향으로 간다는 가정하에 next state를 결정하는 것이 Minimax Search이며, 반대로 확률에 따라 비합리적으로 움직일 수 있다고 가정하고 next state를 결정하는 것은 Expectimax Search 알고리즘이다. 먼저 Minimax Search에 대해 알아보자. 

1. Minimax Search

-8                -5               -10                 +8

(Packman Game은 대표적인 Deterministic 2 player zero sum game이다.)

Game Search는 대게 위 그림과 같이 Tree로 표현된다. Tree에서 파란색 State은 Player의 턴이며 붉은색 State는 Opponent의 턴이고 Player는 현재 State에서 왼쪽으로 갈지 오른쪽으로 갈지 선택을 해야 하는 상황이다. 만약 Terminal State의 Utility V(s) 또한 위 그림과 같이 안다고 가정했을 때, Minimax Search는 Opponent가 Utility를 최소화 하기 위한 움직임을 할 것이라 예측 하는 것이다.

위 예제에서는 좌측 트리의 경우 Opponent는 -8의 Utility를 갖기 위해 좌쪽으로 이동할 것이고, 우측 트리의 경우도 마찬가지로 -10의 Utility를 갖기 위해 좌측으로 이동할 것이다. 그럼 가장 상위 노드인 Player는 Opponent가 -8과 -10의 Utility를 선택했다는 것을 인지하고 상대적으로 높은 점수를 얻을 수 있는 왼쪽 Arc로 이동하는 것을 선택하게 된다.

이렇듯 Minimax Search는 항상 Utility를 최대화 하는 방향으로 선택하는 MAX(player)와 최소화 하는 방향으로 선택하는 MIN(opponent)가 있다고 생각하는 탐색 방법이다. 또다른 예제를 살펴보자.

위 그림과 같이 Terminal Utility를 알고 있다고 가정 했을 때, Minimax Search 는 Opponent는 MIN Player로써 각각 3, 2, 2를 선택할 것라고 예측한다. 따라서 MAX Player는 상대적으로 가장 큰 Utility를 가지는 좌측 노드를 선택하게 된다. 위와 같은 알고리즘을 직접 구현하는 Pseudo code는 아래와 같다.

pseudo code에서 state는 utility와 next player에 대한 정보를 담고 있어서 value 함수에서 턴을 인식하고 Player 턴일때는 MAX값, Opponent 턴일때는 MIN값을 취하고 있다.

α-β pruning

그런데 조금 고민해보면 Minimax Search의 실행속도를 향상시킬 여지가 충분히 있다.

앞선 예제와 동일한 상황이다. 좌측 Opponent node는 3과 12, 그리고 3과 8을 비교하여 MIN값으로 3을 택하였다. 그리고 가운데 위치한 Opponent node는 가장 먼저 2를 입력 받았다. 그런데 여기서 다음 Utility가 2보다 작다고 하더라도 가장 상위의 Player node의 의사결정에 영향을 미치지 못한다. 왜냐하면 Player node는 MAX값을 취하기 때문에 MIN 노드에서 3보다 작은 어떤 값을 취하더라도 상관하지 않기 때문이다. 즉, 첫째 Opponent 노드의 결과로부터 3의 Utility가 선정되었기 때문에, 그 다음 노드에서 3보다 큰 값을 선택하지 않는 이상 그 뒤의 연산은 무의미하다. 가뜩이나 MAX함수는 보기보다 computing 비용이 비싼 함수이다.

결과적으로 다음과 같이 가지치기를 함으로써 컴퓨팅 시간을 단축시킬 수 있는데 이 기법을 α-β Pruning 이라고 한다. pruning의 결과로 본 예제에서는 2개의 가지를 잘라낸 것 처럼 보이지만, 통상 Game search의 Tree depth가 긴 것을 가정하면 매우 큰 손실을 방지한 것이다.

이번 예제에서 Pruning의 기준이 된, 즉 MAX Player가 가지는 최소값을 α, 반대의 경우 MIN Player가 가지는 최대값을 β라 하며, α-β Pruning을 Pseudo code로 표현하면 아래와 같다.

Pseudo code는 Minimax에 α, β를 비교하고 갱신하는 기능이 추가되었다. max-value function만 보면, opponent에서 선택한 utility 값과 α중 더 큰값을 α로 update하고, min-value function에서는 α보다 작은 값이 utility로 주어지면 for문을 중단함으로써 남은 하위 node들은 탐색하지 않는다. 한 가지 예를 더 풀어보자

최초에는 α = -∞, β = + ∞로 초기화 되어 있다.

MIN Player는 b 경로 탐색을 통해 β를 10으로 정했다. 

그리고 f 경로 탐색을 통해 β보다 큰 100이 나오는 순간 g경로는 탐색하지 않는다. 

MAX Player는 a 경로 탐색을 통해 α를 10으로 정하고 h 경로 탐색을 시작한다. 

MIN Player는 i 경로 탐색을 통해 β를 2로 업데이트 하는데 

β가 α보다 작아진 순간 남은 경로는 더 이상 탐색할 필요가 없다.

Resource Limit (Depth-Limit Search)

그런데 또 하나의 문제가 있다. 통상 게임은 위 예제처럼 1~2턴만에 끝나지 않는다. 하지만 Terminal state까지 예측을 하기에는 computing resource에 제한이 있기 때문에 통상 Tree Depth에 제한을 두는데 이 방법을 Depth-Limit Search라 한다. 말 그대로 Tree의 최대 깊이를 미리 정하고 Terminal state가 아닌 곳에서 멈추게 하는 것이다. 여기서 Depth의 의미는 앞을 내다 보는 수이다. MAX, MIN 이 1번씩 나오는 것을 1 depth라 했을 때 depth를 3으로 제한하면 앞의 3수까지 내다보고 게임 하는 것을 의미한다.

어찌됐든 결국 Terminal state가 아닌 곳에서 멈추기 때문에 non-terminal state가 terminal state와 얼마나 가까운지를 approximately 하게 알 수 있는 지표가 필요하다. 이 역할을 하는 것이 Evaluation function 이다.

Evaluation function은 feature들의 weighted sum으로 나타내는데, 이때 feature는 경험을 토대로 (Domain 지식을 토대로) State로 부터 대략적인 점수를 부여할 수 있어야 한다. 예를 들어 Chess 게임의 경우 play의 남은 룩의 수, 퀸의 위치 등 게임에 승패를 나타내는 지표가 될 수 있다. (일종의 Heuristics function이며 A* 의 Heuristics와 유사하다.)

2. Expectimax Search

지금까지는 Opponent player가 optimal (MIN)한 결정을 할거라는 가정하에 MAX Player의 Action을 결정했다. 하지만 Opponent player가 항상 optimal 하다고 할 수는 없다. 실력이 부족하다거나 실수를 할 수도 있다. 즉 Opponent가 확률적으로 잘못된 선택을 할 수 있다는 가정하에 Player의 action을 결정하는 것이 Expectimax Search 알고리즘이다. 조금더 직관적인 예를 보자.

위 경우에 Minimax search는 MIN 값을 취하는 player의 특성을 예측하여 왼쪽 노드(utility = 10)을 택할 것이다. 하지만 우측에 있는 utility=100 의 기회를 놓쳤다고 할 수 있다. 그럼 우측에 있는 utility=100의 기회를 얻고 싶다면 어떻게 해야할까? 정답은 utility=9일때와 utility=100일때의 expected utility를 구해서 의사결정을 하는 것이다. 따라서 더 이상 Opponent는 MIN전략을 취하는 것이 아니라 확률적으로 change를 가질 수 있는 노드로 변경된다. expected utility에 대해서 좀 더 알아보자.

위 예제에서 각 state에 대한 확률이 주어진다고 가정하면 change node는 각각 utility와 확률의 Summation(Σ P(x) * f(x) = 확률을 반영한 평균)을 expected utility로 가진다. 만약 확률정보가 주어지지 않는다면 통상 평균값을 기대값(expected utility)로 갖는데, 이 확률 정보를 Data로부터 알아내서 formalize 하는 기술이 Markov Decision Process 이다. 이는 추후에 다루기로 한다.

※ 모든 utility가 expected utility에 영향을 미치기 때문에 pruning을 할 수는 없다.

Optimism vs. Pessimism

지금까지 2가지 Game search를 살펴보았는데 두 알고리즘은 양날의 검이라 할 수 있다. 만약 Opponent가 optimal 한 MIN player라 생각했는데 상대방이 랜덤하게 움직인다면 게임에서 질 수 있다. 이런 경우를 Dangerous Pessimism이라 한다. 그림처럼 Opponent는 순한 토끼인데 무서운 Ghost라 생각한 것 처럼 말이다.

물론 반대의 경우도 있다. Opponent가 확률적으로 랜덤하게 움직이는 쉬운 상대인 줄 알았는데 알고보니 optimal 한 MIN player라면 분명 패배할 것이다. 이런 경우를 Dangerous Optimism 이라 한다.

실제로 Opponent(MIN vs. CHANGE)와 Search 알고리즘(Minimax vs. Expectimax)을 달리해서 게임을 진행했을 때 극단적인 결과를 관찰할 수 있다.

Other Games

지금까지 Deterministic, 2 player, zero sum game을 살펴봤는데 그 외에도 다양한 형태의 게임 형태가 있을 수 있으니 참고로 알아 두자.

1) Mixed Layer Types

Mixed Layer Type은 쉽게 말해 opponent는 MIN Player지만 그 사이에 주사위와 같은 확률이 동작하는 경우이다. 예를 들면 backgammon이 있는데 무슨 게임인지는 잘 모르겠고, 모두의 마블정도로 생각하면 좋겠다. 이런 경우 MIN, MAX player 전후로 change 노드를 둠으로써 주사위의 확률을 반영할 수 있다.

2) Multi-Agent Utilities

말 그대로 MIN player가 여려명 있는 경우이며, Minimax Search의 Utility를 복수로 생각하고 풀이하면 된다. 위 예제는 player가 3명인 경우이다.

Utilities

지금까지 Utility를 단순히 '점수'정도로 생각하고 있었는데 정확히 무엇을 의미하는지 보자.

Utilities는 Decision making agent라 할 수 있다. 풀어 말하면 의사결정을 하는데 근거가 되는기준이라 할 수 있다. 우리가 해야할 일은 Maximize Expected Utilities를 선택하는 것이며, 그것을 위해 Expected Utilities를 잘 정의 혹은 적용하는 것다.

지금까지는 Minimax나 Average값을 Expected Utilities로 사용했는데, 상황에 따라서는 확률분포를 사용해야 할 수도, 혹은 Domain knowledge가 작용된 기준을 사용해야 할 수도 있다. 

(Utilities에 대해서는 더욱 길게 Review할 것이 많으나 Optional 하기 때문에 다음 강의 정리를 먼저 하고 마저 정리하도록 함.)