Invisible target - probability KotH

king-of-the-hill game grid 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 32 by 32 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 all take their turn simultaneously. After each turn there is a small chance of a wall being added.

Wall rules

• The wall will never be placed on a player.
• The wall will never be placed in a cell that does not have a route to the target.
• Of the possible positions for the wall to be placed, one will be chosen uniformly pseudorandomly.
• The probability of a wall being placed each turn is 1/7.
• The wall will be placed such that every player still has a route to the target (this includes never placing a wall on the target).

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.

Movement rules

• A player can move to any orthogonally adjacent cell (including staying still).
• A player cannot share a cell with 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.

Winning

Play will continue until no wall can be placed for 10 consecutive turns. 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, and in most cases there will be a player on the target cell, meaning only a single winner.

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

Input

During an N player game the input will be a space separated string of N+1 integers received on STDIN:

• The player's position (an integer).
• The position of any wall added since the player's last turn (an integer).
• The position of every enemy player (N-1 integers).

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

For a 4 by 4 arena this would give the following numbering:

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

If no wall was added the wall location will be 1024.

During a particular game 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 move to an unoccupied cell will not necessarily succeed - it will fail if another player is also trying to move to the same cell.

A move to an occupied cell will not necessarily fail - it will succeed if that player is also moving away from that cell (provided that player succeeds in moving away from that cell, and no other player is also trying to move to that cell).

This means two players can swap cells if they both decide to on the same turn.

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. This is answered - Nathan Merrill's strategy of moving to the reachable cell whose maximum distance to any other reachable cell is the shortest will beat the strategy of moving uniformly randomly (although in a crowded arena I don't believe this will be the best strategy so I still consider the question worth posting).

• Should this be tagged probability-theory? I am expecting answers to make use of probability theory, but I can't know in advance what all the strategies will be. Is this close enough to use the tag?

• I'm aiming for this to be a language agnostic challenge communicating with STDIN/STDOUT. Is there a language that is overdue to have its own language specific KotH contest, but that would still allow most users to participate? If not, I'll stick with language agnostic and include at least one example answer so that the processing of STDIN and STDOUT is provided in at least one language.

• Method for deciding which attempted moves succeed. Is there any problem with this: Make a list of every intended destination (including own cell for non-movers). For any destination that appears more than once, make all players aiming for that destination aim for their own cell. Repeat (as this may have created more clashes) until no change is made. Move all the players to the resulting destination. Guaranteed to finish in N steps per turn for an N player game (worst case being a chain of players each moving to the next player's current cell, with the last player in the chain attempting to move onto a wall).

• Pseudo random number source: Does anyone have a preferred/recommended random number generator? Is there any reason to consider a true random number source?