One of the basic chess endgames is where only three pieces remain on the board: the two kings and one rook. By 1970 it was proved that the player having the rook can win the game in at most 16 moves. Can you write code that plays this endgame that well?

Short Overview

Your code will play as white and the testing code will play as black.

Each test case provides you with an initial game setup, consisting of the positions of three pieces: the white king, the white rook, and the black king. Then you will get a valid move for the black king, to which you must reply with a move with a white piece. You will then get another black move for which you should reply with the next white move, ...etc. The testing code will stop this exchange of moves once the game ends, the rook is lost, or an invalid move is made.

Your code must be able to give a checkmate within 16 moves.

At the end of this description you'll find the relevant rules of chess.

Details of the Task

Write a class WhitePlayer with:

• A constructor taking a string as argument, listing the positions of the three pieces in the format Kxy,Rxy - Kxy where xy are coordinates in algebraic notation and the other characters are literal.

Examples of such strings are Kf8,Rd5 - Ke3 and Kb6,Rc5 - Kb3.

The coordinates will always appear in this order and format, and will always be valid. They define the positions of the white king, the white rook, and the black king in that order.

In all provided positions it is black's turn to play a move.

• A method play, which takes a string as argument and returns a string.

The testing code will call this method to pass as argument a legal black king move. Examples are Kf3, Kb2, ... always starting with K followed by the new position of the black king.

The method should return the move that white will make in response to this black move. It should have the same format. For example: Rd7, or Kb5. The method should update the state of the game, reflecting that both the given black move and the produced white move have been played. The next call of this method will provide a black move applicable to that modified game state.

The testing code will keep calling the method with a next black move until one of the following happens (assuming no exceptions are raised):

• the method returns a value that does not represent a valid move (e.g. wrong data type, wrong format, or violating chess rules): the test fails.
• black can capture the rook: the test fails. The capturing move is mentioned in the failure message with an additional "x", like Kxb4.
• black cannot make a valid move. There are three possibilities:
  • Checkmate after at most 16 white moves: the test succeeds.
  • Checkmate after more than 16 white moves: the test fails. Note that the test is not interrupted after 16 white moves so at least you can see how many moves it took.
  • Stalemate: the test fails.
• The threefold position or 50-move rule applies: the test fails.

Tests

The example test cases can be finished with one move. If somehow your code takes up to 16 moves for a mate, the tests will pass. But it seems reasonable that your code should detect mate-in-one positions.

The full tests include around 40 fixed tests with differing levels of difficulty.

There are 1 000 random tests.

Example

Here is an example position:

8			♚		♚
7								♜
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

This position would be passed to the constructor as Ke8,Rh7 - Kc8.

Black has only one valid move here, Kb8, so that is what the testing code will call your method with. The game could proceed like this:

const whitePlayer = new WhitePlayer("Ke8,Rh7 - Kc8");
const whiteMove = whitePlayer.play("Kb8"); 
// Your code will determine what the return value is, let's assume it's "Kd8";
//   then black has again only one possible move:
whiteMove = whitePlayer.play("Ka8");
// Maybe you decided to return "Kc7"? Good choice!
whiteMove = whitePlayer.play("Ka7");
// Maybe you returned "Rh6" so that black can only return back to square a8
whiteMove = whitePlayer.play("Ka8");
// If your code is good, it will certainly return "Ra6" here, 
//   at which moment you pass the test... it is a checkmate.

whiteplayer = WhitePlayer("Ke8,Rh7 - Kc8")
whitemove = whiteplayer.play("Kb8")
# Your code will determine what the return value is, let's assume it's "Kd8";
#   then black has again only one possible move:
whitemove = whiteplayer.play("Ka8")
# Maybe you decided to return "Kc7"? Good choice!
whitemove = whiteplayer.play("Ka7")
# Maybe you returned "Rh6" so that black can only return back to square a8
whitemove = whiteplayer.play("Ka8")
# If your code is good, it will certainly return "Ra6" here, 
#   at which moment you pass the test... it is a checkmate.

The real challenge: not more than 16 moves

The black king must be checkmated in 16 white moves or less. The black king will use some simple (imperfect) heuristic to delay that fate for as long as possible.

The last bunch of tests generate positions that are known to need 16 white moves with perfect play. Although black does not always play the best move, the random nature of the tests and their number provide a high probability that black will happen to play a perfect defense in a few tests. Consequently your code must aim to play the best moves for white as well. Often there are multiple best moves in one position, so there is a little leeway.

Several possibilities are in front of you: maybe you can think of a smart evaluation function, alpha beta pruning, killer moves, and some other optimisations. Or, maybe you'll go for a purely data driven approach by first building a comprehensive tablebase or a variation on that. Or maybe you'll go for a combination of these approaches. There is probably more than one good way to go about this; just be prepared that there are many random tests and you only have 12 seconds to finish all those games with checkmate, each within 16 moves.

There are also resources online that will provide you the best move in any given position of these three pieces. See for example this Chess Endgame Database.

Good luck!

Appendix

1. Chess Rules

Chess is played on a 8x8 board, with two players: one plays with the white pieces, the other with the black ones. They take turns in playing a move. The pieces we need for this kata are:

• King: a king can move to an adjacent square, either horizontally, vertically or diagonally, in any direction. There are always two kings in a game: a white one and a black one. They may never come within eachother's reach. There must be at least one empty square between them. The king may never move to a square where it could be captured by an opponent piece. Therefore, kings can never be captured.
• Rook: a rook may only move horizontally or vertically, but possibly more than one square at a time, so it can even go from one side of the board to the other end. It may however not jump over another piece, nor occupy a square with a piece of the same color. In this kata there will only be one, white rook. The rook should be placed carefully, as the black king can potentially capture it when it is right next to it. In that case the rook is taken off the board, and the black king takes its position.

If after white's move the rook attacks the black king, the black king is "in check". In that case, the black king must move away. If there is no place for the king to go where it is no longer attacked, then it is a checkmate: white wins.

If the black king is not attacked, but it cannot move anywhere, black is in a so-called "stalemate". In that case the game ends without a winner; it is a draw. In this kata you should avoid bringing black into stalemate; you must win!

A player can claim a draw when:

• both players played 50 moves without capturing a piece or without pawn move (there are no pawns in this kata). This is the 50-move rule.

• a position is arrived at that already occurred twice before. This is the threefold repetition rule.

In this kata the black player (the testing code) will claim a draw when possible.

2. Algabraic Notation

See Wikipedia: The letter part (a-h) determines the column and the number part (1-8) the row as depicted in the image above. "K" refers to the king, and "R" to the rook. "Rh1" means the rook moves to the bottom-right square of the board.

3. Strategy

A common strategy in this particular endgame, is to use the rook to confine the black king to a box as it cannot cross the vertical and horizontal lines of the rook's attack, and to reduce that box as the game progresses. Defend the rook with the king, or when that is not possible, move the rook into safety without giving up (too much of) that space restriction. The king is necessary to assist in forcing the black king backwards and to defend the rook. Eventually the black king is pressed against the edge of the board, and once the white king is moved straight in front of it (with one square in between), the rook can give the checkmate.

For more about strategies for this endgame see for example the articles on WikiBooks, Chess.StackExchange, Chess Corner, or Regency Chess. Be aware though that such strategies may lead to a move sequence that is longer than accepted in this kata.