Adversarial Search

게임을 예로 들어서 보자면 지금까지 포스팅은 플레이어가 1명이었을 때였다.

이제는 플레이어가 2명이고 서로 적대적인 관계일때의 Search에 대하여 알아보자.

Adversarial Search

---

적대적인 관계가 존재할 때 적대적 관계의 행동을 미리 고려하여 결정을 내리는 Search이다. 팩맨을 예로 들면 팩맨이 food만 먹는게 아니라 Ghost의 행동도 고려해야하는 것. Ghost가 똑똑하게 나를 향해 올수도, 멍청하게 혼자 이리저리 움직이기만 할 수도 있으나 어쨋든 Ghost의 Action을 고려하여 팩맨의 Action을 취해야 한다. 간단하게 Zero-Sum Game이라 생각하면 된다.

Minmax Values

---

간단하게, 나는 Max 값을 취하고 상대는 내 입장에서의 Min 값을 취한다. 상대가 내 입장에서의 Min 값을 취하는 것이 상대에겐 Max값을 취하는 것이니. Root가 현재 State인데 어느 Action을 취해야 하는지 Minmax를 이용해 결정한다.

Blue는 Max, Red는 Min 값을 취한다. 

left Red = min[-8, -5] = -8

right Red = min[-10, +8] = -10

두 Red의 값이 정해졌고 Root State에서 이 두 Red의 값 중에서 Max 값을 취한다.

Root state = max[left Red, right Red] = max[-8, -10] = -8

그럼 팩맨은 left로 가는 액션을 취하게 되는 것.

Minmax Implementation(Dispatch)

---

Minmax Efficiency

---

How efficient is minmax?

- Just like (exhaustive) DFS

- Time: 

- Space: