Adversarial SearchChapter 6Section 1 - 4The Master vs Machine:A Video
1 Adversarial Search Chapter 6 Section 1 – 4 The Master vs Machine: A Video
OutlineOptimaldecisionsα-β pruning. Imperfect, real-time decisions2
2 Outline • Optimal decisions • α-β pruning • Imperfect, real-time decisions
Games vs. search problems "Unpredictable" opponent → specifying amove for every possible opponent reply Time limits > unlikely to find goal, mustapproximateExample:tic-tac-toe- Relationship to five-in-a-row?3
3 Games vs. search problems • "Unpredictable" opponent → specifying a move for every possible opponent reply • • Time limits → unlikely to find goal, must approximate • Example: tic-tac-toe • – Relationship to five-in-a-row?
Game tree (2-playerdeterministic, turns)MAX (X)MIN (O)MAX (X)MIN (O)XIOTERMINALUtility
4 Game tree (2-player, deterministic, turns)
MinimaxPerfectplayfordeterministicgamesIdea: choose move to position with highest minimaxvalue= best achievable payoff against best play MAxMAXAA3EMIN2MIN.-1431285225
5 Minimax • Perfect play for deterministic games • • Idea: choose move to position with highest minimax value = best achievable payoff against best play • • E.g., 2-ply game: • MAX MIN