[인공지능] Chapter 8. Adversarial Search (2)

Uncertain outcomes controlled by chance, not an adversary!

Expectimax Search

• 어떠한 행동의 결과가 어떻게 될지 알 수 없는 이유는?
  • Explicit randomness
  • Unpredictable opponents
  • Actions can fail
• Values should now reflect average-case (expectimax) outcomes, not worst-case (minimax) outcomes
• Expectimax search
  • Compute the average score under optimal play
    • Minimax search와 같은 max node
    • Chance node
      • are like min nodes
      • but the outcome is uncertain
    • Calculate their expected utilities
    • take weighted average (expectation) on children

Probabilities

• 무작위 변수
  • 결과를 알 수 없는 event를 나타냄
• 확률 분포
  • 결과에 가중치를 할당하는 것
• 예시
  • Traffic on freeway
  • 무작위 변수 T
    • whether there’s traffic
  • 결과
    • T in {none, light, heavy}
  • 확률 분포
    • p(T=none) = 0.25, P(T=light) = 0.5, P(T=heavy) = 0.25
      
      

Expectations

• 무작위 변수 함수의 expected value는 결과에 대한 확률 분포에 가중치를 부여한 평균
• Ex. How long to get to the airport?

Other Game Types

• Mixed Layer Types (Games)
  • Ex
    • Backgammon
  • Expectiminimax
    • Environment는 각 최대/최소 agent 다음에 이동하는 추가 random agent player
    • 각 노드는 자식들의 적절한 조합을 계산
• Multi-Agent Utilities
  • 제로섬이 아니거나 플레이어가 여러 명이라면?
  • Generalization of minimax
    • Terminal에는 utility tuples이 존재
    • Node 값도 utility tuples
    • 각 플레이어는 자신의 구성요소를 최대화
    • 동적으로 협력과 경쟁 가능

Monte Carlo Tree Search

• Ideas
  • Evaluation by rollouts
    • 간단하고 빠른 rollout policy를 사용하여 여러 게임을 플레이 하며 승패를 계산
  • Selective search
    • 깊이에 관계없이 뿌리 노드에서 결정을 개선하는데 도움이 되는 트리의 부분을 탐색

Summary

• Games require decisions when optimality is impossible
  • Bounded-depth search and approximate evaluation functions
• Games force efficient use of computation
  • Alpha-beta pruning, MCTS
• Game playing has produced important research ideas
  • Reinforcement learning (checkers)
  • Iterative deepening (chess)
  • Rational metareasoning (Othello)
  • Monte Carlo tree search (chess, Go)
• Video games present much greater challenges – lots to do!