King and Rook Checkmate

One of the positions of a checkmate with rook

History of chess-playing computer programs was preceded by interesting electro-mechanical computer El Ajedrecista - it was not capable of playing full game - rather was able to win against human in a specific simple endgame - it played King and Rook against bare King - and always delivered checkmate. It may sound laughable nowadays but back in 1912 it was great achievement.

You'll be able to judge yourself. Your goal is to write the program doing exactly this - play King and Rook to deliver checkmate to bare opponent's King. Below follow quick recap of corresponding chess rules, but feel free to refer to some more substantial source if necessary.

1. Game is played on rectangular board consisting of square cells. Our chessboard is 10 cells wide and 9 cells high (instead of usual 8x8).
2. King moves by 1 cell horizontally, vertically or diagonally (8 cells to choose when not near the edge).
3. Rook moves by changing its horisontal or vertical coordinate to any other value (but not both coordinates simultaneously - on the board of size W x H it gives W + H - 2 options always, unless path is blocked by other piece - rooks can't jump).
4. Kings are not allowed on their move to go into the cell where opponent can capture them the very next move - particularly this means king can't go on the same vertical or horizontal with enemy's rook, unless it's "line of sight" is blocked by enemy's king for example - and also king can't go on to the cell adjacent to enemy's king (facing other king).
5. None of the sides is allowed to pass (skip) the move. If there are no valid moves, the game ends - however there could be two situations: if the king (of the player who have no valid move) is attacked (under "check") - it is checkmate (i.e. whatever the player would try, the king is lost the next move) - and win. If the king is not attacked, it is "stalemate" - draw in western chess.

Your program, Input and Output

This is interactive problem in which you need to submit your code in any language supported by our "sandbox" server (one of those for which the "run" buttons work below, except for in-browser execution). Your program and the script playing for the other side are executed simultaneously, and they have stdins and stdouts connected between them - so whatever one program prints, another will read - and vice versa.

The input will be using slightly modified chess notation. Horizontal coordinates (columns or "files") of the chess board are encoded with letters a to j, while vertical coordinates (rows or "ranks") are encoded with digits from 1 to 9. Every piece position or move is described with thre symbols - two last are file and rank respectively, while the first is the piece name K for white king, R for white rook and G for black king (from "General" as it is called in eastern chess traditions).

So the first line of the input your program receives is in form:

Ge4 Ka5 Ri8

Which means that black king is at 5-th column and 4-th row, white king at 1-st column and 5-th row and the rook at the 9-th "file" and 8-th "rank".

You at your move decide whether to move your King or Rook and print the new position, e.g.

Ri4

Then you read opponent's move (e.g. Gf5) and so continue until instead of the opponent's move you'll find exclamation mark (!) which means the game is ended and you need to quit immediately. Full "exchange" may look like this (i.e. if you run your code to play against it manually, typing in moves for black king yourself):

Gb1 Kb3 Rc2         # initial position proposed by "opponent" program or entered by you manually
Rc4                 # move made by your program (any cell between b3 and b9 is fine)
Ga1                 # move by "opponent" or yourself (there is only one place to go)
Rc1                 # your program delivers checkmate
!                   # signal to your program to exit (again you type it manually or "opponent" script prints it)

The game is run several times and your program should win all of them. If some of the games fail with some errors, the first of them is reported to you, with the full log of moves (and initial setup) for analysis.

This task is a new experimental kind of interactive problems and there may be issues not only in the logic of the "opponent" script and "driving" program, but also in the technical setup, so feel free to report if you find anything suspicious. Particularly it is important to print every move on a separate line and flush output (if it is not flushed on line end in your preferred language) - otherwise opponent program won't receive your move. Don't forget to read input, even if you try some test program - without it "opponent" script may wait for you to start reading (i.e. there is a mutual block).

Sample program

This program just reads a line of input (to prevent blocking the opponent, as said above) and attempts to make a move with a king, most probably resulting in rules violation (which is reported to you):

input()
print('Ka1')

If you would like to slightly improve it, start with parsing initial king position and trying to make several random moves (until king falls off the board or collides with rook or enemy king).