Assignment:
Turn in a hardcopy of your solutions to the following problems.
1. In a typical state space representation of the 8-puzzle, let
be the start state and
be the goal state. We want to solve this problem using the A* algorithm. Operators representing legal moves are U (move the blank space up one), D (down), L (left) and R (right), where the obvious prerequisites ap- ply (e.g., if the blank space is in the top row, it cannot move up). For any state n, let g(n) be the usual cost function, in other words, the number of moves used to reach state n from the start state. Let the heuristic function h(n) be the number of tiles that are not in their goal state positions in state n.
a. Draw the search tree generated by Algorithm A*, using the representation and g and h functions given above, starting from the initial state and going to the point in which five nodes have been expanded and their descendants added to the search tree. When a duplicate state occurs, just discard the duplicate and do not include it in the search tree. Thus your answer should show all non-duplicate nodes generated as suc- cessors to any expanded node during this search. Write each node's g, h and f values, along with a written word (first, second, third, etc.) indicating the order in which that node was expanded, next to every node. Also write the operator used (U, D, L or R) next to each corresponding arc/link between states.
b. Put an asterisk next to all leaf nodes in the search tree you produced in (a) that could legally be the next node expanded by this A* algorithm should the search process continue (but don't expand any of them).
c. Suppose that instead of using the h(n) function defined above, the A* algorithm used an h(n) that was one half of the number of tiles that are not in their goal state positions in state n. Would the resulting pro- cedure be guaranteed to find a minimal cost path to the goal state? Why or why not?
2. Consider a puzzle consisting of 4 tiles on a rectangular board with room for 5 tiles in a row. There are two black (B) tiles and two white (W) tiles, e.g., state WBWEB of the board is:
where E is an empty space or cell. The goal of this puzzle is to reach any state in which all of the W tiles are to the left of all of the B tiles. Note that there is more than one such state. Allowed moves, which can be in either direction, are as follows:
- a tile may move into an adjacent empty cell
- a tile may jump over an adjacent tile into an empty cell
- a tile may jump over two adjacent tiles into an empty cell
For example, any of the four tiles in the state pictured above could legally move to the empty space. Con- sider the heuristic function h(board) with
h(board) = i=1Σ5 (white(i,board) + empty(i,board))
where: white(i,board) = i; if the ith board position has a white tile, and 0 otherwise;
empty(i,board) = i/2 if the ith board position is empty, and 0 otherwise.
For example, for the board position WBWEB above h = 1 + 3 + 2 = 6. Lower values of h are "better". Let the cost g(board) be the number of moves needed to reach that board state from the start state.
a. Draw the search tree generated by Algorithm A*, using the given g and h functions, from the initial state BBWWE (not pictured above!) to a goal state. Show all nodes generated as successors to any expanded node during this search. Whenever a duplicate state is generated, discard it and do not add it to the search tree. Write each node's g, h, and f values next to the nodes.
b. Suppose that, even though one solution has been found, it was desired to continue the search process to see if additional paths to a goal state could also be found. Place an asterisk next to all of the non-goal leaf nodes in your search tree in (a) that could legally be the next state expanded by Algorithm A* were the search to continue (but don't expand them).
c. Yes or no: Is the h function that we use above admissible? Explain your answer.
3. Consider the game tree pictured below, where MAX and MIN are indicated in the usual fashion. Leaf node labels indicate the results of applying an evaluation/value function from MAX's viewpoint to the game states. To produce what you turn in, you can either print this page and record your answers on the printed page, or you can just draw everything by hand.
a. Write the backed-up minimax value for each and every non-leaf node in the game tree next to that node.
b. Place an asterisk by the arc representing the move that MAX would select based on (a).
c. Suppose that instead of using minimax search, alpha-beta search is being used, working from left to right in the search tree. Draw a short horizontal line through the arc where the first cut-off would occur, labeling this as either an alpha or a beta cutoff.