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?