Instructions: Compile all solutions to the written problems on this assignment in a single PDF
file (typed, or handwritten legibly if absolutely necessary). Coding solutions may be directly imple
mented in the provided Python file(s). When ready, follow the submission instructions to submit
all files to Gradescope. Please be mindful of the deadline, as late submissions are not accepted, as
well as our course policies on academic honesty.
Problem 1: Wordle (15 points)
Let’s describe the game of Wordle as a task environment. This is a single-player game in which
the objective is to guess a hidden word in six tries or fewer. For each incorrect guess that the
player (agent) makes, the computer (environment) responds with hints regarding whether a letter
is actually present in the hidden word and if it is in the right place, or if a letter does not appear in
the hidden word at all. We only consider the “hard” version of the game, in which each subsequent
guess must be consistent with all hints so far.
(a) Give a state space description of this problem. What information should individual states
contain? What are the valid actions that an agent can take in each state?
(b) Classify this task environment according to the six properties discussed in class, and include a
one- or two-sentence justification for each. For some of these properties, your reasoning may
determine the correctness of your choice.
Problem 2: Utilities and Preferences (15 points)
Consider two lotteries L1 = [p, A; 1 ! p, C] and L2 = [q, B; 1 ! q, L1], where A > B > C > 0.
(a) Compute U(L2). For what value of p is U(L2) a fixed value independent of q?
(b) Suppose that L1 ” L2. Is it guaranteed that p > q? Explain why or why not. (You may use a
counterexample to prove your assertion if your answer is no.)
(c) L2 can be represented as a lottery with each of A, B, and C as three separate outcomes. Solve
for p and q in terms of A, B, and C such that each of the three outcomes has the same expected
utility when weighted by their likelihoods.
Problem 3: Monty Hall (20 points)
This is a variation of the famous Monty Hall problem. Suppose you are a contestant on a game
show and you have to open one of 50 closed doors. Behind one door is a job o↵er from a FAANG
company (U = 100). Behind another door is your school tuition bill (U = !10). Behind all other
doors is a goat (U = 1).
(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
(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
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: firstname.lastname@example.org 微信号:vipnxx