TIL - 2021.10.04

Wanna be __·2021년 10월 4일
0

TIL

목록 보기
39/45
post-thumbnail

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

profile
성장하는 개발자

0개의 댓글