game tree using Expectiminimax with alpha-beta pruning. Node names are given to the left of each node and probability values are given on the top of individual nodes.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

1. Game Playing (6 points)

Section A

Fill out the game tree below by solving it using Expectiminimax with alpha-beta 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 weird-looking 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 weird-looking 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 A-star 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 40-minute 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 three-point 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 5-minute

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 

Attachments:

Expert's Answer

846 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

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. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

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

. 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 Sea Ports. Here are the classes and their instance variables we wish to define:

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