Game Tree
- Game Trees: Adversarial Search
- zero-sum: maximize, minimize
- 현재 상태에서 최선을 다하기: w/ evaluation functions
- depth matters
- minimax pruning
- time: $O(b^m)$, space: $O(bm)$
- alpha-beta pruning
- time: $O(b^{m/2})$
- exact solution: impossible
- Uncertainty & Utilities
- expectimax
- random agent