(a) Compute the expected utility of opening a door at random.

(b) Suppose you’ve chosen a door. Before you open it, the show host offers to open 5 doors with a goat behind them. What is the expected utility of switching to another door choice?

(c) Is it better to stick with your original door or switch to another one?  Compute the value of information of seeing 5 doors that are hiding goats.

(d) The 5 doors have been revealed and there are now 45 unopened doors left.  The show host offers to open your initially chosen door, after which you can either claim that door’s prize or open another unopened door. What is the expected utility of this offer?

Problem 4:  Search Practice (15 points)

In the state space graph below, S is the start state and G1 and G2 are both possible goal states. Costs are shown along edges and heuristic values are shown in the rectangles next to each node. Assume that search algorithms expand states in alphabetical order when ties are present (G1 comes before G2).

(a) List the ordering of the states expanded as well as the solution (as a state sequence) returned by each of DFS, BFS, and UCS. Assume that DFS and BFS use the early goal test. Assume that all algorithms use a reached table.

(b) For what range of values is h an admissible heuristic?  For what range of values of h does A∗ return a suboptimal solution? For what range of values of h does A∗ expand fewer nodes than UCS?

Problem 5: Word Ladders (35 points)

In this problem you will implement and compare the performance of the various implementations of best-first search on word ladder puzzles.  Given two English words, the goal is to transform the first word into the second word by changing one letter at a time.   The catch is that each new word in the process must also be an English (dictionary) word.  For example, given a start word “fat” and a goal word “cop”, a solution would be the word sequence “fat”, “cat”, “cot”, “cop”.

In our implementation, possible words will correspond to different states. Successor states are thus words that differ from the given word by one letter.  Using this idea, we provide a successors function that returns a list of “actions” and successor states given a state.  The action is simply the index of the changed letter.  This function uses the pyenchant library to perform dictionary checking. Finally, the “cost” of each action can simply be treated uniformly (e.g., 1).

To perform search, we represent a search tree node using a Python dictionary containing three components: state, parent, and cumulative cost (keeping track of action is not useful for us here). For example, the root node may be defined as {’state’:start,  ’parent’:None,  ’cost’:0}. The frontier can be implemented as a list and the reached set as a dictionary of states and costs.

5.1: Best-First Search (15 points)

Use the provided successors function to implement best-first search. The arguments are the start state, goal state, and priority function. Your function should implement the frontier and reached set as described above. You are recommended, but not required, to write a separate helper function for node expansion. The search should conclude once the goal state is found.

To simulate priority queue behavior of the frontier,  the heapq module,  and in particular the heappush and heappop functions, can be used to efficiently treat regular Python lists using a priority function.   In order to  “sort” the nodes in the frontier, you can first place each node within a data structure like a tuple, so that the first element captures the priority value and the last element is the node itself.  For example,  (1, node1) would be ordered before  (2, node2). Note that if the first elements of two tuples are equal, they are then compared according to their second elements, followed by their third and so on.  For this problem, you should break ties (and thus include an additional element between the f-cost and node) by alphabetical order of the states.

In addition to returning the node containing the goal, your function should also update and return two additional quantities:  nodes expanded and frontier size.  The first is an integer that is incremented every time that a node is expanded. The second is a list that contains the size of the frontier at each iteration of the search, updated before a node is popped.

5.2: Priority Functions (5 points)

Given a working implementation of best-first search, it remains to write the different priority func- tions that lead to the various search algorithm behaviors. A priority function takes in a node and the goal state as arguments, although the latter does not necessarily have to be used (particularly by uninformed search algorithms). Implement the priority functions for depth-first search, breadth- first search, and uniform-cost search. You should be able to do each with just a single line of code; they should all look quite similar (perhaps even identical).

A priority function for A∗ search should use a suitable heuristic. The Hamming distance between the current state and goal state can act as a heuristic; this is simply the number of letters that are different between the two words. Implement the priority function for A∗ search using the Hamming distance as a heuristic.