2) Heuristic Search for the 16-Queen Problem (paper and pencil --- 13 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 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 the White King and Rook versus the Black King Chess
Endgame (Programming Problem --- 90 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:
(x=1,y=8),(x=2,y=8),...,(x=8,y=8)
(x=1,y=7),...,(x=8,y=7)
...
(x=1,y=1),...,(x=8,y=1).
Our version of the game is deterministic in the sense 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:
number of games to play(integer) name of starting position(4 asci character) starting position (8 lines --- see example) name of starting position(4 asci character) starting position (8 lines --- see example) ... Example: 2 FR01 -- -- -- -- -- BK -- -- -- -- -- -- WR -- -- -- -- WK -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- FR02 -- -- -- -- -- -- -- -- -- BK -- -- -- -- -- -- -- -- -- WR -- -- -- -- -- -- -- -- WK -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --Add a counter to your program that counts the number of chessboard position that are generated by your program during the search process; moreover, terminate the search after more than 10000 board positions have been generated for a single example problem. If your program succeeded in capturing the king print the sucessful state sequence (only displaying the positions with white on move) and report the number of white moves it took to capture the king, and how many board positions had to be generated in order to find the solution. Design your program so that the play of the game can be visualized on the screen and a hard-copy of the game played can be captured in a file for documentation purposes. Write a 5-6 (single-spaced) page report that describes your approach, and explains how your search strategy works for a few examples, and gives a brief history of the project. Limit your writeup to 6 single-spaced pages (you will not get a better grade by writing more pages). Submit the program listing with the report together with a printout of the run that shows your program's behavior for cases TR02, TR04, and TR08, and TR10; also report for how your program performed for the other 6 cases of the training benchmark. More specifically, add a table to your report as an appendix that reports for each test-case the following: test-case number, states generated, wall clock execution time, result of run (e.g. found a solution that mates the king in x moves, stopped after generating 10000 states, was stopped after running one hour, ran out of storage, terminated with runtime-error,...). Also describe the hardware/software platform that was used for executing your program.
last updated: September 5, 2001, 5:50p.