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.

State any other assumptions made and show your work. Your answer does not have to

be mathematically correct, but should be in the right magnitude for the assumptions

you have made and make sense based on your math.

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.

a. (5pt) Breadth-First Search

Only show the first 5 layers of the tree. The goal will not be reached.

b. (5pt) Depth-First Search

c. (5pt) Beam Search with W=2

Only show the first 5 layers of the tree. The goal will not be reached.

d. (5pt) A*

e. (5pt) What is the optimal path found by A*

Purchase answer to see full

attachment