Chess Endgame
The aim of this project is to develop software to play some chess endgames with few pieces remaining on the board. In the view of the 50-move rule (according to which, if fifty moves have passed without a capture or a pawn move, either player may claim a draw), it is crucial to play such endgames optimally to avoid being caught by this rule while having material advantage. 

As an example, consider the King + Bishop + Knight vs. King (KBNvsK) endgame. It is a theoretical win from any starting position (where the defender cannot quickly win one of the pieces and the position is not a so called “stalemate trap”), but it requires up to 33 moves under the perfect play assumption, and the technique is rather difficult. Hence, in practice it is often a draw due to the 50-move rule, and, as Jesús de la Villa remarked in his book “100 Endgames You Must Know”, “Some masters have already gone back home red with embarrassment after failing or showing poor technique in the execution of this checkmate”. Hopefully, the software you develop during this project will help to avoid similar embarrassments.

To analyse the endgames, your software should use a technique called retrograde analysis, to build the endgame table from which it is easy to work out the optimal move for each possible position. The game itself is then reduced to looking up the move for a concrete position. This technique is briefly explained at the end of this document.

The project is available at several levels of difficulty. The exact level will be chosen depending on your course and program of study.
Level 1: basic checkmates 

White has a King plus one or two pieces (no pawns) and Black has just a King. 

1.	Your program should be able to play perfectly at least the following games for White:
•	KQvsK
•	KRvsK (assume that castling is not possible)
•	KBBvsK (the two Bishops are on opposite colours)
•	KBBvsK (the two Bishops are on the same colour)
•	KBNvsK
•	KNNvsK
2.	Your program should be able to make some general conclusions concerning each game type, e.g. whether a win is possible for every valid initial position (except when it is a stalemate or a quick capture of a piece by the defender is possible), or give the percentage of winning initial positions.
3.	The program should analyse the initial position, i.e. whether it is invalid (e.g. two pieces are at the same position, or a King can be immediately captured), a checkmate, a stalemate, or White cannot prevent an immediate capture (which would render the endgame uninteresting), and print an appropriate message concerning the expected outcome of the game. In the case of an expected win, the number of moves under the perfect play assumption should be printed. Examples of possible messages:
•	“The initial position is invalid”
•	“The initial position is a checkmate”
•	“The initial position is a stalemate” (not possible for Level-1 if White moves first; however, the KBNvsK endgame has a possible position where whatever move White makes, it either loses a piece or stalemates)
•	“White cannot prevent a quick capture at the initial position”
•	“The initial position is a draw under the perfect play assumption”
•	“White wins in at most 23 moves”
•	etc.
4.	The following minimalistic user interface should be implemented:
•	The initial position should be read from console.
•	The initial position and the position after each ply (i.e. half-move) should be printed to the console.
•	The moves for Black should be read from the console (in the form e6-d7 or e6d7 or just d7 for basic checkmates, as Black has just one piece whose position is known). 
•	The correctness of the input should be checked, and the user should be able to re-enter the move in case of a mistake.
You have an option of developing a better interface, however it is advised that you do not waste your time developing an elaborated GUI – this is not the point of the project!

Level 2: pawnless endgames

At this level, at least the following requirements should be taken into account (in addition to the ones described above):
5.	Your program should be able to play perfectly the following endgames:
•	KQvsKR (assume that castling is not possible)
•	KQvsKB
•	KQvsKN
•	KRvsKB (assume that castling is not possible)
•	KRvsKN (assume that castling is not possible)
6.	The program should warn whether it is not clear from the initial position that castling is impossible.
7.	The program should allow the user a choice between playing for White and playing for Black; in either case, the program should play perfectly (i.e. if it plays for Black and White can ensure a forced win, it should try to delay it for as long as possible, and if White makes a mistake, the program should print a message and ensure a draw). 

Compared to the previous level of difficulty, White can capture a piece, reducing thus the number of pieces on the board. Hence, such sub-endings should be analysed first. Furthermore, the attacker can now lose from some initial positions (e.g. when the defender can quickly capture a piece). Furthermore, the definition of the optimal move now needs re-visiting, as there are at least two possibilities: one can minimise the number of moves either to the capture of Black’s piece (after which the checkmate usually quickly follows), or to a checkmate. Both metrics have advantages and disadvantages, and you can choose the one you like more.
Level 3: pawnless endgames: up to 5 pieces
At this level, at least the following requirements should be taken into account (in addition to the ones described above):
8.	Your program should be able to play perfectly any endgame with up to 5 pieces (no pawns).
9.	Your program can no longer regard castling impossible; in case when it is not clear from the initial position that castling is impossible, it should make an additional query, and proceed accordingly. (Though in practice it is very unlikely that castling is possible at such a late stage of the game, in many chess miniatures castling is the crux of the solution, and so it is useful to have it.)

Compared to the previous level of difficulty, the game types are not fixed, and the number of possible positions is much larger, which might cause problems with memory allocation. Furthermore, castling has to be handled somehow (note that two positions which look the same may still be different due to castling being possible at one of them, but not at the other).
Level 4: endgames with pawns: up to 5 pieces
At this level, at least the following requirements should be taken into account (in addition to the ones described above):
10.	Your program should be able to play perfectly any endgame with up to 5 pieces (including pawns).
Compared to the previous level of difficulty, there are the following changes:
•	the positions with pawns on 1st or 8th ranks are invalid;
•	a pawn can capture another pawn “en passant”; such a capture may be possible at the initial position, in which case the program should make an additional query, and proceed accordingly; 
•	a pawn can be promoted to another piece, which changes the game type; fortunately, each promotion reduces the number of pawns, and so the relevant game types can be analysed prior analysing the original game type.
Retrograde analysis
The motivation for using retrograde analysis is that the more natural forward analysis starting from the initial position is computationally infeasible. For example, for the KBNvsK endgame one has to analyse the game 33 moves ahead for some initial positions. At each position, for White the Bishop can make up to 13 moves, the Knight up to 8 moves, and the King up to 8 moves (up to 29 moves in total). Then Black King can respond with up to 8 moves, and so on. For simplicity, let’s assume that White can make 20 moves in average and Black can make 6 moves in average. Then to look one move ahead one has to consider 20*6=120 positions, for two moves this number grows to (20*6)2=14,400, for three moves it is (20*6)3=1,728,000, and so on. Hence, to look 33 moves ahead one has to consider (20*6)33=4.1*1068 positions. To put it in perspective, suppose the computer can analyse a million positions per second (which is rather optimistic). Then it would need about
13,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
years to finish the computation. Hence, a different technique is needed.

The key observation is that the total number of possible positions in the endgame with few pieces left on the board is not that big. For example, for the KBNvsK endgame each of the four pieces can stand on one of the 64 squares, and so the total number of positions is bounded by 2*644= 33,554,432 (the multiplication by 2 is needed because one has to specify for each position whose turn it is; note also that some of the counted positions are invalid, e.g. two pieces might stand on the same square), which is easily within the reach of modern computers.

The retrograde analysis, as its name suggests, analyses the endgame not from its initial position forward, but from the final positions (usually checkmates) backwards. The result is the table which tells for each possible position the number of moves (or plys, i.e. half-moves) from it to checkmate, under the perfect play assumption. For the KBNvsK game this table can be declared as follows:
	byte endgameTable[64][64][64][64][2];
The first four indices correspond to the positions of the four pieces on the board, and the last index specifies whose turn it is to make a move (0=White, 1=Black). Hence, a position is specified by a tuple of numbers (p1,p2,p3,p4,t), where 0  p1, p2, p3, p4  63 specify the positions of the four pieces, and 0  t  1 specifies whose turn it is to make a move. Given such numbers, endgameTable[p1][p2][p3][p4][t] contains the number of moves (or plys) to reach a checkmate from this position under the perfect play assumption. The retrograde analysis proceeds in two stages.
Stage 1: building the endgame table
The algorithm for building the endgame table is as follows:
1.	Fill in the table with some fixed value, e.g. -1, signifying that the position has not been evaluated yet; the positions for which the endgame table contains -1 are called unmarked.
2.	Mark all the invalid positions with some other fixed value, e.g. -2.
3.	Mark all the checkmates with value 0 (as 0 moves are needed to reach a checkmate from a checkmate); note that all the checkmates are the positions where it is Black’s turn to move (if it were White’s turn to move, Black King could be captured, and so this would be an invalid position).
4.	Assign distanceToCheckmate=0 (the number of plys to reach a checkmate)
5.	Main loop
o	distanceToCheckmate++

o	[White’s turn to move] Mark the unmarked positions (p1,p2,p3,p4,0) with distanceToCheckmate, provided that White can make a move reaching the position (q1,q2,q3,q4,1) (note that after White makes a move, it is Black’s turn to make a move) that is marked with distanceToCheckmate-1.

o	distanceToCheckmate++

o	 [Black’s turn to move] Mark the unmarked positions (p1,p2,p3,p4,1) with distanceToCheckmate, provided that all the possible Black’s moves reach either an invalid position or a position  (q1,q2,q3,q4,0) (note that after Black makes a move, it is White’s turn to make a move) marked with a number smaller than distanceToCheckmate.

o	If no changes to endgameTable have been made on the current iteration then break out of the loop.
6.	Mark the remaining unmarked positions as draws, by assigning them some fixed value, e.g. -3.

Intuitively, before the main loop starts, all the checkmates are marked. 
On the first iteration of the loop, the positions in which White can checkmate in one move are marked, and then the positions in which whatever move Black makes, White will be able to checkmate in one move. 
On the second iteration, the positions in which White can checkmate in two moves are marked (these are the positions in which White can make a move such that in the resulting position Black cannot stop a checkmate in one move), and then the positions in which whatever move Black make, White will be able to checkmate in two moves. 
Etc.
At the end, all the positions leading to a checkmate are marked, and so the remaining unmarked positions are marked as draws.
Note that the initial position is not used for building the endgame table.
Stage 2: playing the game
Once this table has been built, it is very easy to find the best move for White at any valid position (p1,p2,p3,p4,0) that is not a checkmate: if the position is such that a forced checkmate is possible, i.e. endgameTable[p1][p2][p3][p4][0]>0, then a move leading to the position (q1,q2,q3,q4,1) such that endgameTable[p1][p2][p3][p4][0]>endgameTable[q1][q2][q3][q4][1]≥0 is optimal.

Important: the project involves creating huge arrays; Java Virtual Machine might fail to do that, so you might need to use another programming language, like C++, or do some hacking. In any case, it is advised to check whether an array of given size can be allocated before starting to code.