Problem statement

Snake Duel

Two snakes share a grid full of apples. Every apple a snake eats makes it one cell longer. Crash into a wall, the edge or a snake body and you are out. The last snake still moving wins, and if both survive 300 turns, the longer snake wins.

Your task is to write a bot that steers one snake. 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 cells, with W from 12 to 20 and H from 10 to 16. x is the column (0 at the left) and y is the row (0 at the top).
• Some cells are walls (#). Some maps have a wall all around the edge and some do not, so moving off the board is possible and is fatal.
• Walls, the starting apples and the two snakes are symmetric under a 180° rotation about the centre of the board. Neither side has an advantage at the start.
• Each snake starts 3 cells long in a straight line. Snake 0 starts facing right and snake 1 faces left.
• Every turn both players move at the same time. Each picks UP, DOWN, LEFT or RIGHT. A turn is resolved in three steps:
  1. Move. Each head moves one cell. If the new head cell holds an apple, the snake eats it and grows: its tail stays where it is. Otherwise the tail moves forward one cell, so the snake keeps its length.
  2. Collisions, judged on the new positions. A snake is eliminated if its head is:
     • off the board, or on a wall,
     • on a cell of its own body (so turning back into your own neck is always fatal), or
     • on any cell of the other snake's body. If both heads land on the same cell, the shorter snake is eliminated; if they are the same length, both are.
  3. Apples. Eaten apples disappear, and the same number of new apples appear on random empty cells that are not next to either head. The board always holds the same number of apples as at the start (4 or 6).
• Because tails move before collisions are judged, moving onto the cell where a tail was at the start of the turn is safe, unless that snake has just eaten (its tail then stays put).
• A bot that times out, crashes or prints an invalid line is eliminated before the snakes move that turn. The other snake still moves.
• The game ends as soon as at least one snake is eliminated. If one snake survives, it wins. If both are eliminated on the same turn, the game is a draw.
• If 300 turns are played, the longer snake wins. Equal lengths are a draw.

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.

Every turn you receive H + 3 lines:

turn T
L0 x y x y ... (L0 pairs)
L1 x y x y ... (L1 pairs)
<H lines of W characters each>

• T is the turn number, starting at 1.
• The second line describes snake 0: its length L0, then the x y of each of its cells from the head to the tail. The third line describes snake 1 the same way.
• Each board character is . for an empty cell, # for a wall, * for an apple, 0 for a cell of snake 0 and 1 for a cell of snake 1.

You reply with exactly one line: UP, DOWN, LEFT or RIGHT (upper case). Then flush standard output. If you do not flush, the referee never sees your move and you time out.

• UP is y − 1, DOWN is y + 1, LEFT is x − 1, RIGHT is x + 1.
• Blank lines are ignored, and trailing spaces and \r are removed.
• Anything else, such as up, NORTH or 1, is an invalid move and eliminates you.
• 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 2 of the game below, as seen by player 0. Snake 0 moved up from (4, 3) to (4, 2): its head is now at (4, 2) and its tail moved from (2, 3) to (3, 3). Snake 1 moved left from (8, 6) to (7, 6).

turn 2
3 4 2 4 3 3 3
3 7 6 8 6 9 6
#############
#........#.*#
#...0.......#
#..00...#####
##.....*..*##
##*..*.....##
#####..111..#
#...........#
#*.#........#
#############

From (4, 2), UP to (4, 1), LEFT to (3, 2) and RIGHT to (5, 2) are safe. DOWN to (4, 3) is snake 0's own neck, so it is fatal.

A complete short game

Player 0 keeps moving UP and drives into the top wall on turn 3, while player 1 moves LEFT every turn. Lines starting with < are what player 0's bot receives; lines starting with > are what it prints. Player 1 receives the same lines, except that its first line is 13 10 1.

< 13 10 0
< turn 1
< 3 4 3 3 3 2 3
< 3 8 6 9 6 10 6
< #############
< #........#.*#
< #...........#
< #.000...#####
< ##.....*..*##
< ##*..*.....##
< #####...111.#
< #...........#
< #*.#........#
< #############
> UP
< turn 2
< 3 4 2 4 3 3 3
< 3 7 6 8 6 9 6
< #############
< #........#.*#
< #...0.......#
< #..00...#####
< ##.....*..*##
< ##*..*.....##
< #####..111..#
< #...........#
< #*.#........#
< #############
> UP
< turn 3
< 3 4 1 4 2 4 3
< 3 6 6 7 6 8 6
< #############
< #...0....#.*#
< #...0.......#
< #...0...#####
< ##.....*..*##
< ##*..*.....##
< #####.111...#
< #...........#
< #*.#........#
< #############
> UP

On turn 3 player 0 moves from (4, 1) to (4, 0), which is a wall, so player 0 is eliminated and player 1 wins. The result reads: player 0 hit a wall at (4,0) on turn 3.

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 greedy 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.