Games vs Search
- game은 multi-agent 환경의 형태이다
- 경쟁적인 multi-agent 환경은 adversarial search를 발생시킨다
- 솔루션은 전략적이다 (가능한 모든 상대의 reply에 대한 move를 구체화함
Type of games
- deterministic (ex. chess)
- chance (ex. backgammon)
- imperfect information (ex. poker)
Game setup
- Perfect information: fully observable
- Two players: MAX and MIN
- MAX가 먼저 움직인다
- 승자는 점수를 받고 패자는 패널티를 받는다
- zero-sum game : 한 사람에게 좋은 건 다른 사람에게 나쁘다
- 게임도 서치다
- initial state
- players
- actions and transition model :(move, state)의 페어는 legal move를 규정한다
- terminal test
- utility function or payoff function
- initial state와 legal moves는 game tree를 정의한다
Minimax algorithm
Complete? Yes (if tree is finite)
Optimal? Yes, against an optimal opponent; Otherwise?