#Flit - a simple board game for bots

##Overview

###Neutral pieces

###Moving

###Communication

#Specification

Available: An available square is an empty square 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. The board has no boundaries - no edges or corners to give an advantage.

###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. [This differs from the human playable version linked above: there a list is kept of all available squares and a neutral piece is placed on one of those with probability 1/6 each turn - I now prefer this approach so the rate of new neutral pieces does not slow in the end game]

###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 (8,192 per bot)
• 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.

Flit - a simple board game for bots

Overview

Neutral pieces

Moving

Communication

Specification

Available: An available square is an empty square 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. The board has no boundaries - no edges or corners to give an advantage.

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. [This differs from the human playable version linked above: there a list is kept of all available squares and a neutral piece is placed on one of those with probability 1/6 each turn - I now prefer this approach so the rate of new neutral pieces does not slow in the end game]

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 (8,192 per bot)
• 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.

Ideally I'd like each bot to play from a different raspberry pi, as described in this Fortnightly Challenge suggestion, but to start out I will probably try a simplified Stack Snippets version (see the end of this sandbox post).

###Neutral pieces

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.

#Specification

Available: An available square is an empty square 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. The board has no boundaries - no edges or corners to give an advantage.

###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 (8,192 per bot)
• 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.

#Sandbox questions

I may post a Stack Snippets version of this question to see if the dynamics are interesting and to iron out some loopholes, before considering a full language agnostic version. I've posted a meta question to see how people feel about the idea of running a trial version of a question (which has received some interesting feedback). For here in the sandbox, I'm just looking for guidance on how much to simplify it. I want it to be simpler than the full game so that the final question doesn't end up being too similar, but I still want it to stand alone as an interesting question.

My current thoughts for the simple Stack Snippets version:

• Only 2 players per game
• Small board to keep games short: 16 by 16
• Maximum number of moves 1,024 (512 per bot)
• Time limit per turn: 100ms (so games should last less than 2 minutes)

I've made a human playable version of this game with a simple strategy to give an idea of how the game plays out. You can play it before or after reading the rules here - picking up the rules intuitively adds an extra challenge...

If playing this gives any idea about whether the KotH version would be better with 2, 4, or more players per game, or any other subtle adjustments that would help, please let me know.

###Neutral pieces

[Not moving is a valid move, and is indicated by specifying the same coordinates for origin square and destination square. not sure about this rule] 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.

#Specification

Available: An available square is an empty square 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. The board has no boundaries - no edges or corners to give an advantage.

###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. [This differs from the human playable version linked above: there a list is kept of all available squares and a neutral piece is placed on one of those with probability 1/6 each turn - I now prefer this approach so the rate of new neutral pieces does not slow in the end game]

###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 (8,192 per bot)
• 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.