Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP-424: Artificial intelligence, Fall 2023

Homework 2

Due on myCourses Friday Oct 20, 9:00pm.

General instructions.

• This is an individual assignment.  You can discuss solutions with your classmates, but should only exchange information orally, or else if in writing through the discussion board onEd.  All other forms of written exchange are prohibited.

• Unless otherwise mentioned, the only sources you should need to answer these questions are your course notes, the textbook, and the links provided. Any other source used should be acknowledged with proper referencing style in your submitted solution.

• Submit one single pdf of your responses through myCourses.

Question 1: Belief in the Turtle [50]

Consider an unobservable state planning problem where N balls can start anywhere within the puzzle shown here. The Turtle has 4 rings, separated by walls with a specific pattern of gaps you can see in the left image. Our job is to find a series of actions that leads to all the balls being in Ring 1, regardless of   where they started (a conformant plan).

We will simplify the game to 4 critical positions per ring: up, down, left and right. Four actions, with the same names mean we tip the puzzle in that direction and hold it until all balls come to rest. Ignore ball collisions. Balls roll along the rings, resting when they either balance stably on top of a “hill” or at the bottom of a “cup”. Balls pass through any “gap” they touch at any point in their path if the current action is aligned with the gap. Examples:

1.   One ball starting at 2U passes the gap with action down, resting on the hill at 1U. After left it rolls into the cup at 1L. Finally, after down it ends at 1D.

2.   One ball starting at 4R, passes the gap with action left, resting at 3R. After down it rolls to 3D. Finally, after left, it rolls to the cup at 3L but doesn’t stop there due falling through the gap to 4L.

3.   Three balls starting at 4U, 4U and 4U, under the action sequence right, left, up all end at 3U.

4.   Three balls starting at 1R, 2U, 3D under the action up, end at 2U, 2U, and 2D.

Question 2: Search and Game Playing [50]

You are playing the dots andboxes game on a 3x3 grid shown below. Each player must draw an edge connecting two dots, if it doesn’t already exist. The player who draws the 4th line that completes a small square receives a +1 score. The overall square surrounding the whole game does not count. After all 4 missing edges have been completed, the utilities will lay between +3 (first/max player completed all 3 boxes) and -3 (second/min player completed all 3 boxes).

It’s the max player’sturn.

a)   Draw a full minimax search tree for this game using the order A(leftmost) to D(rightmost) to organize your diagram.

b)   Apply the alpha-beta pruning method using the same order of node expansion and show the alpha-beta values for all nodes. Is there any advantage to using alpha-beta pruning with this ordering? Write out one of the orderings that leads to the most pruning. If you cannot find one, explain why not.