[AI]5. Game Trees
우리는 game에서 각 state에서의 최적의 strategy를 계산하는 알고리즘을 구하고자 한다.
Adversarial Games
여러 분야로 나눈다. Deterministic or stochastic. How many players? Zero sum? Perfect information?
Deterministic Games
formalization을 하는 방법은 여러가지이지만 그중 하나는 아래와 같다.
- States: S
- Players: P={1…N}(turn방식으로 작동한다)
- Actions: A
- Transition function: SxA $\rightarrow$ S(State X Action $\rightarrow$ Next State)
- Terminal Tests: S $\rightarrow$ {t,f}
- Terminal Utilities: SxP $\rightarrow$ R(State X Player $\rightarrow$ Reward)
결론은 player에 대한 policy는 S $\rightarrow$ A 이다.
Zero-Sum Game
- Agent들은 모두 다른 utility(values on outcomes)를 가진다.
- 한 agent는 maximize, 한 agent는 minimize하려는 방식.
- Adversarial, pure competition
General Games
- Agent들은 독립적인 utility(values on outcomes)를 가진다.
- 다양한 방식이 가능하다.
Adversarial Search
Single-Agent Tree를 예로 들면 가능한 State를 Tree로 나타낸다.
Value of State(V)는 그 State에서 가능한 가장 좋은 결과(utility)를 말한다.
Terminal State에서는 V(s)를 확실하게 알지만 Non-Terminal State에서는 V(s)를 자식노드의 가장 좋은 결과를 사용한다.
Adversarial Game Trees
Player는 Turn제로 play하기 때문에 한 State에서 한번의 action만 가능하다.
Minimax Values
Agent는 Max value of state를, Opponent는 min value of state를 지향한다.
각 노드에서 minimax value(optimal한 adversary에 반하는 가장 좋은 결과)를 recursive하게 계산한다.
Implementation
Two Adversarial Agent
max-value는 min-value가 가능한 작은 값을 골랐을 때 그중 가장 큰 값을 선택한다.
min-value는 max-value가 가능한 큰 값을 골랐을 때 그중 가장 작은 값을 선택한다.
Three Adversarial Agent
셋 이상의 agent가 있을때는 하나의 함수가 추가된다.
value는 다음 player가 min을 추구하는지 max를 추구하는지에 따라 min-value or max-value를 결정해주는 함수이다.
Resource Limit
모든 State의 leave를 계산할 수는 없다. 따라서 search depth를 제한하는 방법으로 optimality를 줄이고 계산한다. 하지만 depth가 과하게 얕으면 search의 quality가 떨어진다.
반대로 depth가 과하게 깊으면 search의 complexity가 높아진다.