Lecture 9. Game playing 1

 여기서는 앞의 MDP와는 달리, 우리의 전략이 자신의 state $s$ 뿐 아니라, 상대 플레이어들의 전략으로부터도 영향을 받는다. 여기서는 플레이어가 둘(나 agent와 상대 opp)인 제로섬 게임(내가 $10을 따면, 상대는 $10을 잃는다는 의미에서의)을 예로 설명한다.

Game

 기본적인 접근법은 searching problem과 MDP와 유사하다. searching problem은, 현재 나의 state $s$ 노드가 $succ(s,a)$들을 자식노드로 같는 식으로 트리를 만들고 그 트리를 탐사함으로써 최적의 선택(action $a$)를 찾는다는 것을 의미하며, MDP처럼 state $s$에서 취할 수 있는 actions $a$들이 존재한다. 단지 여기서는 state $s$가 $Players(s)$에 속해있다. 또한, MDP에서는 $a$를 취할 때마다 cost가 존재했다면, 여기서는 $s$가 end state에 도달해야 Utility(s)가 존재한다( 게임이 끝나야 내가 내가 이겼는지 졌는지 알고 그에 대한 보상을 받는다). 또한, agent와 opp가 번갈아가며 $s$를 결정하고 둘의 $s$는 서로에게 fully observable하다.

 이 강의에서 사용한 예시는 다음과 같다. A박스에는 -50과 50이, B박스에는 1과 3이, C박스에는 -5와 15가 들어있으며, agent는 A, B, C 중에서 하나를 고르며, opp는 agent가 고른 박스에 들어있는 2개의 공 중 하나를 고른다. 따라서 당연히 공에 써있는 값을 최대화하기 위한 agent의 전략은 opp의 전략에 의존할 것이다. opp가 둘 중 아무거나 고른다면 박스안의 공의 평균이 가장 높은 C박스를 고르는 것이 최선의 전략일 것이고, opp가 둘 중 낮은 값의 공을 뽑는다면 들어있는 공의 최솟값이 가장 큰 B박스를 고르는 것이 최선일 것이다. 이 강의의 목적은 이러한 전략을 모델링하고 컴퓨팅을 통해서 최적의 전략을 찾는것이다.

앞으로 사용할 예제로, 빨간 선은 agent가 파란선은 opp가 선택한다.

 이 게임에서의 Value $V_{eval}$은 다음과 같다.

 $V_{eval}(s)= \begin{cases} Utility(s), & \mbox{IsEnd(s)} \\ \sum_{a \in Actions(s)} \pi_{agent}(s,a)V_{eval}(Succ(s,a)), & \mbox{Player(s) = agent} \\ \sum_{a \in Actions(s)} \pi_{opp}(s,a)V_{eval}(Succ(s,a)), & Player(s) = opp \end{cases}$

 2, 3번째 조건은, 누구의 턴이냐에 따라 누구의 policy를 기반으로 V값을 계산해야 하는지 나타낸다.

Expectimax

 agent가 자신의 전략을 정할 때, 가장 기본적인 전략은 내 이득을 최대화하는 선택을 하는 것이다. 이러한 선택을 하는 노드를 max노드라 한다. 이러한 max노드에서는 가장 큰 값을 같는 자식 노드를 취한다. 즉, MDP의 예제에서처럼 가능한 모든 자식노드들에 대한 평균값을 V 값으로 취하는 것이 아닌, 최댓값을 갖는 자식 노드를 취하며, 이러한 방식에 의해 얻어진 V값을 expectimax value $V_{exptmax}(s)$라 한다. 위의 예제에서 상자를 고르면 안의 두 공 중 랜덤하게 하나가 선택된다면 $V_{exptmax}(s) = 5$ 가 된다(두 공 중 하나가 임의로 선택되므로 평균값이 가장 높은 상자를 취한다). Expectimax를 취하는 경우의 V 값은 다음과 같다.

 $V_{exptmax}(s)= \begin{cases} Utility(s), & \mbox{IsEnd(s)} \\ \max_{a \in Actions(s)} V_{exptmax}(Succ(s,a)), & \mbox{Player(s) = agent} \\ \sum_{a \in Actions(s)} \pi_{opp}(s,a)V_{exptmax}(Succ(s,a)), & Player(s) = opp \end{cases}$

  이 경우의 전략을 나타내면 아래와 같다.

$\pi_{exptmax(r)} = arg \max_{a \in Actions(s)}mean_{a \in Actions(s)} V_{eval}(Succ(s,a))$ (agent의 전략)

$\pi_{r} = \begin{cases} \min_{a \in Actions(s)} V_{eval}(Succ(s,a)), \mbox{Prob.} = \frac{1}{2} \\ \max_{a \in Actions(s)} V_{eval}(Succ(s,a)), \mbox{Prob.} = \frac{1}{2} \end{cases}$ (opp의 전략)

 즉, opp는 아무거나 뽑고, agent의 경우에는 공들의 평균값이 가장 높은 것을 고른다.

 이러한 접근의 문제점은 상대방의 전략이 $\pi_r$이 아니면 제대로 대처할 수 없다는 것이다. 위의 예제를 예로 들면, 상대가 두 공 중 임의로 공을 뽑지 않고 두 공 중 값이 낮은 공만을 뽑을 경우 제대로 대처할 수 없다.

Minimax

 위의 문제를 해결하기 위한 전략이 Minimax 이다. 즉, 최악의 경우만을 상정하여 내가 취할 전략을 정하는 것이다. 위의 예제에서는 상대가 값이 낮은 공만을 뽑을거라고 생각하며 $a$를 취하게 되므로 공의 값들 중 낮은 값이 가장 큰 B 상자를 택하게 될 것이다$V_{minimax}(s) = 1$. 이러한 경우의 V값은 아래와 같이 주어진다.

 $V_{minimax}(s)= \begin{cases} Utility(s), & \mbox{IsEnd(s)} \\ \max_{a \in Actions(s)} V_{minimax}(Succ(s,a)), & \mbox{Player(s) = agent} \\ \min_{a \in Actions(s)} \pi_{opp}(s,a)V_{minimax}(Succ(s,a)), & Player(s) = opp \end{cases}$

 즉, 상대는 최솟값만 선택하므로, 나는 최솟값이 가장 큰 상자를 선택하는 것이다. minimax에서의 전략 $\pi$는 다음과 같이 주어진다.

$\pi_{max} = arg \max_{a \in Actions(s)} V_{minimax}(Succ(s,a))$ (agent의 전략)

$\pi_{min} = arg \min_{a \in Actions(s)} V_{minimax}(Succ(s,a))$ (opp의 전략)

비교

 이제 agent와 opp의 전략에 따라 $V$가 어떻게 달라지는지 보겠다. 먼저, $\pi_{opp} = \pi_{r}$ 인 경우에는

$V(\pi_{exptmax{r}},\pi_r) = 5, V(\pi_{max},\pi_r) = 2$ 가 된다. 또한, $\pi_{opp} = \pi_{min}$ 인 경우에는, $V(\pi_{exptmax{r}},\pi_{min}) = -5, V(\pi_{max},\pi_{min}) = 1$ 가 되다. 즉, agent가 opp의 전략을 제대로 알지 못하는 경우에는 손해를 볼 수 있다.   

 

Computation

 위와 같은 단발성 게임이 아닌 체스 등과 같이 상대와 내가 계속해서 Action을 취하는 경우 나의 최적의 선택을 찾기 위해서는 위와 같은 트리를 만든 후, 가장 최적의 해를 주는 branch를 찾으면 될 것이다. 하지만, 여기서 문제는 tree가 너무 커지면 모든 가능성에 대해서 탐사하는 것이 현실적으로 불가능하거나 너무 비효율적이라는 것이다. 선택지가 b개이고, 트리의 깊이가 d까지 내려갈 경우에 완전탐색을 하게 되면 시간복잡도는 $O(b^{2d})$이 된다. 여기서 해결책이 두가지가 있는데, 첫번째는 내가 게임에 대하여 잘 알고 있을 경우, 트리를 탐색하지 않고, 현 상황을 분석하여 적절한 점수를 주어 결괏값을 예측하는 것이다. 예를 들어 체스의 경우, 왕의 안전성, 가지고 있는 말의 개수, 움직일 수 있는 말의 개수 등을 이용하여 각 $a$에 대한 Reward를 계산하는 방법이 있다. 두번째는 tree의 필요없는 가지들을 쳐내는 것이다.