Test 1        Name __________________        Score __

1. Three blocks, A, B, C are initially on the floor as:
    

   A

   B

   C

   and goal is the blocks are to be stacked as:

   A

   B

   C

   Problem constraints are:

   • An agent can move only one block at a time.
   • A block can only be placed on another block.
   • A block can be moved from on top of one block to another.
   • The agent stops when three blocks are stacked.

   Diagram the full state space.

Number the search tree nodes as added to the fringe by depth-first search and breadth-first search.

2. Uniform cost (or Branch and Bound or Dijkstra's algorithm)

   g(n) is the path cost to node n. Always expand least cost node first placing in queue ordered by path cost g(n). From our map, the step cost is the distance between towns.

   Give the next three fringe values starting from initial state Sibiu.

    

   Map of Romania with straight-line distances to Bucharest on right

   

3. Trace the operation of A* applied to the problem of getting to Bucharest from Craiova using the straight-line distance heuristic. That is, show the sequence of nodes the algorithm will consider and the f, g and h score for each node.
4. What is the number of possible states for placing one queen on an empty 4x4 board?
5. What is the number of possible states on a 4x4 board after placing 1 queen?
6. What are the total number of possible states for the 4-queens problem?
7. Describe an appropriate fitness function for a genetic algorithm solution to the 8-puzzle. The initial and goal states are:

   Initial            Goal

   283                123
   164                8  4
   7  5                765

8. Binary CSP discussed in class is specified by four inputs:
   1. VARIABLES      - A list of variables; each is atomic (e.g. int or string).
   2. DOMAINS         - Possible values for each variable.
   3. NEIGHBORS     - For each variable lists the other variables that
                               participate in constraints.
   4. CONSTRAINTS - A binary function f(A, a, B, b) that returns true if
                               neighbors A, B satisfy constraint with values A=a, B=b.

Define the four inputs for a palindrome CSP of length 5 (e.g. 'abcba').

9. For the game tree at right, give the Minimax values.
10. For the game tree at right, give the alpha-beta values.
11. For the game of Nim, what are the successor states of  [8, 1]?