First Draft Project1 COSC 6368 Fall 2016 (Dr. Eick)
Heuristic Search for the White Rook and King versus the Black King Chess Endgame
Final Draft
Individual Project

Deadlines: (electronic submission): Thursday, October 6, 11p (5% bonus for early submission), Satuday, October 8, 11p (hard deadline; no submissions after this due date will be accepted)

The goal of the project to develop a software system that solves White Rook and King versus Black King Chess Endgame Problems (WRKBK for short). The steps of the project include:
0. Familiarize yourself with the WRKBK-problem and how to solve it "as a human".
1. Implement the state space of the WRKBK-problem.
2. Select a search strategy and implement it!
3. Augment the search strategy with problem-specific knowledge!
4. Run the implemented system for the training benchmark.
5. Remove bugs from your implementation and enhance your search strategy and the problem specific knowledge it uses based on the experience of Step 4.
6. Repeat steps 4 and 5 until a satisfactory software system has been obtained.
7. Write a short report that summarizes your employed search strategy, the design of your program, the results from running of your program for the training benchmark, and gives a brief history of the project. Also include a brief description of special/tricky parts in your implementation (if any).
8. Be prepared to demo the software system you developed.

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 but cannot move to a safe field this is called a stalemate (which is a draw and has to be avoided, when playing the white pieces).

Test your system for the following WRKBK Training Benchmark, consisting of 13 test cases; the training testcases are ordered by degree of difficulty: do not get too disappointed, if your software system has some problems with some test cases with high numbers.

Develop an interface to your program so that it can read a set of example problems from a file, and then solves all problems in the file, and generates an output file containing solutions (and background info about the obtained solutions) for the problem set of the input file. In general, Project1 input-files of the following format:

number of games to play(integer)
name of the test case(4 asci character)
starting position (8 lines --- see example)
name of starting position(4 asci character)
starting position (8 lines --- see example)
Moreover, add a counter, SEXP, to your program that counts the number of chessboard positions 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, output 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; output NA if your program could not find a solution for the particular testcase. Design your program that your program has an option that your program output can be visualized on the screen, in addition to write the output to an output file. Moreover, WRKBK software system will be additionally tested using a testing benchmark of 7 testcases that will not be published before the Project1 deadline.

More problem-specific knowledge about the WRKBK-problem as well as stategies on how to approach the problem will be discussed in the lectures of COSC 6368 on September 13 and 15. Moreover, check-out the following links:
WRKBK Video (good source to get started!)
WRKBK Article

Project1 Submission Instructions: will also be posted on Sept 25 at Nguyen Pham's COSC 6368 webpage the latest!

The deliverable includes:

All items should be packed as one single zip folder, named as:
Finally, if you are going to submit via email (in case of problems with Black Board), please use this keyword for the beginning of the subject: [Cosc6368-Fall2016]

Last Updated: September 26, 11a.