Python代写｜AI Homework 2

这是一个美国的Python人工智能作业代写

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.

Suppose that we have an admissible heuristic function h for a search problem. You may assume
that all costs and heuristics are nonnegative. Parts (a) and (b) are questions regarding an arbitrary
problem; parts (c) and (d) specifically refer to the search graph shown below.

(a) Suppose that h is also consistent. Consider the f-cost of some node n, where f(n) = g(n)+h(n).

Let n0 be a successor of n. Explain why we can guarantee that f(n0) ! f(n).

(b) Explain why the above observation helps us to conclude that the first time that a node is
expanded, it must be along the cheapest path to it. In other words, such a node will never be
re-expanded later along a cheaper path.

(c) If h is inconsistent, a node may have to be expanded more than once in order to find the
optimal path to it. Find the lower and upper bounds on an admissible heuristic at
each node, such that node C is guaranteed to be expanded twice by A⇤ search. These ranges
should be expressed in terms of specific values (e.g., h(S) < x) or other known heuristic values
(e.g., h(A) < f(h(S)).

(d) The idea of weighted A⇤ is that we can start with an admissible heuristic function and scale all
heuristic values by a constant ↵ larger than 1. This can lead to a suboptimal solution but more
e!cient search. Come up with a set of inequalities in terms of the heuristic values and
the multiplier ↵ that would ensure that weighted A⇤ returns S, B, C, G (and thus avoids
expanding A). Then give an example of a consistent heuristic function (one value for each
node) along with an ↵ value that satisfies these inequalities.

Two players are playing a modified tic-tac-toe game in which grid spaces have point values, shown
on the left grid below. The players take turns marking a grid space with their own designation (X
or O) until either one player gets three marks in a row or the board has no empty spaces. When
the game ends, a score is computed as the sum of the values of the X spaces minus the sum of the
values of the O spaces. In addition, if X has three in a row, 3 points are added to the score; if O
has three in a row, 3 points are subtracted from the score. X seeks to maximize the total score and
O seeks to minimize it.

(a) The right grid shows the current board configuration, whose current value is “3. It is X’s turn
to move. Draw out the entire game tree with the root corresponding to the current board. Use
game tree convention to draw the MAX and MIN nodes. Also sketch out the tic-tac-toe board
configuration for each terminal node (e.g., draw them right below each node).

(b) Compute the minimax values of each node. What is the best move for X to make, and what is
the expected score of the game assuming both players play optimally?

(c) Suppose we are performing alpha-beta search. In what order would the successors of the root
node have to be processed in order to maximize the number of nodes that can be pruned?
Identify the node(s) in the game tree that can be pruned, and find the ↵, “, and v values of
the parent node right before pruning occurs.

(d) Suppose that instead of playing to minimize the score, player O chooses a random valid move
with uniform probability. Explain how the game tree will change (you do not have to redraw
it), and compute the new utility and best move for X starting from the current state.