+1(978)310-4246 credencewriters@gmail.com
Select Page

CS 4660: Artificial Intelligence
Fall 2022
Assignment 1
Due 11:59pm September 9th, 2022
Directions: Complete questions 1-4 below. Submit 1 PDF document with your answers
(Typed or Handwritten and Scanned)
1. (25 pt) Consider the game of Chess (https://en.wikipedia.org/wiki/Chess).
Approximately how many different states can a chess game have? You may assume
a. We do not consider pawn promotion
b. We consider each pawn is a distinct piece
c. We consider only states with no captured pieces, i.e all states will have
32 pieces
d. We do not consider pawn promotion, castling, or any other special cases.
be mathematically correct, but should be in the right magnitude for the assumptions
2. (25pt) A farmer has just bought a wolf, a goat, and a cabbage. They must cross the
river to get home, but their small rowboat can only carry the farmer and 1 animal or
vegetable at a time. However, the farmer cannot leave the goat unsupervised with
the cabbage, or the goat will eat the cabbage. Similarly, the farmer cannot leave the
goat unsupervised with the wolf, or the wolf will eat the goat. Draw the full search
space starting from the initial state below. Indicate with different colors or labels
which states would not be further explored because something gets eaten, as well as
which states would not be further explored because they are repeats of previous
states (to avoid cycles)
Initial State
Goal State
FWGC
FWGC
3. (25pt) Consider the following state space graph with Initial State S and Goal State G
2
S
3
2
1
C
A
4
7
B
F
3
4
6
1
9
D
2
E
5
6
G
a. (5pt) Draw out the complete search tree, ignoring cycles by not allowing the
same node in the path more than once. The tree has been started below to
show formatting.
S
SA
SB
SC
SF
b. (5pt) List the Node exploration order for a Breadth First Search. For grading
simplicity, when there is a tie, explore the nodes alphabetically.
c. (5pt) List the Node exploration order for a Depth First Search. For grading
simplicity, when there is a tie, explore the nodes alphabetically.
d. (5pt) The table below shows the estimated distance from each node to the
goal. Using these as the heuristic h(n), list the Node exploration order for a
Best-First Search. For grading simplicity, when there is a tie, explore the nodes
alphabetically.
e. (5pt) Using the same table as the heuristic h(n), list the A* Node exploration
order. For grading simplicity, when there is a tie, explore the nodes
alphabetically.
S
A
B
C
D
E
F
G
10
5
8
3
2
4
9
0
4. (25pt) Consider the grid below with start state 50 and goal state 49:
Draw the search tree for the following algorithms a-d assuming:
â— Black squares are walls that cannot be passed through.
â— Break ties in the order N-E-S-W.
â— Each step has a uniform cost.
â— The heuristic is the manhattan distance to the goal.