A Game Search Problem, A Two-Ply (One Move Deep) Game Tree, The Optimal Strategy in a Game Tree

Games

- Multiagent (competitive) environments : 상대방 agent 의 action 을 예측할 수 없기 때문에 Contingency 가 존재한다.

(상대방의 action 이 ~라면 if , else 로 나눠서 결정)

- 대부분의 게임은 deterministic, turn-taking (돌아가면서 진행), two-player , zero-sum game(한 명이 무조건 이기는 게임), perfect information(full observation, 게임에 필요한 모든 정보가 주어짐, 바둑, 체스)

- 탐색 공간이 매우 크다 :

• chess 의 경우 branching factor 가 35에 가깝고, 각 플레이어는 50번 정도를 움직인다.
• search tree 는 35^100 => 10^154 nodes 를 가질 수 있다.
• 따라서 이는 최적의 행동을 결정하는 것이 실질적으로 불가능하다.

 

 

A Game Search Problem

- two player 의 이름은 MAX(나 자신 agent), MIN(상대방) 이다.

- S0 : initail state

- PLAYER(s) : state s 에서 어떤 플레이어가 움직여야 하는지 정해야 한다.

- ACTIONS(s) : PLAYER(s) 가 할 수 있는 action 의 집합

- RESULT(s,a) : transition model

- TERMINAL-TEST(s) : 게임이 끝난 상태라면 false, 그렇지 않다면 true

- UTILITY(s,p) : 게임이 끝난 상태 s 가 player p 에게 주는 최종 점수

ex) 체스의 경우, 이기면 1점, 진다면 0점, 무승부라면 1/2 을 부여한다.

-> 위의 정의로 game tree 가 정의된다.

 

 

 

The Game Tree for Tic-Tac-Toe

MAX -> MIN -> MAX ... 의 순서대로 진행이 되며 마지막에 TERMINAL 이 된다.

이때 branching factor 는 9 x 8 x ... 1 로, 총 노드의 개수는 9! 가 된다.

 

 

 

Optimal Decisions in Games

- MAX 는 contingent strategy (Solution) 를 찾아야 한다.

- initial state 에서 MAX 의 움직임이 정해져야한다.

- 그런다음, MIN 이 취할 수 있는 모든 action 에 의해 나온 모든 state 에 대해 MAX 가 어떤 움직임을 취해야 할지 정해져야 한다. (If~ If ~ If ~...)

-> AND-OR search 와 매우 닮아있다. MAX는 하나를 선택해야 하므로 OR, MIN 이 택하는 경우 AND 이 된다.

 

만약 MAX 가 o 가 된다면? initial state 에서 움직임을 결정할 수 없고 두 번째 turn 부터 움직일 수 있다. 따라서 첫 번째turn 에서 MIN(x) 가 결정한 action 에 따른 state 가 MAX(o) 의 root 노드가 될 것이다.

 

 

 

A Two-Ply (One Move Deep) Game Tree

- 간단한 Game Tree 이다. 

- 이때 MINIMAX(n) 를 정의할 수 있는데 이는, 노드 n 부터 시작해서 두 플레이어가 모두 자기자신에게 최적으로(optimally) 게임을 진행했을 때, 게임이 끝난 다음 얻게 되는 utility 를 말한다.

 

MINIMAX(c) 를 구해보자. 이것은 이 시점부터 두 플레이어가 optimal 하게 게임을 진행할 때의 utility 값을 의미한다.

이때, turn 은 MIN 의 차례이다. MIN 은 optimal 하게 play 를 하며 c1을 택한다. 따라서 MAX 는 2를 택하게 되고, MINIMAX(c) 는 2가 된다.

 

만약, terminal node 라면, 이는 바로 utility 값인 MINIMAX(n) 이 된다.

terminal node 가 아니라면, MINIMAX 값은 다음과 같이 재귀적으로 계산된다.

Terminal node 는 값 자체가 MINIMAX 가 된다.

->

MINIMAX(B) 는 player 가 MIN 이기 때문에 3,12,8 중 가장 작은 값 3 이 된다.

MINIMAX(C) 는 player 가 MIN 이기 때문에 2,4,6 중 가장 작은 값 2 이 된다.

MINIMAX(D) 는 player 가 MIN 이기 때문에 14,5,2 중 가장 작은 값 2 이 된다.

->

root node 인 MINIMAX(A) 는 player 가 MAX 이기 때문에 3,2,2 중 가장 큰 3이 된다.

 

 

 

The Optimal Strategy in a Game Tree

- 각 node 에서 minimax 값을 가지고 optimal strategy 를 결정할 수 있다.

- 즉 root node A 에서 minimax 값은 3이기 때문에 MAX는 a1을 취한다.

- MIN 역시 3 을 얻기 위해 b1 을 취하고, terminal state 에서 utility 값으로 3을 얻고 게임은 종료하게 된다.

 

-> 나의 상대방인 Min 도 optimal 하게 행동하기 때문에, 최악의 경우 가장 좋은 값은 3점이라는 뜻이다. 만약 MAX 가 a2 를 취했을 때, MIN player 가 최적의 행동을 하지 않고 d2 를 취한다면 나는 5점을 얻을 수 있을 것이다. 그러나 MIN 도 최적의 행동을 취하기 때문에 나는 2점을 얻게 될 것이다.

즉, 상대방이 optimal 한 행동을 취했을 때 worst-case 중 최댓값이 Minimax 값이 된다.

그러나, 일반적인 게임에선 minimax 를 계산하는 것이 불가능하다. 체스의 경우 10^154 node 에 대해 minimax 를 계산할 수 없다.