Description
PURPOSE:
This assignment provides experiences with Graphsearch, heuristics and A*, and also preliminary experiences with adversarial searchand the Minimax algorithm.
THE ASSIGNMENT:
This assignment consists of one section:
1. Written problems to be turned in.
2. A program to be completed. Click here to return to top of this page.
Written Problems to be turned in:
Algorithm A* (25 points): Problem 3.23 from 3rd Edition of the text. It makes use of Figure 3.2 (p. 68) and Figure 3.22 (p.93).
A.
Algorithm A* (8-Puzzle) (25 points)
Consider the familiar 8-Puzzle problem – a 3×3 sliding block puzzle featuring 8 numbered pieces and a blank cell is to berearranged to place the tiles in a specified order. We have examined two heuristics (referred to below as heuristics h1 andh2). We introduce some other heuristics appropriate for the 8-Puzzle.
h0
(node): 0
h1(node): number of tiles out of place
h2(node): sum of distances out of place
h3(node): 2*DT(node) – defined below
h4(node): h2(node) + 3*S(node) – see below
h5(node): h1(node) + h3(node)
h6(node): h2(node) + h3(node)
h7(node): maximum of all admissible heuristics in {h1(node), h2(node) …
h6(node)}
2 3 48 1 67 5Sample A1 2 38 47 6 5Goal
State2 1 38 47 5 6Sample BDT(node) counts “direct tile reversals” – in which two adjacent tiles must be exchanged to be in their respective properpositions (DT(node)=2 for sample state B, since 1-2 and 5-6 are direct reversals.)
S(node) is a “sequence score” – for every tile around the edge, count 2 for every tile not followed by its proper successorand 0 for every other tile. If there is a piece in the center, add 1.
For each of these heuristics, determine whether it is admissible, and justify your answer.
For the admissible heuristics above, show the precedence from least to most informed¸ e.g., hi(node) ≤ hj(node) ≤ …B.
Minimax, Alpha-Beta (from Tanimoto) (25 points) : The game tree in the figure below illustrates the possible moves, to adepth of 4, that can be made from the current position (at the root) in a hypothetical game between a computer and a human.C.
1.
CS 380 Homework 3 – Informed Search
The evaluation function is such that the computer seeks to maximize the score while the human seeks to minimize it. Thecomputer has five seconds to make its move and four of these have been allocated to evaluating board positions. The orderin which board positions are evaluated is determined as follows: The root is “searched.” A node which is at ply 0, 1, 2, or 3is searched by
generating its children,
statically evaluating the children,
ordering its children by static value, in either ascending or descending order, so as to maximize the probability ofalpha or beta cutoffs during the searches of successive children,
searching the children if they are not in ply four, and
backing up the minimum or maximum value from the children, where the value from each child is the backed-upvalue (if the child is not in ply four) or the static value (if the child is in ply four).
The computer requires 1/7 seconds to statically evaluate a node. Other times are negligible (move generation, backing upvalues, etc.). The computer chooses the move (out of those whose backed-up values are complete) having the highestbacked-up value.
Give the order in which nodes will be statically evaluated. Hint: the first eight nodes have been done for you. Be sureto skip the nodes that alpha-beta pruning would determine as irrelevant. Indicate where cutoffs occur.
a.
b. Determine the backed-up values for the relevant nodes. Node Q has been done for you.
c. Keeping in mind that it takes 1/7 seconds per static evaluation, what will be the computer’s move?d. Now assume that it takes 1/8 seconds per static evaluation. What will be the computer’s move?Click here to return to top of this page.
CS 380 Homework 3 – Informed Search
Programs to be turned in:
Search: Backtracking – Pegboard (25 points): This is a continuation of the programming exercises from the previousassignment: (https://www.cs.drexel.edu/~jpopyack/Courses/AI/Sp19/assignments/HW2/index.html#Prog) :
In the previous assignment, you used the backtracking algorithm to find a solution to the Pegboard problem, howeverno attempt was made to either find an efficient solution or to find a solution efficiently. For this assignment, you areto:
devise a heuristic h(s,r) which estimates the desirability of applying rule r when the system is in state s, andreturns a numerical value, where a low number is considered more desirable than a high number. (Yourheuristic may base its decision entirely on the rule r, or on the new state s’ produced after r is applied to s, oreven something else).
i.
Use this heuristic in applicableRules so that the list of rules returned are arranged in order from mostdesirable to least desirable.
ii.
iii. Solve the problem, using your heuristic.
Output should report on the number of calls to backTrack, both with and without use of your heuristic, andnumber of failures before finding the solution.
iv.
It is likely you will need to experiment with several heuristics before finding one that provides suitably improvedperformance. Describe all of the heuristics you used, and report on the results of using them.
a.
A.
2.
WHAT TO SUBMIT:
All homework for this course must be submitted electronically using Bb Learn. Do not e-mail your assignment to a TA orInstructor! If you are having difficulty with your Bb Learn account, you are responsible for resolving these problems with a TA,an Instructor, or someone from IRT, before the assignment it due. It is suggested you complete your work early so that a TA canhelp you if you have difficulty with this process.
For this assignment, you must submit:
A PDF document with your answers to the “Written problems to be turned in”.
Source code, documentation and results for your program. Click here to return to top of this page.
ACADEMIC HONESTY:
You must compose all program and written material yourself, including answers to book questions. All material taken fromoutside sources must be appropriately cited. If you need assistance with this aspect of the assignment, see a consultant duringconsulting hours. Click here to return to top of this page.
CS 380 Homework 3 – Informed Search
