Heuristic Search for a White King and Rook versus the Black
King Chess
Endgame
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
|x-5|*5 + |y-5|*3 + (x+y)*0.1
If there is no such safe field the game ends. If the black king
is attacked by the rook this is called a mate (which is a winning
position for white); if the black king is not attacked attacked and cannot move
this is called a stalemate (which is a draw and has to be avoided, when
playing the white pieces).
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
...
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.