1. Game Playing (6 points)
Section A
Fill out the game tree below by solving it using Expectiminimax with alphabeta pruning. Node
names are given to the left of each node and probability values are given on the top of individual
nodes. The evaluation function is bounded by [8, 8]. Evaluate the tree from left to right.
1.A.1 Answer the questions below, using the appropriate inequality signs, if needed. For
example, if A is less than or equal to 3, write its value as “<= 3”. If a node is never
explored, write its value as “N/A”.
a. What is the value of A: _______________ (0.75 points)
b. What is the value of B: _______________ (0.75 points)
c. What is the value of D: _______________ (0.75 points)
d. What is the value of J: _______________ (0.75 points)
e. What is the value of K: _______________ (0.75 points)
f. What is the value of L: _______________ (0.75 points)
Page 2 out of
374 3 7 3 1 5 3
g. Total number of pruned nodes under the subtree of node B (including B) is
__________ and under the subtree of node C (including C) is __________ and
under the subtree of node D (including D) is __________. (If a pruned node has
two children, mark all three as pruned and count the number of pruned nodes as
3) (1.5 points)
Page 3 out of
2. Search (6 points)
Section A
On one day of adventure, Dakota found a weirdlooking door in a cave. Hanging on the door
was a puzzle there that Dakota must solve to finally get access to the secret recipe of a special
cheese that is said to grant immortality to whoever eats it.
The puzzle takes on the look of a 2 by 2 board, with numbers on each cell having the value of:
We will denote the starting game board as Ա
Luckily, Dakota need not to scratch head over the meaning of the numbers, as a mysterious
merchant once handed over a note, telling Dakota of the rules of the lock:
In one round, one of the following actions could be performed:
a. One cell could be either incremented or decremented, and will have a cost of 1
b. Two different cells could be swapped, and this action will have a cost of 2
Attached with the note was a sheet drawing the goal state, which we denote as : Բ
Page 4 out of
On one day of adventure, Dakota found a weirdlooking door in a cave. Hanging on the door
was a puzzle there that Dakota must solve to finally get access to the secret recipe of a special
cheese that is said to grant immortality to whoever eats it.
The puzzle takes on the look of a 2 by 2 board, with numbers on each cell having the value of:
We will denote the starting game board as Ա
Luckily, Dakota need not to scratch head over the meaning of the numbers, as a mysterious
merchant once handed over a note telling Dakota of the rules of the lock: merchant once handed over a note, telling Dakota of the rules of the lock:
We will locate the cell at the ith row and jth column for a board as
Ւ, Փ
Dakota decided to use Astar search to find the set of operations with the minimum cost to
change the starting game board to exactly the same state as , and needs your help in Ա Բ
determining the best strategies.
The indicator function is defined below. It is used in parts of the problem.
Ը(ա
1
, ա
2
) =
0 ՒՏ ա
1
= ա
2
1 ՝ℎՎ՛ՠՒ՜Վ
2.A.1 Heuristic  For a starting board and a goal board (both and will be 2 by 2 boards), Դ Ե ԴԵ
which of the following heuristics will guarantee to find the solution with the smallest cost
using A* search? Check all that apply. (2 points)
Ւ = 1
2
∑
Փ = 1
2
∑ Դ
Ւ, Փ − Ե
Ւ, Փ
 +
Ւ = 1
2
∑
Փ = 1
2
∑ Ը(Դ
Ւ, Փ
, Ե
Ւ, Փ
)

Ւ = 1
2
∑
Փ = 1
2
∑ ԴՒ, Փ − Ե
Ւ, Փ
 +
Ւ = 1
2
∑
Փ = 1
2
∑ Ը(Դ
Ւ, Փ
, Ե
Ւ, Փ
)

Ւ = 1
2
∑
Փ = 1
2
∑ Դ
Ւ, Փ − Ե
Ւ, Փ

Ւ = 1
2
∑
Փ = 1
2
∑ ԴՒ, Փ − Ե
Ւ, Փ

0
None of the above
2.A.2 See questions below
a. What is the minimum cost to turn the starting game board into the goal state ? Ա Բ
(2 points)
_____________________________________________________
b. What is the minimum number of rounds needed such that Dakota could still turn
the starting game board into the goal state with the minimum cost? Ա Բ (1 point)
_____________________________________________________
2.A.3 Heuristic  By following an ancient ritual and making drawings with unclear meanings,
Dakota can now increase or decrease each cell by up to 2 with the same cost of 1. For a
starting board and a goal board (both and will be 2 by 2 boards),which of the Դ Ե ԴԵ
following heuristics will guarantee to find the solution with the smallest cost using A*
search? Check all that apply. (1 point)
Ւ = 1
2
∑
Փ = 1
2
∑ Դ
Ւ, Փ
− Ե
Ւ, Փ

2 +
Ւ = 1
2
∑
Փ = 1
2
∑ Ը(Դ
Ւ, Փ
, Ե
Ւ, Փ
)

Ւ = 1
2
∑
Փ = 1
2
∑ ԴՒ, Փ
− Ե
Ւ, Փ

2 +
Ւ = 1
2
∑
Փ = 1
2
∑ Ը(Դ
Ւ, Փ
, Ե
Ւ, Փ
)
Ւ = 1
2
∑
Փ = 1
2
∑ Դ
Ւ, Փ
− Ե
Ւ, Փ

2

Ւ = 1
2
∑
Փ = 1
2
∑ ԴՒ, Փ
− ԵՒ, Փ

2
None of the above
3. Optimization Algorithms (8 points)
Section A
Gradient descent is an optimization technique that can be used to find the local minimum of
some differentiable function. It is extremely useful for training neural networks where it is used to
minimize some loss function which enables the network to learn better parameters. The gradient
descent update rule is wn+1 ← wn  ɑ∇f(wn) where ɑ is the learning rate. Suppose we have some
model given by ŷ = w(x + x2
). Notice that w is a shared parameter in this model. Normally there
can be many parameters but in this case we will use only one. Say we input a few data points to
this model, given by x = [0.6, 0.2, 0.1, 0.9], and the true values of this model for these data
points are represented by y = [0.192, 0.128, 0.088, 1.368]. Let our loss function for this model
be represented by the sum of the squared differences between the model output and the actual
values (L(y, ŷ) = Σi=1n (y  ŷ)
2
).
Use the gradient descent update rule for five iterations to update the parameter w. Let w0 = 0
and use a learning rate of 0.1.
3.A.1 What is ∂L/∂w ? Mark all that apply (1 point)
Σi=1n 2(wxi + wxi
2  yi
)(xi + xi
2
)
Σi=1n 2(wxi + wxi
2  yi
)(w + 2wxi
)
Σi=1n (wxi + wxi
2  yi
)(xi + xi
2
)
Σi=1n (wxi + wxi
2  y)(w + 2wxi
)
Σi=1n 0.5(wxi + wxi
2  yi
)(xi + xi
2
)
2Σi=1n (wxi + wxi
2  yi
)(xi + xi
2
)
Σi=1n 0.5(wxi + wxi
2  yi
)(xi + xi
2
)
3.A.2 Fill out the table with the appropriate value of wi
. (2 points)
i wi
1
2
3
4
5
Page 7 out of
3.A.3 We know that the true global minimum for this model is 0.8. Which of the following
learning rates would result in w5 being less than 0.1 away from the global minimum? (2
points)
0.05
0.15
0.20
0.25
0.30
Section B
3.B.1 Increasing the learning rate will always result in faster convergence. (1 point)
True
False
3.B.2 For any differentiable function, gradient descent will always converge to a global
minimum. (1 point)
True
False
3.B.3 Ridges or plateaus do not alter the performance of local search methods in continuous
spaces. (1 point)
True
False
Page 8 out of
4. Constraint Satisfaction (8 points)
Section A
The chart below shows the heights and averages per game for several metrics for 10
players on a basketball team. We would like to optimize lineups of these players over the
course of a 40minute game relative given the constraints listed below.
Abbreviation: PTS = Average Points Per Game
REB= Average Rebounds Per Game
AST= Average Assists Per Game
3PT%= Three point percentage
FT% = Free throw percentage
1. There must be at least one player in the game who averages at least 20 points per game
at all times.
2. There must be at least one player in the game who averages at least 8 rebounds per
game at all times.
3. There must be at least one player in the game who averages at least 5 assists per game
at all times.
4. There must be at least two players who have a threepoint percentage of at least 35
percent in the game at all times.
5. No player can play more than 10 minutes in a row.
6. There can be no more than one player taller than 6’9” in the game at the same time.
7. There can be no more than one player shorter than 6’5” in the game at the same time.
8. No player who shoots less than 75% at the free throw line can be in the game during the
last 5 minutes.
9. Substitutions can only be made at each 5 minute mark.
10. Exactly 5 players must be on the floor at all times.
11. Player C cannot play more than 20 minutes for the entire game
Page 9 out of
4.A.1 Which of the above are unary constraints? Provide a comma separated list of constraints
(use the corresponding numbers above to denote the constraints). (2 points)
____________________________________
4.A.2 Which of the above are binary constraints? Provide a comma separated list of
constraints (use the corresponding numbers above to denote the constraints). (2 points)
____________________________________
4.A.3 Below is a chart marking each player who is in the game at the beginning of a 5minute
interval. For example, “Start” indicates the interval beginning at the start of the game,
the column labeled “35” indicates the interval beginning with 35 minutes left in the game,
and so on, with each interval lasting for 5 minutes. Provide a valid configuration for all
40 minutes of the game in the table below by filling in the missing values (each column
must have at least five X’s, i.e. five players in the game). For example, if you want to
include player A in a lineup in the interval beginning at the start of the game, mark an X
in the appropriate column (Start) and row (A) combination. (4 points)
Page 10 out of
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
1 Project 1 Introduction  the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
1 Project 2 Introduction  the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of