#Flit - a simple board game for bots
Note: adjacency is vertical or horizontal - for this game there are no diagonal neighbours.
##Overview
The board is a square grid. Each bot starts with 2 pieces of their colour, and gains more pieces by converting neutral pieces that appear from time to time. The objective is to end up with more pieces than your opponents.
Each turn, one bot moves. It chooses one of its pieces and moves it to be next to another of its pieces. There is no limit to the distance a piece can move in a single step, provided it lands next to a piece of the same colour.
Ideally I'd like each bot to play from a different raspberry pi, as described in this Fortnightly Challenge suggestion.
###Neutral pieces
There are initially zero neutral pieces.
A new neutral piece can appear at any point, regardless of whether there are already neutral pieces unconverted. A neutral piece will only appear on a square that has 4 empty neighbours, to prevent it being instantly converted.
If a neutral piece is adjacent to another piece, it is converted - it becomes the colour of that piece. A neutral piece can only ever be adjacent to a single other piece - it will be instantly converted before any other bot has a chance to move next to it.
###Moving
A move is specified by an origin square and a destination square. It is a valid move if the origin square contains a piece of the bot's colour, and the destination square is empty and is adjacent to at least one piece of the bot's colour.
Not moving is a valid move, and is indicated by specifying the same coordinates for origin square and destination square. Not supplying a move within the time limit also results in not moving, but repeatedly exceeding the time limit will lead to the bot losing the opportunity to make further moves.
###Communication
The board information will not be supplied each turn. Instead the bot must keep track of the board state itself. Each time a change is made a message will be sent to all bots describing the change. If a bot chooses not to move, the non-move will not be broadcast.
The board starts empty. The initial two pieces for each bot will be broadcast to all bots, then the first bot will be sent a request for a move, to which it must respond within the time limit. Any response sent after the time limit expires will be discarded (any waiting input will be read and discarded before the next request for a move is sent to that bot).
Bots will therefore have complete information about the board state at all times.
#Specification
Available: An available square is one that has 4 empty neighbours
###Players There are 4 bots competing in each game. Bots are numbered 1 to 4 and take turns in that fixed order.
###Board The board is a 32 by 32 square grid. It wraps toroidally - every square has 4 neighbours. There are no edge squares.
###Initial state For each bot, one piece will be placed on a square chosen uniformly from the available squares. After all first pieces have been placed, a second piece will be placed for each bot in the same way. The initial state contains no neutral pieces.
###Addition of neutral pieces Each turn one bot will move. After that move has been made, the addition of a new neutral piece will be considered. A square will be selected at random. If that square is available then a neutral piece will be placed on it with probability 1/16. If the square is unavailable then play continues - a second square will not be selected.
###Bot STDIN All received messages will be terminated by a newline. Each bot will receive messages of two types: an update or a move request
Update:
x y c
where (x, y) is the square to be updated, and c is the new colour (which may be 0 for empty, 1, 2, 3 or 4 for a bot colour, or 5 for neutral).
Move request:
M
where M is the literal string "M" and indicates that a move is required.
###Bot STDOUT The response must be terminated by a newline. A bot responds with a move in the following format:
x0 y0 x1 y1
where (x0, y0) is the origin square, and (x1, y1) is the destination square.
If origin and destination are identical, no move will be made. This is valid and does not lead to the bot being penalised. The bot will only be penalised if it fails to respond within the time limit.
###Time limit The time limit is 50ms. If a bot exceeds the time limit on 5 consecutive turns then it will no longer be prompted for moves. That bot will be frozen for the rest of the game.
###Winning criterion The winner is the bot with the most pieces when the game ends. There is no reward for second place. If two bots tie for first place, neither is rewarded.
The game ends when one of the following conditions is met:
- the total number of turns taken exceeds 32,768
- all 4 bots choose not to move consecutively
- one bot has too many pieces to catch up with
Too many pieces to catch up with is defined as follows:
- A, B and C are the numbers of pieces of the other 3 bots.
- D is the number of pieces of the bot in question.
- N is the number of neutral pieces.
- E is the number of empty squares.
- P is the number of potential neutral pieces. P = N + E - 4
- M is the maximum number of pieces attainable by A, B or C.
- M = Max(A+P, B+P, C+P)
- If D > M then the bot has too many pieces to catch up with.
I've tried to make this game as simple as possible, while still having non-trivial dynamics. I may post a Stack Snippets version of this question to see if the dynamics are interesting, before considering a full language agnostic version. I've posted a meta question to see how people feel about this idea.