Adversarial Search Chapter 6 Section 1-4
Adversarial Search Chapter 6 Section 1 – 4
Outline ·Optimal decisions ·a-βpruning Imperfect,real-time decisions
Outline • Optimal decisions • α-β pruning • Imperfect, real-time decisions
Games vs.search problems ·"Unpredictable"opponent→specifying a move for every possible opponent reply ● ·Time limits→unlikely to find goal,.must approximate
Games vs. search problems • "Unpredictable" opponent → specifying a move for every possible opponent reply • • Time limits → unlikely to find goal, must approximate •
Game tree (2-player, deterministic,turns) MAX (X) MIN (O) MAX (X) X o X X o MIN (O) X o X X o X TERMINAL o x oo X x可 X oo Utility 0
Game tree (2-player, deterministic, turns)
Minimax Perfect play for deterministic games ● Idea:choose move to position with highest minimax value best achievable payoff against best play MAX 3 ·E A MIN 12 21 3
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: •