1. Search (30 points)
Figure 1: Search problem description
Imagine we are living the real scene in a science fiction movie in which aliens have launched attacks to our cities. Aliens also cut off all the phone, Internet, electricity and so it forces us to use our memory and common sense to navigate through our cities to safe shelters. Assuming that we are at downtown area (S) and the safe shelters are at location T. Figure 1 above shows how the streets are connected with each other. The edges are labelled with distances and the nodes are labelled with a heuristic estimate to the destination T. When performing search, ties are
oken by choosing the node that is alphabetically first.
1.1 Show a path if using Breadth First Search and a path if using Depth First Search
1.2 Show a path using Best First Search and a path using A* search. Would you find any path returned by A* the same with a path returned by a Best First Search? Why/Why not?
2. Heuristic (30 points)
Figure 2: Heuristic problem
In this search problem shown in Figure 2 above, the number along the edge represents the step cost (g(n) between two nodes. Assuming that we have h(n) = minimum number of arcs between node n and the goal node. Is h(n) an admissible heuristic? Why or why not?
3. Game (30 points)
Figure 3: Game theory problem
a. Using minimax only, indicate the values of the following nodes
A
B
C
D
E
G
I
K
M
. Using minimax only, what is the best next move from A?
c. Now apply minimax with alpha beta to do pruning on the same tree above. Note that alpha, betas are updated before pruning occurs.
According to our recursive minimax algorithm with alpha and beta, what are the final alpha and beta values at node E and node A?
4. First order logic:
XXXXXXXXXXpoints) Consider a vocabulary with the following symbols:
Occupation(p,o): predicate. Person p has occupation o.
Customer (p1,p2): predicate. Person p1 is a customer of person p2.
Boss(p1,p2):predicate. Person p1 is a boss of person p2.
Doctor, Surgeon, Lawyer, Actor: constants denoting occupations
Emily, Joe: constants denoting people
Use these above symbols to write the following assertion in first order logic
a. Emily is either a surgeon or a laye
. Joe is an actor, but he also holds another job.
c. All surgeons are doctors
d. Joe is not a customer of any lawye
e. Emily has a boss who is a lawye
f. There exists a lawyer all of those customers are doctors
g. Every surgeon has a lawyer.
XXXXXXXXXXpoints) Given the following predicates and their associated meaning:
Child(x,y): represents y is the child of x.
Male(x): represents x is a male.
Female(x):represents x is a female.
Spouse(x,y): x is a spouse of y
Sibling (x,y): x is a sibling of y
Please write the following predicates based on the above-given predicates:
Grandchild (x,y), Greatgrandparent(x,y), Ancestor(x,y), Brother(x,y), Sister(x,y)
Daughter(x,y), Son(x,y), FirstCousin(x,y), BrotherInLaw(x,y), SisterInLaw(x,y), Aunt(x,y), Uncle(x,y)
1. Search (30 points)
Figure 1: Search problem description
Imagine we are living the real scene in a science fiction movie in which aliens have launched attacks to our cities. Aliens
also cut off all the phone, Internet, electricity and so it forces us to use our memory and common sense to navigate
through our cities to safe shelters. Assuming that we are at downtown area (S) and the safe shelters are at location T.
Figure 1 above shows how the streets are connected with each other. The edges are labelled with distances and the
nodes are labelled with a heuristic estimate to the destination T. When performing search, ties are
oken by choosing
the node that is alphabetically first.
1.1 Show a path if using Breadth First Search and a path if using Depth First Search
1.2 Show a path using Best First Search and a path using A* search. Would you find any path returned by A* the
same with a path returned by a Best First Search? Why/Why not?
2. Heuristic (30 points)
Figure 2: Heuristic problem
In this search problem shown in Figure 2 above, the number along the edge represents the step cost (g(n)
etween two nodes. Assuming that we have h(n) = minimum number of arcs between node n and the goal node.
Is h(n) an admissible heuristic? Why or why not?
3. Game (30 points)
Figure 3: Game theory problem
a. Using minimax only, indicate the values of the following nodes
A
B
C
D
E
G
I
K
M
. Using minimax only, what is the best next move from A?
c. Now apply minimax with alpha beta to do pruning on the same tree above. Note that alpha, betas are
updated before pruning occurs.
According to our recursive minimax algorithm with alpha and beta, what are the final alpha and beta values at
node E and node A?
4. First order logic:
XXXXXXXXXXpoints) Consider a vocabulary with the following symbols:
Occupation(p,o): predicate. Person p has occupation o.
Customer (p1,p2): predicate. Person p1 is a customer of person p2.
Boss(p1,p2):predicate. Person p1 is a boss of person p2.
Doctor, Surgeon, Lawyer, Actor: constants denoting occupations
Emily, Joe: constants denoting people
Use these above symbols to write the following assertion in first order logic
a. Emily is either a surgeon or a layer
. Joe is an actor, but he also holds another job.
c. All surgeons are doctors
d. Joe is not a customer of any lawyer
e. Emily has a boss who is a lawyer
f. There exists a lawyer all of those customers are doctors
g. Every surgeon has a lawyer.
XXXXXXXXXXpoints) Given the following predicates and their associated meaning:
Child(x,y): represents y is the child of x.
Male(x): represents x is a male.
Female(x):represents x is a female.
Spouse(x,y): x is a spouse of y
Sibling (x,y): x is a sibling of y
Please write the following predicates based on the above-given predicates:
Grandchild (x,y), Greatgrandparent(x,y), Ancestor(x,y), Brother(x,y), Sister(x,y)
Daughter(x,y), Son(x,y), FirstCousin(x,y), BrotherInLaw(x,y), SisterInLaw(x,y), Aunt(x,y), Uncle(x,y)