Invisible target

king-of-the-hillgamegrid probability-theory ?

In short

Walls are gradually added and the player nearest to the stationary invisible target at the end of the game wins.

Detail

Players are all present on a 64 by 64 grid of square cells, which wraps toroidally. One randomly chosen cell is the target, which is not indicated to any of the players (regardless of whether they are on that cell or not). The target does not move.

Players take turns in order. After each turn there is a small chance of a wall being added.

Wall rules

• The wall will never be placed in a cell that would leave any player with no route to the target (this includes never placing a wall on the target).
• The wall will never be placed in a cell that does not have a route to the target.
• The wall will never be placed on a player.
• No further walls will be added until every player has taken a turn, so between two consecutive turns a player will only ever see either zero or one wall added.

Note that a player having a route to the target means that there exists a path that does not include a wall. If another player blocks the path it still counts as a path, so the wall can still be placed.

Movement rules

• A player can move to any orthogonally adjacent cell (including staying still).
• A player cannot move onto another player.
• A player cannot move onto a wall.
• A player can move onto the target, but will have no way of knowing that this has happened.

Starting position

At the start of the game the arena will have no walls and the players will be randomly positioned with the guarantee that there are no other players within each player's 5 by 5 neighbourhood.

• Each player will be represented at least once.
• Each player will be represented the same number of times.
• Each player will be represented enough times to bring the number of players up to at least 16.

Winning

Play will continue until no player can move or all players choose not to move. The player closest to the target (by Manhattan distance) is the winner. Although this makes it possible to have an arbitrary number of joint winners, the density of walls by this point makes it unlikely there will be many.

Each of the (one or several) joint winners scores one point. Games will be played until one player is the clear winner, or until it is clear there should be joint winners overall.

Input and output

If your language will have difficulty in running more than one copy of the same program in competition with itself, or require a special course of action, please let me know. This will only be a problem until there are 16 or more players (after which each player will only be present once).

Input

The program will receive the following on STDIN:

• The number of remaining inputs.
• The player's position.
• The position of any wall added since the player's last turn.
• The position of every enemy player (duplicated players count as enemies of each other).

Positions will be single integers from 0 to 4095, representing the distance in English reading order from the top left cell.

For a 4 by 4 arena this would give a numbering like this:

 0  1  2  3
 4  5  6  7
 8  9 10 11
12 13 14 15

The number of remaining inputs will always be N+1 during an N player game: player location + wall location + N-1 enemy player locations. If no wall was added the wall location will be 4096.

The input will be a space separated string of N+2 integers.

The order of enemy players will be consistent - the nth location will always refer to the same enemy player.

Output

The player must send an integer from 0 to 4 to STDOUT representing a move in English reading order:

  0
1 2 3
  4

(2 being no move).

A player taking longer than 50 milliseconds to respond will not move.

Sandbox questions

• If someone can demonstrate that there can exist no better strategy than moving uniformly randomly, then I will not post this challenge. I'm hoping that the knowledge of the rules behind wall placement and the ability to block the movement of other players will make probability estimating competitive strategies non-trivial.

• I'd like to hear views on the approach of duplicating players to make up to at least 16. Would it be preferable to simply start off with fewer players? Or to pad the numbers out with copies of a basic example answer rather than duplicating the real players?