1) Search and the 15-puzzle (paper and pencil --- 6 points)
Assume you apply depth first search to the 15-puzzle
problem and answer the following 2 question. Give reasons
for each of your answers.
a) Is it worthwhile to check for repeated states in the
currently explored search path?
b) Assume that you check for repeated states, and your
version of depth-first search does not use a depth
bound. Will this version of the algorithm always find
a solution if a solutions exists?(assuming that you
have unlimited runtime)? Will this version always
terminate, if no solution exists?
2) Heuristic Search for the 16-Queen Problem (paper and pencil
--- 14 points)
Assume we are applying various search teachniques to
the 16-queen problem.
a) Give a description of the initial state, goal test,
and operators you would use when solving the problem
b) Assume you apply depth-first search to the 16-queen
problem within the framework you introduced in a).
Is it worthwhile to check for repeated states in the
currently explored search path? Give reasons for your answer!
c) Now assume you intend to use bestfirst-search for the
16-queen problem. What state evaluation function
would you use? Explain why you selected the
presented function. Submit the search tree for the first 6
state expansions that your bestfirst-search algorithm would make for a run
of your hypothetical system. Are there any additional
heuristics you would employ when solving the the 16-queen
problem?
3) Heuristic Search for a White King and Rook versus the Black
King Chess Endgame (Programming Problem --- 80 points)
Select a search strategy, implement it, and make your algorithm
"more intelligent"
by using domain knowledge and "experience of past runs"
for the above mentioned endgame playing the white pieces.
It is assumed that white has to move first.
Your objective is to capture the
black king (stale mate has to be avoided). It is assumed
that the fields on the chess board are represented as
pairs of integers, where the first coordinate is assumed to be
the x-coordinate, and the second coordinate
is the y-coordinate: (1,1),(1,2),...,(8,8).
Our version
of the game is deterministic in the sence that black's move
is completely determined for a given position. The black king's first
priority is to capture an unprotected rook. If this is not possible,
it is assumed that the black king moves to a safe field (a field
is safe, if it is neither in the reach of the
white rook nor in the reach of the white king) for which
the following value is minimal
Test your system for a tranining benchmark that consists of 12 example problems; the training testcases are ordered by degree of difficulty --- do not get too disappointed, if your program does not too well for some test cases with high numbers.
Provide an interface to your program that it can read a set of example problems from a file, and then tries to solve all problems of the set in a file. In general, your program should be able to read input-files of the following format (example: file for tranining benchmark):
number of games to play(integer) newline name of starting position(4 asci character) newline starting position (8 lines --- see example) empty_line newline name of starting position(4 asci character) newline starting position (8 lines --- see example) empty_line ...
Be prepared to demo and run your
for a test-benchmark after the due-date. These are
the precise deadlines:
electronic submission of program code: Tu., Sept. 28, 11:59p to
ceick@aol.com
program report + listings: We., Sept. 29, 2:30p in class
solutions to other homework problems: We., Sept. 29, 2:30 in class
demo program for test-cases: after October 6
4) Hill Climbing and Simulated Annealing
(Paper & Pencil -- 8 Points)
Compare Simulated Annealing with Hill Climbing discussing
the similarities and differences of the two search strategies,
and discussing the advantages and disadvantages of each
approach.
5) A* (Paper & Pencil -- 13 points)
Solve Problem 4.6 of the textbook
6) Search for 2-Player Games (Paper & Pencil -- 9 points)
Solve Problem 5.1 of the textbook