Today, I Learned

1. AI

Adversarial Search

Games
solved?

• checker: 2007년에 solved
• chess: 아직 solved단계는 아님.
• go: 체스와 비슷함. expert 단계이기는 하나 solved는 아님

Types of games - Several axes

• Deterministic or stochastic? - checker, chess, go / backgammon(주사위 결과 따라서..)
• One, two or more players?
• Zero sum? - all playing against 냐 그건 아니냐 또 세분화 가능
• Perfect information? chess나 go 같이 전체 보드를 아는것 vs 포커처럼 상대방 패를 모르는 것

즉, Adversarial Search의 경우 나는 "상대방이라면 나를 어떻게 생각할지"에 대하여 생각해야함.
가위바위보에서 "나는 묵낼거임" 하고 말하고나서 무한으로 "그러면 얘는 빠 낼꺼니깐 나는 찌 내야지. 그러면 이까지 걔도 생각했을꺼니깐 나는 한번더 생각해서 진짜 묵내야겠다" 이거랑 유사.

Tree의 경우에서 single-agent의 경우 항상 좋은 선택을 할거고, 그렇다면 Terminal state가 아닌 internal node들은 자식노드 중 max값을 선택하면 해당 state의 value를 구할 수 있음.
Single-agent가 아니라면? pacman에서 나와 ghost가 한 move씩 한다고 하면, 나는 점수를 많이 받는 선택을, ghost는 그 반대의 선택을 할 것이므로, value of state를 반복적인 max로 볼 수 없음.
max와 min의 선택이 번갈아 나오는 형식이 될 것. -> minimax

Minimax 방법

• DFS와 유사, 반복적으로 Min과 Max를 계산해야함.
• Time -> O(b^m)
• Space -> O(bm)
  즉, Fringe는 많지 않아서 space complexity는 좋으나, time complexity가 너무 큼. -> CSP에서 filtering하는 것 처럼 가망없는 branch는 pruning하자!

Alpha-Beat Pruning