Fundamentals of Artificial Intelligence
Laboratory
Dr. Mauro Dragoni
Department of Information Engineering and Computer Science Academic Year 2020/2021
Exercise 5.1
page 02
Minimax with alpha-beta pruning
MAX nodes. The goal at a MAX node is to maximize the value of the subtree rooted at that node. To do this, a MAX node chooses
the child with the greatest value, and that becomes the value of the MAX node.
MIN nodes. The goal at a MIN node is to minimize the value of the subtree rooted at that node. To do this, a MIN node chooses the
child with the least (smallest) value, and that becomes the value of the MIN node.
α: Alpha is the maximum lower bound of possible solutions. It is equivalent to ≥ -∞
β: Beta is the minimum upper bound of possible solutions. It is equivalent to ≤ ∞.
Exercise 5.1
page 03
Minimax with alpha-beta pruning, tips:
• When any new node is being considered as a possible path to the solution, it can only work if:
α ≤ N ≤ β
α
β
Exercise 5.1
page 04
Minimax with alpha-beta pruning, tips:
• When any new node is being considered as a possible path to the solution, it can only work if:
α ≤ N ≤ β
α
β
Exercise 5.1
page 05
Minimax with alpha-beta pruning, tips:
• When any new node is being considered as a possible path to the solution, it can only work if:
α ≤ N ≤ β
α
β
Exercise 5.1
page 06
Minimax with alpha-beta pruning
3 17 2 12 15 25 0 2 5 3 2 14
α= -∞ ; β= ∞
α= -∞ ; β= ∞ α= -∞ ; β= ∞
α= -∞ ; β= ∞ α= -∞ ; β= ∞ α= -∞ ; β= ∞ α= -∞ ; β= ∞
α= -∞
β= ∞ α= -∞
β= ∞
α= -∞
β= ∞ α= -∞
β= ∞ α= -∞
β= ∞ α= -∞
β= ∞
α= -∞
β= ∞
Exercise 5.1
page 07
Minimax with alpha-beta pruning
α= -∞ ; β= ∞
α= -∞ ; β= ∞
Exercise 5.1
page 08
Minimax with alpha-beta pruning
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= -∞ ; β= ∞
Exercise 5.1
page 09
Minimax with alpha-beta pruning
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= -∞
β= ∞
Exercise 5.1
page 010
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= -∞
β= ∞
Exercise 5.1
page 011
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= -∞
β= 3
Exercise 5.1
page 012
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= -∞
β= 3
17
Exercise 5.1
page 013
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= 3 ; β= ∞
α= -∞
β= 3
17 3
Exercise 5.1
page 014
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= ∞
Exercise 5.1
page 015
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= ∞
2
Exercise 5.1
page 016
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
Exercise 5.1
page 017
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
α
β
Exercise 5.1
page 018
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= ∞
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2 3
Exercise 5.1
page 019
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2 3
Exercise 5.1
page 020
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= -∞ ; β= 3
Exercise 5.1
page 021
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= -∞ ; β= 3
α= -∞
β= 3
Exercise 5.1
page 022
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= -∞ ; β= 3
α= -∞
β= 3
15 15
Exercise 5.1
page 023
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
Exercise 5.1
page 024
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
Exercise 5.1
page 025
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
α
β
Exercise 5.1
page 026
Minimax with alpha-beta pruning
3
α= -∞ ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15 3
Exercise 5.1
page 027
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15 3
Exercise 5.1
page 028
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
3 α= 3 ; β= ∞
Exercise 5.1
page 029
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
3 α= 3 ; β= ∞
α= 3 ; β= ∞
Exercise 5.1
page 030
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
3 α= 3 ; β= ∞
α= 3 ; β= ∞
α= 3β= ∞
Exercise 5.1
page 031
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
3 α= 3 ; β= ∞
α= 3 ; β= ∞
α= 3β= ∞
2
Exercise 5.1
page 032
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
3 α= 3 ; β= ∞
α= 3 ; β= ∞
α= 3β= 2
2
Exercise 5.1
page 033
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
3 α= 3 ; β= ∞
α= 3 ; β= ∞
α= 3β= 2
2
2
Exercise 5.1
page 034
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
3 α= 3 ; β= ∞
α= 3 ; β= ∞
α= 3β= 2
2
2 α= 3β= ∞
Exercise 5.1
page 035
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
3 α= 3 ; β= ∞
α= 3 ; β= ∞
α= 3β= 2
2
2 α= 3β= ∞
3
Exercise 5.1
page 036
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
3 α= 3 ; β= ∞
α= 3 ; β= ∞
α= 3β= 2
2
2 α= 3β= 3
3
Exercise 5.1
page 037
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
3 α= 3 ; β= ∞
α= 3 ; β= ∞
α= 3β= 2
2
2 α= 3β= 3
3
3
Exercise 5.1
page 038
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
3 α= 3 ; β= ∞
α= 3 ; β= ∞
α= 3β= 2
2
2 α= 3β= 3
3
3 3
Exercise 5.1
page 039
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
3 α= 3 ; β= 3
α= 3 ; β= ∞
α= 3β= 2
2
2 α= 3β= 3
3
3 3
Exercise 5.1
page 040
Minimax with alpha-beta pruning
3
α= 3 ; β= ∞
α= -∞ ; β= 3
α= 3 ; β= ∞
α= -∞
β= 3
17
3 α= 3β= 2
2
2
3 α= 15 ; β= 3
α= -∞
β= 3
15 15
15
3 α= 3 ; β= 3
α= 3 ; β= ∞
α= 3β= 2
2
2 α= 3β= 3
3
3 3
3
Exercise 5.2
page 041
Expectiminimax
3 17 2 12 25 0 2 5 3 2
a1 a2
Exercise 5.2
page 042
Expectiminimax
3 17 2 12 25 0 2 5 3 2
a1 a2
0.2
0.5
0.3 0.7 0.3
Exercise 5.2
page 043
Expectiminimax
3 17 2 12 25 0 2 5 3 2
a1 a2
0.2
0.5
0.3 0.7 0.3
3 2 0 2 2
Exercise 5.2
page 044
Expectiminimax
3 17 2 12 25 0 2 5 3 2
a1 a2
0.2
0.5
0.3 0.7 0.3
3 2 0 2 2
1.6 2
Exercise 5.3
page 045
LRTA*
1 2 3 4
1 G
2 3
4 S
The agent starts from S, it has to reach G. Each step costs 1. Heuristic is based on Manhattan distance.
In case of same h(s) values, the order of possible actions are: UP, RIGHT, DOWN, LEFT
Exercise 5.3
page 046
LRTA*
1 2 3 4
1 G
2
3 4
4 S (5) 4
1 2 3 4
1 G
2
3 4
4 S (6) 4
1 2 3 4
1 G
2
3 4
4 S (6) 4
Exercise 5.3
page 047
LRTA*
1 2 3 4
1 G
2
3 5
4 S (6) 4
1 2 3 4
1 G
2
3 5
4 S (6) 4
Exercise 5.3
page 048
LRTA*
1 2 3 4
1 G
2
3 5 3
4 S (7) 4 3
1 2 3 4
1 G
2
3 5 3
4 S (7) 4 3
Exercise 5.3
page 049
LRTA*
1 2 3 4
1 G
2
3 5 3
4 S (7) 5 3
1 2 3 4
1 G
2
3 5 3
4 S (7) 5 3
Exercise 5.3
page 050
LRTA*
1 2 3 4
1 G
2 2
3 5 3 2
4 S (7) 5 3
1 2 3 4
1 G
2 2
3 5 3 2
4 S (7) 5 3
Exercise 5.3
page 051
LRTA*
1 2 3 4
1 G
2 2
3 5 4 2
4 S (7) 5 3
1 2 3 4
1 G
2 2
3 5 4 2
4 S (7) 5 3
Exercise 5.3
page 052
LRTA*
1 2 3 4
1 1 G
2 3 2 1
3 5 4 2
4 S (7) 5 3
1 2 3 4
1 G
2 2
3 5 4 2
4 S (7) 5 3
Exercise 5.3
page 053
LRTA*
1 2 3 4
1 1 G
2 3 3 1
3 5 4 2
4 S (7) 5 3
1 2 3 4
1 1 G
2 3 3 1
3 5 4 2
4 S (7) 5 3
Exercise 5.3
page 054
LRTA*
1 2 3 4
1 2 G
2 3 3 1
3 5 4 2
4 S (7) 5 3
1 2 3 4
1 2 G
2 3 3 1
3 5 4 2
4 S (7) 5 3
Exercise 5.3
page 055
LRTA*
1 2 3 4
1 2 G
2 3 4 1
3 5 4 2
4 S (7) 5 3
1 2 3 4
1 2 G
2 3 4 1
3 5 4 2
4 S (7) 5 3
Exercise 5.3
page 056
LRTA*
1 2 3 4
1 2 G
2 3 4 1 2
3 5 4 2
4 S (7) 5 3
1 2 3 4
1 2 G
2 3 4 1 2
3 5 4 2
4 S (7) 5 3
Exercise 5.3
page 057
LRTA*
1 2 3 4
1 2 G
2 3 4 2 2
3 5 4 2
4 S (7) 5 3
1 2 3 4
1 2 G
2 3 4 2 2
3 5 4 2
4 S (7) 5 3
Exercise 5.3
page 058
LRTA*
1 2 3 4
1 2 G 1
2 3 4 2 2
3 5 4 2 3
4 S (7) 5 3
1 2 3 4
1 2 G 1
2 3 4 2 2
3 5 4 2 3
4 S (7) 5 3
Exercise 5.3
page 059
LRTA*
1 2 3 4
1 2 G (0) 1
2 3 4 2 3
3 5 4 2 3
4 S (7) 5 3
Exercise 5.1
page 060
Minimax with alpha-beta pruning
3 17 2 12 15 25 0 2 5 3 2 14
α= -∞ ; β= ∞
α= -∞ ; β= ∞ α= -∞ ; β= ∞
α= -∞ ; β= ∞ α= -∞ ; β= ∞ α= -∞ ; β= ∞ α= -∞ ; β= ∞
α= -∞
β= ∞ α= -∞
β= ∞
α= -∞
β= ∞ α= -∞
β= ∞ α= -∞
β= ∞ α= -∞
β= ∞
α= -∞
β= ∞
