Problem statement

Isolation

Two pieces stand on a small board. The players take turns, and on your turn you move your piece like a chess queen. The square you leave is burned and can never be used again, so the board shrinks with every move. If it is your turn and you cannot move, you lose.

Your task is to write a bot that plays one piece. Your bot plays many games against the judge bots on the server, and it is scored on how often it wins.

Rules

• The board is W × H squares, with W and H each from 7 to 9. x is the column (0 at the left) and y is the row (0 at the top).
• Some squares are walls (#). Walls are symmetric under a 180° rotation about the centre of the board, and the two start squares are mirror images of each other.
• The players take turns. Player 0 moves first (turns 1, 3, 5, …) and player 1 moves second (turns 2, 4, 6, …). Every game is played from both sides when you are scored, so moving first or second evens out.
• On your turn you move your piece like a chess queen: any number of squares in a straight line in one of the 8 directions (up, down, left, right or diagonal). You may not pass through or land on a wall, a burned square or the other piece, and you may not stay where you are.
• The square your piece leaves is burned: it becomes a wall for the rest of the game.
• If it is your turn and your piece has no legal move, you lose.
• A bot that times out, crashes, prints an invalid line or names a square it cannot legally reach loses at once.
• There are no draws: the board fills up long before the 100-turn limit.

Input and output

Your bot talks to the referee through standard input and standard output, one line at a time.

Once, at the start, you receive one line:

W H my_id

my_id is your player number, 0 or 1. The opponent is 1 - my_id.

On each of your turns you receive H + 3 lines (nothing is sent on the opponent's turns):

turn T
x0 y0
x1 y1
<H lines of W characters each>

• T is the turn number, counting both players' moves, starting at 1. Player 0 always gets odd turn numbers and player 1 even ones.
• x0 y0 is the square of player 0's piece and x1 y1 is player 1's.
• Each board character is . for a free square, # for a wall or burned square, and 0 or 1 for the square of that player's piece.

You reply with exactly one line: the square to move to, as x y (two integers separated by a space). Then flush standard output. If you do not flush, the referee never sees your move and you time out.

• Blank lines are ignored, and trailing spaces and \r are removed.
• Anything else, such as 3,4, UP or a square your piece cannot reach, is an invalid move and makes you lose.
• Print debug text to standard error only. The server's replay viewer shows your stderr turn by turn (up to 2,000 characters per turn). Standard output is read as moves only.
• After the game ends, your standard input is closed. Your bot may simply exit when reading fails.

Example turn

Turn 1 of the game below, as seen by player 0:

turn 1
2 2
4 4
...#...
.......
.#0.#..
.......
..#.1#.
.......
...#...

From (2, 2) player 0 can reach 11 squares: (2, 1) and (2, 0) going up; (3, 1) and (4, 0) going up-right; (3, 2) going right (then (4, 2) is a wall); (3, 3) going down-right (then (4, 4) is the other piece); (2, 3) going down (then (2, 4) is a wall); (1, 3) and (0, 4) going down-left; and (1, 1) and (0, 0) going up-left. Going left is blocked by the wall at (1, 2).

A complete short game

Lines starting with < are what player 0's bot receives; lines starting with > are what it prints. Player 0 moves to (2, 1), (5, 1) and then (6, 0); player 1 answers with (4, 3), (6, 1) and (5, 0). Player 1 receives only the even turns, and its first line is 7 7 1.

< 7 7 0
< turn 1
< 2 2
< 4 4
< ...#...
< .......
< .#0.#..
< .......
< ..#.1#.
< .......
< ...#...
> 2 1
< turn 3
< 2 1
< 4 3
< ...#...
< ..0....
< .##.#..
< ....1..
< ..#.##.
< .......
< ...#...
> 5 1
< turn 5
< 5 1
< 6 1
< ...#...
< ..#..01
< .##.#..
< ....#..
< ..#.##.
< .......
< ...#...
> 6 0

On turn 6 player 1 moves from (6, 1) to (5, 0). Player 0's piece at (6, 0) is now boxed in: (5, 0) is the other piece, and (6, 1) and (5, 1) are burned. Player 0 cannot move on turn 7, so player 1 wins. The result reads: player 0 has no legal move at (6,0) after turn 6.

Limits

The server compiles your bot with:

C and C++ bots get a 256 MB stack, so deep recursion is fine. Your bot has no network access and cannot write files outside /tmp.

Scoring

Each submission plays every judge bot on the same 6 evaluation maps, once from each side, which is 60 games. For each judge bot j:

rate_j = (wins + 0.5 × draws) / games

Your score is the weighted sum of these rates, from 0 to 100:

score = Σ weight_j × rate_j

random_safe and mobility are in your starter kit as source code, so you can practise against them. The other three are stronger and stay on the server, but you can play single games against any of them with the Run button.

The live leaderboard uses the best score among your submissions. At the end of the contest your final bot (the one you mark as final, otherwise your latest successful submission) is re-scored on 20 hidden maps, once from each side against every judge bot, and that score decides the final ranking. Ties are broken by the live score of that bot, then by the earlier submission time.