Games
- 예측할 수 없는 상대 -> solution은 가능한 모든 상대의 응답에 대해 이동을 지정하는 전략
- 시간 제한(constraint : 제약조건) + search space가 지나치게 큼 -> (can not search all) -> unlikely to find goal,, 근사해야함.
Adversarial Search
- 적(상대)가 내가 가고 싶지 않은 곳으로 state를 바꾸는(방해하는) 탐색 (Search when there is an "enemy"(opponent) changinig the state of problem every step in a direction you do not want)
- (ex) chess : 내가 현재 state를 바꾸지만 다음 state를 바꿀수는 없음(상대가 바꿈), 예측불가함
Types of Games
- Level of information
- Deterministic(action에 의한 state가 결정적임) vs chance(stocastic / 결정적이지 않음)
- Number of players
| Deterministic | Chance | |
| Perfect information (게임에 필요한 모든 정보 제공) | Chess(내가 말을 둠 -> next state는 상대방이 "결정"), go, Checkers | Backgammon Monopoly (dice에 영향을 받음) |
| Imperfect information (상대방 정보 없음) | Battleships, Blind tictactoe | Bridge, poker, scrabble |
- Zero sum game
- 상대방이 얻으면(+1) 내가 잃고(-1) (=0) 내가 얻으면(+1) 상대방이 잃음(-1) (=0) (A situation in which a participant's gain or loss is exactly balanced by the losses of gains of other participants)
Game Problem Formulation
- A game with 2 players (플레이어가 두명인 게임에서 / MAX & MIN / MAX가 먼저 움직임)
- Initial state : board position(보드에서의 위치. tic-tac-toc의 경우)
- Player
- Successor function : a list of legal pair (move, state) / 갈 수 있는 가능한 경우
- Goal test : 게임이 끝나는 지점 (terminal states)
- Utility function : expected cost to win the game(arrive terminal state) 게임에서 이겼을 때 player에게 주어지는 최종 cost
- Game tree = Initial state + legal moves
Optimal Strategies
- Max (player 1) must find a contingent strategy(상황의존적 전략)
- initial state에서 MAX가 가야할 곳이 지정되어 있어야함
- 그 다음, MIN 이 취할 수 있는 모든 action 에 의해 나온 모든 state 에 대해 MAX 가 어떤 움직임을 취해야 할지 정해져야 함
Minimax (최소극대화)
- Idea : 높은 minimax value인 position으로 움직이는 것을 선택 (= best play에 대한 best 달성가능한 보상 / 상대방의 최고의 수가 나에게 최소의 영향을 미치게..)
- Zero-sum games
- 예측한 트리노드에서 나에게 최고가 되게, 상대방은 자신에게 최고(나에게 최소)가 되게 선택하는 search 알고리즘 (상대방인 MIN 또한 자기 자신에게 최적으로 움직일 것이므로, MAX의 score 를 최소한으로 만들려고 하기 때문에 MAX는 최악의 상황을 가정하고, 거기서 최대한의 점수를 내는 방향으로 움직임)
- complete depth-first search인가? 트리가 유한할 경우 Yes
- Time complexity -> O(b^m)
- Space complexity -> O(bm)
- chess인 경우, b는 약 35, m은 약 100 -> 너무 커서 실행불가능..
- 우리가 모든 걸 탐색해야할까? 시간을 어떻게 줄일 수 있을까? => 알파베타 가지치기 이용!
추가참고 :