1. In a tic-tac-toe game, MAX (playing 'O') is about to make his next move from the initial state in the game tree given below. The numbers in circles are node IDs.
Give the utility functions (1 for win, 0 for draw, -1 for loss) for all the leaf nodes (terminal states).
Give the minimax values for all the nodes. Which move(s) should MAX choose?
Determine the nodes that will NOT be checked if α-β pruning is used. (Search is left to right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
19 21 23 24 28 32 34
20
22
25
26
27
31
33
17
18
29
30
35 36 37 38 39 40 41 42
2. For the tic-tac-toe game, design an evaluation function for MAX (playing 'O'). Test the evaluation function on only a 2-ply version of the tree above. This means that the tree only includes nodes 1-16, and the evaluation function is only computed for nodes 5-16.
Clearly explain how your evaluation function is defined. The answer is not unique, but it should be reasonable.
Apply Minimax to the 2-ply tree, and give the minimax values for all the nodes. Which move(s) should MAX choose?
3. This is the map of the Hsinchu area, with the regions represented by letters A to N. We want to assign numbers 1, 2, 3, or 4 to the regions, with adjacent regions having different numbers. To break ties, when multiple regions are equally preferred, choose according to the alphabetical order, and when multiple numbers are equally preferred for an assignment, choose the smallest one.
Draw the constraint graph.
Do backtracking search with forward checking and the MRV, degree, and LCV heuristics. (Apply the heuristics in the order above.) Fill in the spaces below the region and value assigned in each step as well as the domains updated by forward checking.
N M
L
B
A
C
K
D
E
H
F G
I
J
assigned
assigned
updated domains after assignment
region
value
A
B
C
D
E
F
G H
I
J
K
L M N
1234
Using the example case in the textbook/slides (the whether-to-enter-a-restaurant dataset), repeat the process of building a decision tree. When selecting the attribute to be tested at each node, use Gini index instead of Shannon's entropy, and see if the resulting tree is the same or different.
Notes:
Late submission penalty: 10% per day for up to 3 days.
Please submit the assignment through the E3 system.
