# 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.