READABLE COPY of Quiz 4 (Search Lecture 7, Game Tree Search Lectures 1 & 2)
Started: Dec 2 at 3:25am
Quiz Instructions
Question 1 10 pts
Consider state space show above. We are doing A* search with initial state A and the goal being state D.
Consider the following heuristics and then answer the questions below. In this table each row specifies one heuristic. So for example h1(A) = 8, h1(B) = 3, h1(C) = 7, h1(D) = 0
Heuristic
A
B
C
D
h1 8370
h1 8370
h2
10
6
7
0
h3
9
5
7
0
h4
8
4
6
0
h5
9
6
8
0
Answer the following questions.
Note an alternative definition of a heuristic being monotonic, that is sometimes easier to apply, is as follows:
If for every two states X and Y in the state space and every action k that transitions from X to Y (with cost equal to cost(X,k,Y) )we have that
h(X) ¡Ü cost(X,k,Y) + h(Y) then h is monotonic.
1. h1 is
2. h2 is
3. h3 is
4. h4 is
5. h5 is
[ Select ]
[ Select ] [ Select ] [ Select ] [ Select ]
and [ Select ] and [ Select ] and [ Select ] and [ Select ] and [ Select ]
Question 2 10 pts
Say that heuristic h is perfect. That is h(n) = h*(n) for every state n. Let X and Y be two states and k an action that transitions from X to Y (with cost equal to cost(X,k,Y)).
Answer the following two questions. Question 1:
Give a short explanation (three sentence maximum) for why it must be the case that.
cost(X,k,Y) + h(Y) ¡Ý h(X)
(Long answers will have marks deducted. Very long answers will get zero.)
Question 2. Is h*(n) monotonic? Just give a yes/no answer.
View keyboard shortcuts
p View keyboard shortcuts Accessibility Checker 0 words
Switch to raw html editor Fullscreen
Edit View Insert Format Tools Table
12pt Paragraph
Question 3 1 pts
Answer the following questions about A* search when it is using an admissible heuristic.
In these questions: C* always represents the cost of an optimal solution and all paths p mentioned start at the initial state.
1. Ifwehaveapathpwithf(p)
[ Select ]
3. For any path p (starting at the initial state!) it must be that
[ Select ]
4. If p is returned by A* as a solution then
5. If S is an arbitrary state, and A* uses cycle checking and a monotonic
heuristic, then it will never expand more than one path to S [ Select ]
6. If S is an arbitrary state, and A* uses cycle checking and an admissible heuristic that is not monotonic, then it will never expand more than one path to
[ Select ]
[ Select ]
S
Question 4 15 pts
In the game tree above the game positions are indicated by nodes in the tree.
MIN nodes are circular, MAX nodes are square, and TERMINAL nodes are triangular. The utility (for MAX) of each TERMINAL node is written inside the node.
Question A:
For each (game position A-v) give the position’s minimax value (i.e., value for max under a minimax strategy). Give your answers in a table formatted in the following way: (hint, the answers for h-v really are as obvious as you think)
Position
minimax value
Position
minimax value
A
B
C
D
EF
E
F
G
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
Question B.
When we do alpha-beta search on this game tree each non-pruned position (node) will be visited by calling the alpha-beta algorithm with that position as an argument. In addition, when the alpha-beta algorithm is invoked on that position it will also be invoked with particular alpha and beta bounds that will be used to perform cuts in the subtree below that position.
In a table like that below, for each game position indicate if that position is visited by the alpha-beta algorithm. If the position is visited then (1) give the alpha and beta bounds that are passed to the alpha-beta algorithm when it is called on that position, (2) the minimax value for that position returned by alpha- beta, and (3) for non-terminal nodes only the move that is returned by alpha-beta (specify the move as the position that alpha-beta recommends the player at the passed position move to next).
Note, for each position in the game tree either you will specify the passed alpha- beta bounds, minimax value, and move returned by alpha-beta or you will specify that the position is not visited by alpha-beta. Do not try to specify the alpha and beta bounds, minimax value or returned move on positions that are not visited.
We have filled in some of the answers to give you examples of the expected format. Note that in at the terminal node h, no move is returned as h is a terminal node.
Visited
Passed in
Passed in
minimax
move
Position (Yesor alpha beta returnedby
Position (Yesor alpha beta value returnedby No) bound bound alpha-beta
A Y -inf inf
B5k
C
D
E
F
G
h Y -inf inf 8
iY6
j
k
l
m
n
o
p
q
r
s
t
u
v
View keyboard shortcuts
p View keyboard shortcuts Accessibility Checker 0 words
Switch to raw html editor Fullscreen
Edit View Insert Format Tools Table
12pt Paragraph
Saving…
Submit Quiz