Practical 4-Adversarial Search

▶ Minimax

▶ α-β pruning

Minimax

▶ At A, it is MAX’s turn. MAX will choose the maximum of B, C, D

▶ What are the values of B, C, D?

▶ At each of these states, it is MIN’s turn. MIN will choose the minimum of the states below it.

▶ At B, MIN would choose F, so the value of B is 4

▶ At C, MIN would choose I, so the value of C is 3

▶ at D, MIN would choose K, so the value of D is 2

▶ MAX chooses B!

α-β pruning

▶ E=2, F=3, and G=3, so B=2 and A is at least 2

▶ H=2, so C is at most 2

▶ A is at least 2 already

▶ We don’t need to look further below C; I and J are pruned ▶ K=8, so D is at most 8

▶ A is at least 2 and D is at least 8, so D might improve utility; keep searching

▶ L=2, so D is at most 2

▶ A is at least 2 already

▶ We don’t need to look further below D; M is pruned

▶ K=1 and L=8, so E=8 and B is at most 8

▶ M=1 and N=5, so F=5, B=5, and A is at least 5

▶ O=5 and P=6, so G=6 and C is at most 6

▶ Q=4 and R=4, so C=4, A is still at least 5

▶ S=8 and T=3, so I=8 and D is at most 8

▶ U=7 and V=9, so J=9, D=8 and A=8

▶ K=4 and L=8, so E=8 and B is at most 8

▶ M=6 and N=2, so F=6, B=6, and A is at least 6

▶ O=5 and P=4, so G=5 and C is at most 5

▶ A is at least 6 already, as C is at most 5, it will never be chosen

▶ We don’t need to look further below C: H, Q, and R are pruned

▶ S=9 and T=1, so I=9 and D is at most 9

▶ U=6 and V=3, so J=6, D=6 and A=6